< Back




455. Assign Cookies

We have a list of children with greed[i] and a list of cookies with size s[i]. Children will only
accept cookies that fit the constaint s[i] >= greed[i].

Regular greedy problem, we could solve this with a max heap or sort, either way they have the same
time and space complexity. Solving it with sort, we'll maintain a pointer to the current cookie and
a pointer to the child.

If the child will accept the cookie, we increment both pointers, otherwise we only increment the
cookie pointer. We finally return the number of children that were satisfied - which is the pointer
to the child.

The solution is as follows:


  class Solution:
      def findContentChildren(self, g: List[int], s: List[int]) -> int:
          s.sort()
          g.sort()
          m, n = len(s), len(g)
          i = j = 0

          while i < m and j < n:
              if s[i] >= g[j]:
                  j += 1

              i += 1

          return j


_ Time Complexity:

  O(n * log(n) + m * log(m)) - We sort both the children and the cookies.

_ Space Complexity:

  O(n + m) - The sort method in Python uses n space.