Fruit in Baskets [ Sliding Window]

XXX. Total Fruit

Array

Sliding Window

HashMap

Problem Statement:

You are visiting a row of trees represented as an integer array fruits, where fruits[i] is the type of fruit the ith tree produces. You can carry at most two types of fruits at the same time. Your goal is to pick the maximum number of fruits in a row while adhering to this rule.

Example:

Input: [1, 2, 1] Output: 3 Explanation: You can pick all fruits.

Approach:

1. Use a sliding window to maintain the range of valid subarrays where at most two types of fruits exist.
2. Use a hash map basket to keep track of the count of each type of fruit in the current window.
3. Expand the window by iterating through the array and adding fruits to the basket.
4. If the basket exceeds two types of fruits, shrink the window from the left by removing one fruit type at a time until the basket has at most two types.
5. The maximum size of the window during this process gives the desired result.

Algorithm Intuition:

The problem can be viewed as finding the largest subarray containing at most two distinct elements. The sliding window technique is ideal for this, as it dynamically adjusts the window size while keeping track of valid subarrays. The hash map acts as a "basket" to store the fruit types and their counts, enabling efficient management of the subarray properties.

Complexity:

Time Complexity: O(n), where n is the length of the array. Each element is added to and removed from the hash map at most once.
Space Complexity: O(1), as the hash map stores at most two keys at any given time.

Java Implementation:

// Sliding Window Approach
public int totalFruit(int[] fruits) {
    // Hash map 'basket' to store the types of fruits.
    Map basket = new HashMap<>();
    int left = 0, right;

    // Add fruit from the right side (right) of the window.
    for (right = 0; right < fruits.length; ++right) {
        basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);

        // If the current window has more than 2 types of fruit,
        // remove one fruit from the left index (left) of the window.
        if (basket.size() > 2) {
            basket.put(fruits[left], basket.get(fruits[left]) - 1);
            if (basket.get(fruits[left]) == 0) basket.remove(fruits[left]);
            left++;
        }
    }

    // Once we finish the iteration, the indexes left and right 
    // represent the longest valid subarray we encountered.
    return right - left;
}