If we cannot satisfy the least greedy kid with the smallest cookie, we cannot satisfy any other kid with that cookie.
Time: 
from heapq import heapify, heappop as pop
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
minq_greed = [greed for greed in g]
heapify(minq_greed)
minq_size = [size for size in s]
heapify(minq_size)
content_child_count = 0
while minq_greed and minq_size:
smallest_cookie = pop(minq_size)
if smallest_cookie < minq_greed[0]:
continue
pop(minq_greed)
content_child_count += 1
return content_child_count
Although does not improve worst case, to reduce waste, we can match more than one compatible (cookie, kid)-pairs at once.
from heapq import heapify, heappop as pop, heappush as push
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
gmap = {}
for greed in g:
gmap[greed] = gmap.get(greed, 0) + 1
smap = {}
for size in s:
smap[size] = smap.get(size, 0) + 1
minq_greed = [(g, n) for g, n in gmap.items()]
heapify(minq_greed)
minq_size = [(s, n) for s, n in smap.items()]
heapify(minq_size)
content_child_count = 0
while minq_greed and minq_size:
smallest_cookie, cookie_count = pop(minq_size)
least_greed, greed_count = minq_greed[0]
if smallest_cookie < least_greed:
continue
pop(minq_greed)
satisfy_count = min(cookie_count, greed_count)
content_child_count += satisfy_count
if (remaining_cookie_count := cookie_count - satisfy_count) > 0:
push(minq_size, (smallest_cookie, remaining_cookie_count))
if (remaining_greed_count := greed_count - satisfy_count) > 0:
push(minq_greed, (least_greed, remaining_greed_count))
return content_child_count
To improve space complexity we could trade heap for sort.
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
m, n = len(g), len(s)
i, j = 0, 0
content_count = 0
while i < m and j < n:
least_greed = g[i]
smallest_cookie = s[j]
if smallest_cookie < least_greed:
j += 1
continue
content_count += 1
i += 1
j += 1
return content_count
unreasonably effective 
Leave a comment