Problem Statement in English

You’re given an array cookies where cookies[i] contains the number of cookies in the $ith$ bag, and $k$, which is the number of children that the cookies must be distributed amongst.

Your task is to return the minimum amongst the maximum number of cookies that a child gets in each unique distribution.

Approach

There’s no real “smart” way to do this, you simply have to bruteforce it. However, you can dramatically reduce the amount of computation by realizing the fact that we don’t have to recompute distributions that have already been considered.

Let’s call child 1 Ant, and child 2 Bob.

For example if index $0$ and represents cookies given to Ant and index $1$, the cookies given to Bob, then, [0,1] and [1,0] are the same thing! Giving Ant $0$ cookies, and Bob $1$ cookie is the exact same as giving Ant $1$ cookie and Bob $0$ cookies.

So once we’ve calculated the outcome of giving Ant $0$ cookies, and Bob $1$ cookie, we shouldn’t calculate Ant getting $1$ cookie and Bob getting $0$ cookies.

Take a look at this tree to get a strong visual grip of it.

Consider the input, cookies = [1,2,3], k = 2

    graph TD
    A(<0,0>) -->|Ant gets 1| B(<1,0>)
    A -->|Bob gets 1| C(<0,1>)

    B -->|Ant gets 2| D(<3,0>)
    B -->|Bob gets 2| E(<1,2>)

    C -->|Ant gets 2| F(<2,1>)
    C -->|Bob gets 2| G(<0,3>)

    D -->|Ant gets 3| H(<6,0>)
    D -->|Bob gets 3| I(<3,3>)

    E -->|Ant gets 3| J(<4,2>)
    E -->|Bob gets 3| K(<1,5>)
    
    F -->|Ant gets 3| L(<5,1>)
    F -->|Bob gets 3| M(<2,4>)
    
    G -->|Ant gets 3| N(<3,3>)
    G -->|Bob gets 3| O(<0,6>)

If you look closely, you’ll realise that half the tree is redundant. We can save a lot on compute by memoization/caching.

Solution in Python



class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        ans = -1

        # this decorator internally handles memoization
        # by caching function calls
        #
        # we're assigning `currDistribution` a type of tuple
        # as it can be hashed, while lists can't,
        # and the cache decorator only accepts hashable types
        @cache
        def recursiveCall(bagIndex, currDistribution: tuple[int]):
            # bind to `ans`
            nonlocal ans

            # we've processed all bags
            if bagIndex >= len(cookies):
                if ans == -1:
                    ans = max(currDistribution)
                else:
                    ans = min(ans, max(currDistribution))
                # terminate this path as we've processed all cookie bags
                return

            # convert the tuple to a list
            # since we need to mutate it
            # (list) currDistribution
            lcd = list(currDistribution)

            # add the current cookie bag to each distinct child as separate possibilities
            for i in range(len(lcd)):
                # copy the list
                copied_currentDistribution = lcd.copy()
                # add the current cookie bag to each index separately
                copied_currentDistribution[i] += cookies[bagIndex]

                # backtrack
                recursiveCall(bagIndex + 1, tuple(sorted(copied_currentDistribution)))

        # init call
        # init tuple with `k` 0s
        recursiveCall(0, (0 for _ in range(k)))

        # return answer
        return ans

Complexity

  • Time: $O(n \times k^n)$
    $n$ represents the number of cookie bags, (len(cookies)). Instead of the regular $2^n$, it’s $k^n$ because we generate $k$ different possibilities.

    Since we do this for each cookie in the cookie bag, it’s $n \times k^n$.

  • Space: $O(k \times k^n)$
    Since we generate $k^n$ arrays, each with a max length of $k$.

Note: For what it’s worth, we don’t actually get anywhere near these numbers as we achieve massive savings, thanks to memoization.

Mistakes I Made

I didn’t realize just how much duplication was occuring, and so I wasn’t caching function calls. Needless to say, I got a Time Limit Exceeded error :(

And we are done.