L5. Fruit Into Baskets | 2 Pointers and Sliding Window

This chapter covers the classic "Fruit Into Baskets" problem, a core pattern in the Two Pointer and Sliding Window algorithmic catalog. By mastering this problem, you will learn how to reduce complex substring/subarray constraints into clean, linear-time sliding window solutions.

1. Problem Statement & Real-World Analogy

Imagine you visit a farm with a row of fruit trees represented as an array of integers (e.g., [3, 3, 3, 1, 2, 1, 1, 2, 3]). Each number corresponds to a specific type of fruit produced by that tree.

The Rules of Harvest

1. Two Baskets: You are given exactly two baskets to collect your harvest.
2. Single Type per Basket: Each individual basket can hold only one unique type of fruit (though you can collect as many individual fruits of that type as you want).
3. No Skipping: You must pick fruits contiguously. Once you start picking, you cannot skip trees or break the continuous sequence.

Your goal is to find the maximum number of fruits you can collect under these constraints.

Real-Life Analogy

Real-Life Analogy (The Shopping Cart & Shelf Limit): Think of walking down a grocery aisle where every shelf has a specific item. You are allowed to carry two shopping bags. Bag A can hold only apples, and Bag B can hold only oranges. You want to walk as far down the aisle as possible without violating your 2-bag/2-item-type limit. The moment you encounter a third type of item (e.g., bananas), your current stretch is broken, and you must decide where to start your next continuous run.

2. Reducing the Problem: Finding the Subarray Constraint

Before writing code, we must translate the physical constraints into computer science terms.

• The requirement of picking contiguous fruits without skipping maps directly to finding a subarray (a consecutive portion of an array).
• The rule allowing at most two types of fruit maps to having at most two unique numbers in our subarray.

Thus, the problem statement simplifies to:

Core Problem Reduction: Find the maximum length subarray that contains at most two unique numbers.

Even if an array contains all identical numbers (e.g., [3, 3, 3, 3]), it is still valid because we can put all of them into one basket and leave the second basket empty.

3. The Naive Brute Force Approach

The most straightforward way to solve any subarray problem is to generate and evaluate every possible subarray.

Strategy

1. Use an outer loop (i) to fix the starting point of the subarray.
2. Use an inner loop (j) to expand the ending point from i to the end of the array (n).
3. Maintain a data structure (such as a Set) to track unique fruit types.
4. If the set size exceeds 2, the subarray becomes invalid, and we can immediately break out of the inner loop.
5. Track the maximum length encountered across all valid subarrays.

Naive Implementation (Conceptual)

int maxLength = 0;
for (int i = 0; i < n; i++) {
    Set<Integer> set = new HashSet<>();
    for (int j = i; j < n; j++) {
        set.add(arr[j]);
        if (set.size() <= 2) {
            maxLength = Math.max(maxLength, j - i + 1);
        } else {
            break; // More than 2 unique fruit types; stop expanding from this 'i'
        }
    }
}
return maxLength;

Complexity Analysis

• Time Complexity: $O(N^2)$ because of the nested loops checking every possible starting and ending point. (Set operations take $O(1)$ or $O(\log 3)$ since the set size never exceeds 3).
• Space Complexity: $O(3) = O(1)$ auxiliary space for the set.

While correct, an $O(N^2)$ solution is too slow for large datasets ($N \ge 10^5$) and will fail interviews. We need an optimized approach.

4. Transitioning to the Sliding Window Pattern

Whenever an interview problem asks for the longest subarray or window satisfying a specific condition, the optimal paradigm is Sliding Window with Two Pointers (L and R).

Mental Model for Sliding Window

• Right Pointer (R): Expands the window by moving to the right, incorporating new elements.
• Left Pointer (L): Shrinks the window from the left when the constraint (at most 2 unique fruit types) is violated.
• Frequency Map: A hash map stores elements and their counts within the current window to keep track of unique types.

5. Better Approach: $O(2N)$ Sliding Window

In this standard sliding window approach, whenever our window becomes invalid (map size > 2), we shrink the window from the left by moving L repeatedly until the window becomes valid again.

Step-by-Step Execution Flow

