Fruits into Baskets (Longest Subarray with At Most Two Distinct Values)

• Problem reduction – two baskets, each holding one fruit type, means the window can contain at most two distinct types.
• Sliding window – expand right, adding each type's count; shrink left when distinct types exceed two.
• Frequency map – tracks the count of each type in the current window; remove a type when its count hits zero.
• Generalization – the same template solves "longest subarray with at most k distinct values" for any k.
• Complexity – O(n) time, O(1) space (map holds at most 3 keys transiently).

What is the problem?

You walk along a row of trees, each producing one type of fruit. You have two baskets, each holding only one type. You must pick from every tree you pass, moving right, until you encounter a third type. Find the maximum number of fruits you can collect.

This is exactly the longest subarray with at most two distinct values.

Why is pattern recognition the key insight?

The fruit-and-basket framing is a disguise for the k-distinct sliding window where k = 2. Candidates who try to invent a bespoke basket simulation overcomplicate it. Recognizing the reduction is the main value of this problem in an interview.

How does the sliding window solution work?

package com.bank.analytics;

import java.util.HashMap;
import java.util.Map;

public class FruitsIntoBaskets {
    public static int totalFruit(int[] trees) {
        Map<Integer, Integer> basket = new HashMap<>();
        int left = 0;
        int maxFruits = 0;

        for (int right = 0; right < trees.length; right++) {
            basket.merge(trees[right], 1, Integer::sum);

            while (basket.size() > 2) {
                int leftType = trees[left];
                basket.merge(leftType, -1, Integer::sum);
                if (basket.get(leftType) == 0) {
                    basket.remove(leftType);
                }
                left++;
            }

            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }

    public static void main(String[] args) {
        int[] trees = {1, 2, 1, 3, 4, 3, 5, 5, 5};
        System.out.println("Max fruits: " + totalFruit(trees));
    }
}

Max fruits: 4

Why remove the key when count reaches zero?

The map's size represents the number of distinct types in the window. If you leave a key with count zero, the map falsely reports three distinct types even when there are only two.

// Wrong: leaves dead keys
basket.put(leftType, basket.get(leftType) - 1);
// basket.size() is still 3 even if one type's count is 0

// Correct: remove when count reaches 0
basket.merge(leftType, -1, Integer::sum);
if (basket.get(leftType) == 0) basket.remove(leftType);

What is the step-by-step trace?

For trees [1, 2, 1, 3, 4, 3, 5, 5, 5]:

• right=0: basket={1:1}. Window [1]. max=1.
• right=1: basket={1:1, 2:1}. Window [1,2]. max=2.
• right=2: basket={1:2, 2:1}. Window [1,2,1]. max=3.
• right=3: basket={1:2, 2:1, 3:1}. Size 3, shrink: remove trees[0]=1, count 1:1. Still 3 types. Remove trees[1]=2, count 2:0, remove key. basket={1:1, 3:1}. left=2. Window [1,3]. max=3.
• right=4: basket={1:1, 3:1, 4:1}. Shrink. left moves until size <= 2. basket={3:1, 4:1}. max=3.
• right=5: basket={3:2, 4:1}. max=3.
• right=6: basket={3:2, 4:1, 5:1}. Shrink. basket={3:1, 5:1}. max=3.
• right=7: basket={3:1, 5:2}. max=3.
• right=8: basket={3:1, 5:3}. Window size 4. max=4.

Answer: 4 (window [3, 5, 5, 5]).

How does this generalize to k distinct values?

Replace basket.size() > 2 with basket.size() > k. The rest of the code stays identical.

public static int longestWithKDistinct(int[] arr, int k) {
    Map<Integer, Integer> window = new HashMap<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < arr.length; right++) {
        window.merge(arr[right], 1, Integer::sum);
        while (window.size() > k) {
            int leftVal = arr[left];
            window.merge(leftVal, -1, Integer::sum);
            if (window.get(leftVal) == 0) window.remove(leftVal);
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

What is the time and space complexity?

| Aspect | Complexity |
|---|---|
| Time | O(n), each pointer moves forward at most n times |
| Space | O(1) effective, map holds at most k+1 = 3 keys transiently |

What are common mistakes?

Not removing keys when their count reaches zero, causing the map size to be inaccurate.

Forgetting to shrink fully (using if instead of while), which leaves the window with too many distinct types.

What are the edge cases?

• All trees same type: the entire array is the answer.
• All trees different types: the answer is 2 (any two adjacent trees).
• Empty array: return 0.
• Single tree: return 1.

What should a senior engineer know?

The entire value of this problem is spotting the reduction. Once you see it is k-distinct with k=2, the solution is the standard sliding window template. Demonstrating that you see one unified template behind several differently-worded problems is exactly what interviewers want.

The removal-on-zero rule is the common bug source across all frequency-map sliding window problems.

What are common interview follow-up questions?

• What if you have k baskets instead of 2? (Parameterize the limit.)
• What if you want the shortest window with at least k distinct types? (Reverse the shrink condition.)
• What about the longest substring with at most k distinct characters? (Same algorithm on a character array.)