Course4all

Fruit Into Baskets

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Sliding Window.

Fruit Into Baskets

You are visiting a farm that has a single row of fruit trees. Each tree has a type. You have TWO baskets, each holding ONE type. Find the maximum fruits you can collect in a contiguous range.

Visual Representation

fruits = [1, 2, 1, 2, 3] L R | | 1, 2, 1, 2, 3 Types: {1, 2}, Count: 4 [---------] L R | | 1, 2, 1, 2, 3 Types: {2, 3}, Count: 2 [-]
Medium

Examples

Input: fruits = [1,2,1]
Output: 3
Approach 1

Level I: Brute Force

Intuition

Check every possible contiguous range of trees and count how many fruits and types are in that range. If the number of types is ≤ 2, the range is valid. Track the maximum fruits collected.

Thought Process

  1. Use two nested loops to define all possible ranges [i, j].
  2. In the inner loop, add each fruit to a set to count types.
  3. If types ≤ 2, update maxFruits = max(maxFruits, j - i + 1).
  4. If types > 2, break the inner loop.
⏱ O(N^2)💾 O(1) - The set size is at most 3 before breaking.

Detailed Dry Run

ijfruits[j]TypesFruitsMax
001{1}11
012{1, 2}22
021{1, 2}33
032{1, 2}44
043{1, 2, 3}54 (Break)
java
import java.util.*;

public class Main {
    public static int totalFruit(int[] fruits) {
        int maxFruits = 0;
        for (int i = 0; i < fruits.length; i++) {
            Set<Integer> types = new HashSet<>();
            for (int j = i; j < fruits.length; j++) {
                types.add(fruits[j]);
                if (types.size() <= 2) {
                    maxFruits = Math.max(maxFruits, j - i + 1);
                } else {
                    break;
                }
            }
        }
        return maxFruits;
    }

    public static void main(String[] args) {
        int[] fruits = {1, 2, 1, 2, 3};
        System.out.println(totalFruit(fruits)); // 4
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum number of fruits L we can collect. For a fixed length L, we check if any contiguous subarray of length L contains at most 2 distinct fruit types using a fixed-size sliding window.

Thought Process

  1. Search range is [1, n].
  2. For a fixed mid length:
    • Slide a window of size mid.
    • Maintain a frequency map of fruit types in the window.
    • If map.size() <= 2 at any point, the length mid is possible.
  3. Adjust the search range based on possibility.

Pattern: BS on Answer + Sliding Window Check

⏱ O(N log N)💾 O(1) - The map size in the check is at most 3.
java
public class Solution {
    public int totalFruit(int[] fruits) {
        int low = 1, high = fruits.length, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canCollect(fruits, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean canCollect(int[] fruits, int len) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < fruits.length; i++) {
            counts.put(fruits[i], counts.getOrDefault(fruits[i], 0) + 1);
            if (i >= len) {
                int out = fruits[i - len];
                counts.put(out, counts.get(out) - 1);
                if (counts.get(out) == 0) counts.remove(out);
            }
            if (i >= len - 1 && counts.size() <= 2) return true;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We need to find the longest subarray that contains exactly or at most two distinct elements. We use a frequency map to track the fruits in our window. When the number of types (map size) exceeds 2, we shrink the window from the left.

Pattern: Variable Size Sliding Window (K Distinct Elements)

  • Expand: count[fruits[right]]++
  • Constraint: count.size() > 2
  • Shrink: while (count.size() > 2) { count[fruits[left]]--; if (count[fruits[left]] == 0) count.remove(fruits[left]); left++; }
⏱ O(N)💾 O(1) - Hash Map size is at most 3.

Detailed Dry Run

RFruitMapMap SizeActionResult
01{1:1}1Expand1
12{1:1, 2:1}2Expand2
21{1:2, 2:1}2Expand3
32{1:2, 2:2}2Expand4
43{1:2, 2:2, 3:1}3Shrink L (remove 1s)4
java
import java.util.*;

public class Main {
    public static int totalFruit(int[] fruits) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, maxFruits = 0;
        for (int right = 0; right < fruits.length; right++) {
            count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);
            
            while (count.size() > 2) {
                count.put(fruits[left], count.get(fruits[left]) - 1);
                if (count.get(fruits[left]) == 0) {
                    count.remove(fruits[left]);
                }
                left++;
            }
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }

    public static void main(String[] args) {
        int[] fruits = {1, 2, 1, 2, 3};
        System.out.println(totalFruit(fruits)); // 4
    }
}

⚠️ Common Pitfalls & Tips

Be careful with shrinking: ensure you decrement the count and remove the key from the map ONLY when the count reaches zero. Forgetting to remove the key will result in an incorrect count.size().

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMax Consecutive Ones III
Next Question →Longest Repeating Character Replacement