When invalid, we enter a cleanup loop:

1. Decrement the frequency of arr[L] in the map.
2. If its frequency drops to 0, completely erase arr[L] from the map.
3. Increment L until the map size drops back to 2 or fewer.

Pseudo-Code ($O(2N)$ Approach)

int l = 0, r = 0, maxLength = 0;
Map<Integer, Integer> map = new HashMap<>();

while (r < arr.length) {
    // 1. Expand window by adding arr[r]
    map.put(arr[r], map.getOrDefault(arr[r], 0) + 1);
    
    // 2. Shrink window from the left if invalid (size > 2)
    while (map.size() > 2) {
        map.put(arr[l], map.get(arr[l]) - 1);
        if (map.get(arr[l]) == 0) {
            map.remove(arr[l]);
        }
        l++;
    }
    
    // 3. Window is guaranteed valid here; update max length
    if (map.size() <= 2) {
        maxLength = Math.max(maxLength, r - l + 1);
    }
    
    r++;
}
return maxLength;

Complexity Analysis

• Time Complexity: $O(2N)$. In the worst-case scenario (e.g., all identical elements followed by two unique elements), the right pointer traverses the array of size $N$, and the left pointer also traverses up to $N$ steps. Thus, $N + N = 2N$ operations.
• Space Complexity: $O(3) = O(1)$ because the hash map never stores more than 3 unique keys at any given time.

6. Optimal Approach: $O(N)$ Sliding Window

While $O(2N)$ is accepted in most interviews, premier interviewers may ask: "Can you optimize this to strict $O(N)$?"

The Insight for Strict $O(N)$

In the $O(2N)$ approach, when the window becomes invalid, the while loop aggressively drags L forward step-by-step until validity is restored.

However, notice that we only care about finding the maximum possible window length. If our maximum window length reaches size 4, we never need to check windows of size smaller than 4 again!

Instead of aggressively shrinking L multiple times in a while loop, we can simply slide the window at a fixed maximum size:

• When adding arr[r] violates the limit (size > 2), we increment L by only 1 (instead of a full while loop).
• This maintains the maximum window size achieved so far, preventing the window from ever shrinking below its historical best, while still correctly tracking valid combinations as R advances.

Optimal Pseudo-Code ($O(N)$ Approach)

int l = 0, r = 0, maxLength = 0;
Map<Integer, Integer> map = new HashMap<>();

while (r < arr.length) {
    // 1. Add current element to map
    map.put(arr[r], map.getOrDefault(arr[r], 0) + 1);
    
    // 2. If invalid, instead of a while loop, shift L by just 1
    if (map.size() > 2) {
        map.put(arr[l], map.get(arr[l]) - 1);
        if (map.get(arr[l]) == 0) {
            map.remove(arr[l]);
        }
        l++; // Single shift maintains max window size boundary
    }
    
    // 3. Update max length if valid
    if (map.size() <= 2) {
        maxLength = Math.max(maxLength, r - l + 1);
    }
    
    r++;
}
return maxLength;

Complexity Analysis

• Time Complexity: $O(N)$ because both r and l move forward at most once per iteration without nested loops.
• Space Complexity: $O(1)$ auxiliary space (map size capped at 3).

7. Comparison Summary Table

Summary and Key Takeaways

• Problem Translation: Recognizing that "at most two baskets of unique fruit types" translates directly to finding the maximum length subarray with at most 2 unique elements.
• Sliding Window Paradigm: Subarray and substring optimization problems are best solved using the Two Pointer / Sliding Window pattern.
• Role of Pointers: The Right pointer (R) expands the window to explore new possibilities, while the Left pointer (L) adjusts the window to enforce constraints.
• Frequency Mapping: A Hash Map is essential for keeping track of unique element counts in $O(1)$ time.
• Space Efficiency: Because the unique element limit is strictly bound to 2 (plus 1 temporarily during expansion), auxiliary space complexity remains $O(1)$ constant.
• Interview Strategy: Always start by explaining the Brute Force ($O(N^2)$), transition immediately to the standard Sliding Window ($O(2N)$), and if time permits, deliver the polished $O(N)$ optimized solution.