Fruit Into Baskets

Fruit Into Baskets

What is this problem about?

The Fruit Into Baskets interview question asks you to find the longest contiguous subarray that contains at most two unique numbers. The story is framed as picking fruit from trees: you have two baskets, each basket can hold only one type of fruit, and you must pick exactly one fruit from every tree continuously until you hit a third type of fruit. You want to maximize the total number of fruits picked.

Why is this asked in interviews?

This is one of the most famous Sliding Window interview pattern problems, frequently asked by Google, Amazon, and Microsoft. It is essentially the "Longest Substring with At Most 2 Distinct Characters" problem disguised with a story. It tests a candidate's ability to maintain a dynamic window and use a Hash Map to track the frequency of elements within that window.

Algorithmic pattern used

This problem is solved using a Sliding Window with a Hash Map.

1. Use two pointers, left and right.
2. Expand the window by moving right and adding the fruit type to a Hash Map, keeping track of its frequency.
3. If the Hash Map size exceeds 2 (meaning you found a 3rd type of fruit), you must shrink the window from the left.
4. Decrement the frequency of the fruit at the left pointer. If its frequency becomes 0, remove it from the map.
5. Keep track of the maximum window size (right - left + 1) whenever the map size is $\le 2$.

Example explanation

Fruits: [1, 2, 1, 2, 3]

1. right at 0: Fruit 1. Map: {1: 1}. Max = 1.
2. right at 1: Fruit 2. Map: {1: 1, 2: 1}. Max = 2.
3. right at 2: Fruit 1. Map: {1: 2, 2: 1}. Max = 3.
4. right at 3: Fruit 2. Map: {1: 2, 2: 2}. Max = 4.
5. right at 4: Fruit 3. Map: {1: 2, 2: 2, 3: 1}. Size is 3!
   • Move left. Remove fruit 1. Map: {1: 1, 2: 2, 3: 1}. Still size 3.
   • Move left. Remove fruit 2. Map: {1: 1, 2: 1, 3: 1}. Still size 3.
   • Move left. Remove fruit 1. Map: {2: 1, 3: 1}. Size is 2. (Valid window is [2, 3]). Max remains 4.

Common mistakes candidates make

• Not removing keys: Forgetting to completely delete a key from the Hash Map when its frequency drops to 0, causing the map.size() check to fail.
• Jumping the left pointer: Trying to cleverly jump the left pointer to the last occurrence of the dropped fruit instead of moving it one by one. While possible, it's prone to bugs. The standard while loop shrink is safer and still $O(N)$.

Interview preparation tip

Memorize the template for "Longest Subarray with at most K distinct elements." The exact same code works for 2 baskets, 3 baskets, or $K$ unique characters in a string.