Fruit Into Baskets

Master this topic with zero to advance depth.

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

Use two nested loops to define all possible ranges [i, j].
In the inner loop, add each fruit to a set to count types.
If types ≤ 2, update maxFruits = max(maxFruits, j - i + 1).
If types > 2, break the inner loop.

⏱ O(N^2)💾 O(1) - The set size is at most 3 before breaking.

Detailed Dry Run

j	fruits[j]	Types	Fruits	Max
0	1	{1}	1	1
1	2	{1, 2}	2	2
2	1	{1, 2}	3	3
3	2	{1, 2}	4	4
4	3	{1, 2, 3}	5	4 (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

Search range is [1, n].
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.
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

R	Fruit	Map	Map Size	Action	Result
0	1	{1:1}	1	Expand	1
1	2	{1:1, 2:1}	2	Expand	2
2	1	{1:2, 2:1}	2	Expand	3
3	2	{1:2, 2:2}	2	Expand	4
4	3	{1:2, 2:2, 3:1}	3	Shrink 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().

← Previous QuestionMax Consecutive Ones III

Next Question →Longest Repeating Character Replacement

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.