Leetcode 904. Fruit Into Baskets

Clarification

Okay, so first I’ll restate the problem. We are given an integer array fruits, where each number represents a type of fruit on a tree. We have two baskets, and each basket can only hold one type of fruit. We need to pick fruits from a contiguous section of trees and return the maximum number of fruits we can pick. So basically, I need to find the longest subarray that contains at most two distinct values.

Should I return the maximum number of fruits, or the actual subarray?
How many types of fruits do we have?
Is there a limitation on how many fruit each bucket can hold?

Brute-force Approach

The simple way is: for every starting index, keep expanding to the right while tracking fruit types in a set. Once we have more than two types, stop and update the maximum length. That works, but in the worst case it is O(n²).

Optimized Approach

Since this is a subarray problem, we can consider to use sliding window approach trying to optimize it.

I’ll use two pointers, left and right, and a hash map to count how many of each fruit type exists inside the current window. When I expand right, I add the new fruit into the map. If the map has more than two fruit types, the window is invalid, so I move left forward and remove fruits from the map until the window becomes valid again. Then after each valid window, I update the maximum length.

So why does it work? There are three most important things for a sliding window: when to increase the window; when to shrink the window; when to update the result. The key observation for this question is that the window always contains at most two fruit types. If the window is valid, we try to expand it to hold more fruits. Once we encounter the third type fruit tree, there is no point to keep increasing the window. So the best thing to do is to move the left boundary forward until we completely remove one fruit type. Since we are looking for the longest window, we have to update the result whenever the window gets bigger.

Since both pointers only move forward and never backward, each element enters and leaves the window at most once, this gives us O(n) time. The space is O(1) because even we use a hash map, the map stores at most two types of fruits, so the space is constant.

Code

class Solution {
    // find the longest subarray that has maximum two values
    public int totalFruit(int[] fruits) {
        int left = 0, right = 0;
        Map<Integer, Integer> bucket = new HashMap();
        int max = 0;

        while (right < fruits.length) {
            while (left < right && !bucket.containsKey(fruits[right]) && bucket.size() >= 2) {
                int fruitL = fruits[left];
                bucket.put(fruitL, bucket.get(fruitL) - 1);
                if (bucket.get(fruitL) == 0)      bucket.remove(fruitL);
                left++;
            }

            int fruitR = fruits[right];
            bucket.put(fruitR, bucket.getOrDefault(fruitR, 0) + 1);
            right++;
            max = Math.max(max, right - left);
        }

        return max;
    }
}

Follow-up