41. Fruit Into Baskets

🔗 LeetCode Problem: 904. Fruit Into Baskets
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Sliding Window

Problem Statement

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

Example 2:

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

Example 3:

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

Constraints: - 1 <= fruits.length <= 10^5 - 0 <= fruits[i] < fruits.length

---

🎨 Visual Understanding

The Problem Visualized

fruits = [1, 2, 3, 2, 2]

Two baskets, each can hold one type of fruit.

Option 1: Start from index 0
[1, 2, 3, 2, 2]
 ↓  ↓  
 Pick 1 and 2, then encounter 3 (third type) → Stop
 Collected: 2 fruits

Option 2: Start from index 1
[1, 2, 3, 2, 2]
    ↓  ↓  ↓  ↓
 Pick 2 and 3, continue with 2 and 2 → 4 fruits ✓

Answer: 4

Key Observation: This is "At Most 2 Distinct" Problem!

The problem is asking:
"Find the longest contiguous subarray with at most 2 distinct elements"

This is EXACTLY Problem #37 with k = 2!
- Longest Substring with At Most K Distinct Characters (k = 2)

Fruit types = Characters
Baskets (2) = Distinct limit (k = 2)
Maximum fruits = Length of longest subarray

Example:
fruits = [1, 2, 3, 2, 2]

All subarrays with ≤ 2 distinct types:
[1]         → 1 type, length 1
[1, 2]      → 2 types, length 2
[2]         → 1 type, length 1
[2, 3]      → 2 types, length 2
[2, 3, 2]   → 2 types, length 3
[2, 3, 2, 2] → 2 types, length 4 ✓ (maximum)
[3]         → 1 type, length 1
[3, 2]      → 2 types, length 2
[3, 2, 2]   → 2 types, length 3
[2]         → 1 type, length 1
[2, 2]      → 1 type, length 2

Answer: 4

Visual Process

fruits = [1, 2, 3, 2, 2]
k = 2 (two baskets)

Use HashMap to track fruit types:

[1] → {1:1}, distinct = 1 ≤ 2 ✓, len = 1
[1, 2] → {1:1, 2:1}, distinct = 2 ≤ 2 ✓, len = 2
[1, 2, 3] → {1:1, 2:1, 3:1}, distinct = 3 > 2 ✗
Shrink: [2, 3] → {2:1, 3:1}, distinct = 2 ✓, len = 2
[2, 3, 2] → {2:2, 3:1}, distinct = 2 ✓, len = 3
[2, 3, 2, 2] → {2:3, 3:1}, distinct = 2 ✓, len = 4

Maximum: 4

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Try every starting position:
1. For each starting index i
2. Count distinct fruit types while moving right
3. Stop when encountering third type
4. Track maximum fruits collected

Why This Works: - Checks all possibilities - Guaranteed to find answer - Easy to understand

Why This Fails Requirements: - Time complexity O(n²) - Recounts for overlapping windows - Too slow for large arrays - Not optimal for interviews

Implementation

public int totalFruit(int[] fruits) {
    int n = fruits.length;
    int maxFruits = 0;

    for (int i = 0; i < n; i++) {
        Set<Integer> basket = new HashSet<>();

        for (int j = i; j < n; j++) {
            basket.add(fruits[j]);

            if (basket.size() <= 2) {
                maxFruits = Math.max(maxFruits, j - i + 1);
            } else {
                break;  // Third type encountered
            }
        }
    }

    return maxFruits;
}

⏰ Time: O(n²) - for each start, expand until third type
💾 Space: O(1) - HashSet stores at most 3 elements

---

✅ Approach 2: Sliding Window with HashMap (Optimal)

The Breakthrough Insight 💡

Core Logic:

This is "Longest Substring with At Most K Distinct Characters" with k = 2!

Use variable-size sliding window:
1. HashMap tracks fruit type → count
2. Expand window: Add right fruit
3. If distinct > 2: Shrink from left
4. Track maximum length

Key insight: HashMap.size() = number of distinct fruit types

Visual Explanation:

fruits = [1, 2, 3, 2, 2]

Step 1: [1]
        map = {1:1}, distinct = 1 ≤ 2 ✓
        maxFruits = 1

Step 2: [1, 2]
        map = {1:1, 2:1}, distinct = 2 ≤ 2 ✓
        maxFruits = 2

Step 3: [1, 2, 3]
        map = {1:1, 2:1, 3:1}, distinct = 3 > 2 ✗

        Shrink:
        Remove 1: map = {2:1, 3:1}, distinct = 2 ✓
        Window: [2, 3]

Step 4: [2, 3, 2]
        map = {2:2, 3:1}, distinct = 2 ≤ 2 ✓
        maxFruits = 3

Step 5: [2, 3, 2, 2]
        map = {2:3, 3:1}, distinct = 2 ≤ 2 ✓
        maxFruits = 4

Final: 4

Why This Works:

Sliding window maintains invariant:
"At most 2 distinct fruit types in window"

When distinct > 2:
- Shrink from left until distinct ≤ 2
- Each fruit visited at most twice
- Total time: O(n)

HashMap tracks:
- Which fruit types are in window
- Count of each type
- When count becomes 0, remove from map

Implementation

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

    for (int right = 0; right < fruits.length; right++) {
        // Add fruit to basket
        basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);

        // Shrink window if more than 2 types
        while (basket.size() > 2) {
            int leftFruit = fruits[left];
            basket.put(leftFruit, basket.get(leftFruit) - 1);

            // Remove fruit type if count becomes 0
            if (basket.get(leftFruit) == 0) {
                basket.remove(leftFruit);
            }

            left++;
        }

        // Update maximum fruits
        maxFruits = Math.max(maxFruits, right - left + 1);
    }

    return maxFruits;
}

⏰ Time: O(n) - each fruit visited at most twice
💾 Space: O(1) - HashMap stores at most 3 fruit types

---

🔍 Step-by-Step Execution

Example: fruits = [1, 2, 3, 2, 2]

Initial State:
═══════════════════════════════════════════════════════════════════
fruits = [1, 2, 3, 2, 2]
left = 0, maxFruits = 0
basket = {}


Step 1: right = 0, fruit = 1
═══════════════════════════════════════════════════════════════════
Add fruit 1: basket = {1:1}
Distinct count = 1 ≤ 2 ✓

Window: [1]
maxFruits = max(0, 0-0+1) = 1

left = 0, maxFruits = 1


Step 2: right = 1, fruit = 2
═══════════════════════════════════════════════════════════════════
Add fruit 2: basket = {1:1, 2:1}
Distinct count = 2 ≤ 2 ✓

Window: [1, 2]
maxFruits = max(1, 1-0+1) = 2

left = 0, maxFruits = 2


Step 3: right = 2, fruit = 3
═══════════════════════════════════════════════════════════════════
Add fruit 3: basket = {1:1, 2:1, 3:1}
Distinct count = 3 > 2 ✗

Need to shrink:

Shrink iteration 1:
  Remove fruits[0]=1: basket = {2:1, 3:1}
  1 count = 0, remove from basket
  left = 1
  Distinct count = 2 ≤ 2 ✓, stop shrinking

Window: [2, 3]
maxFruits = max(2, 2-1+1) = 2

left = 1, maxFruits = 2


Step 4: right = 3, fruit = 2
═══════════════════════════════════════════════════════════════════
Add fruit 2: basket = {2:2, 3:1}
Distinct count = 2 ≤ 2 ✓

Window: [2, 3, 2]
maxFruits = max(2, 3-1+1) = 3

left = 1, maxFruits = 3


Step 5: right = 4, fruit = 2
═══════════════════════════════════════════════════════════════════
Add fruit 2: basket = {2:3, 3:1}
Distinct count = 2 ≤ 2 ✓

Window: [2, 3, 2, 2]
maxFruits = max(3, 4-1+1) = 4

left = 1, maxFruits = 4


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 4
═══════════════════════════════════════════════════════════════════

Another Example: fruits = [0, 1, 2, 2]

Step 1: [0] → {0:1}, distinct = 1, max = 1
Step 2: [0, 1] → {0:1, 1:1}, distinct = 2, max = 2
Step 3: [0, 1, 2] → {0:1, 1:1, 2:1}, distinct = 3 ✗
        Shrink: [1, 2] → {1:1, 2:1}, distinct = 2, max = 2
Step 4: [1, 2, 2] → {1:1, 2:2}, distinct = 2, max = 3

Result: 3

---

🔍 Edge Cases

Case 1: All same fruit
Input: fruits = [1,1,1,1,1]
Output: 5
Explanation: Only one type, can pick all

Case 2: Two fruit types
Input: fruits = [1,2,1,2,1,2]
Output: 6
Explanation: Only two types, can pick all

Case 3: Single fruit
Input: fruits = [3]
Output: 1

Case 4: All different fruits
Input: fruits = [1,2,3,4,5]
Output: 2
Explanation: Can only pick 2 consecutive

Case 5: Three types, last two dominate
Input: fruits = [1,2,3,3,3]
Output: 4
Explanation: [2,3,3,3]

Case 6: Alternating with extra
Input: fruits = [0,1,0,1,2]
Output: 4
Explanation: [0,1,0,1]

Case 7: Long sequence of one type
Input: fruits = [1,1,1,2,2,2]
Output: 6
Explanation: All fruits (only 2 types)

Case 8: Complex pattern
Input: fruits = [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: [1,2,1,1,2]

---

Common Mistakes

Mistake 1: Not removing fruit type when count becomes 0
❌ Wrong: 
    basket.put(leftFruit, basket.get(leftFruit) - 1);
    // Forgot to remove when count = 0
✓ Right: 
    basket.put(leftFruit, basket.get(leftFruit) - 1);
    if (basket.get(leftFruit) == 0) {
        basket.remove(leftFruit);
    }
Reason: HashMap size must equal distinct count

Mistake 2: Using if instead of while for shrinking
❌ Wrong: 
    if (basket.size() > 2) {
        // Remove once
    }
✓ Right: 
    while (basket.size() > 2) {
        // Keep removing until valid
    }
Reason: May need to remove multiple fruits

Mistake 3: Updating maxFruits inside while loop
❌ Wrong: 
    while (basket.size() > 2) {
        maxFruits = Math.max(maxFruits, right - left + 1);
        // shrink...
    }
✓ Right: 
    while (basket.size() > 2) {
        // shrink...
    }
    maxFruits = Math.max(maxFruits, right - left + 1);
Reason: Update only when window is valid

Mistake 4: Using array instead of HashMap for large fruit values
❌ Wrong: 
    int[] count = new int[100000];  // Wasteful if fruits[i] is large
✓ Right: 
    Map<Integer, Integer> basket = new HashMap<>();
Reason: HashMap is more space-efficient

Mistake 5: Not understanding this is k=2 problem
❌ Wrong: 
    // Implementing custom logic instead of recognizing pattern
✓ Right: 
    // Recognize: "At Most K Distinct" with k = 2
Reason: Pattern recognition saves time

Mistake 6: Treating it as a different problem
❌ Wrong: 
    // Complex logic specific to "baskets" and "fruits"
✓ Right: 
    // Same as "Longest Substring with At Most 2 Distinct"
Reason: It's the exact same algorithm!

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

Approach 2: Sliding Window + HashMap (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Optimal solution, best for interviews

🔑 The Core Insight

Problem Translation:
"Fruit Into Baskets" = "Longest Substring with At Most 2 Distinct"

Mapping:
- Fruit types → Characters/Elements
- Two baskets → At most 2 distinct
- Maximum fruits → Length of longest subarray

This is EXACTLY Problem #37 with k = 2!

Same Algorithm:
1. Use HashMap to track element → frequency
2. HashMap.size() = number of distinct elements
3. Expand window (right++)
4. Shrink while distinct > 2
5. Track maximum length

Template (k = 2):
═══════════════════════════════════════════════════════════════

Map<Integer, Integer> window = new HashMap<>();
int left = 0, maxLen = 0;

for (int right = 0; right < n; right++) {
    // Expand: add right element
    window.put(arr[right], window.getOrDefault(arr[right], 0) + 1);

    // Shrink: while distinct > 2
    while (window.size() > 2) {
        window.put(arr[left], window.get(arr[left]) - 1);
        if (window.get(arr[left]) == 0) {
            window.remove(arr[left]);
        }
        left++;
    }

    // Update max
    maxLen = Math.max(maxLen, right - left + 1);
}

return maxLen;

🎯 Pattern Recognition

Problem Type: Longest Subarray with Constraint
Core Pattern: Variable-Size Sliding Window + HashMap

When to Apply:
✓ Finding longest subarray/substring
✓ "At most K distinct" constraint
✓ Contiguous elements required
✓ Want O(n) time complexity

Recognition Keywords:
- "Two baskets" → k = 2
- "Collect maximum" → Find longest
- "Must pick from every tree" → Contiguous
- "Single type per basket" → Distinct constraint

This Problem is Disguised:
- Fruit trees → Array elements
- Fruit types → Distinct values
- Baskets → Distinct limit (k = 2)
- Picking fruits → Subarray length

Related Problems:
- Longest Substring with At Most K Distinct Characters (LC 340) - k variable
- Longest Substring with At Most Two Distinct Characters (LC 159) - k = 2
- Subarrays with K Different Integers (LC 992)

🧠 Interview Strategy

Step 1: "Two baskets, each holds one type"
Step 2: "This is 'at most 2 distinct elements' problem!"
Step 3: "Same as LC 340 with k = 2"
Step 4: "Use sliding window with HashMap"
Step 5: "Expand always, shrink when distinct > 2"
Step 6: "O(n) time, O(1) space"

Key Points to Mention:
- Recognize pattern: "At most K distinct" with k = 2
- Variable-size sliding window
- HashMap for frequency tracking
- HashMap.size() gives distinct count
- Shrink while distinct > 2
- Remove from map when frequency = 0
- Update maxLen after shrinking
- O(n) time, each element visited twice max
- O(1) space (HashMap stores at most 3 elements)

Pattern Recognition:
"I recognize this as the 'Longest Substring with 
At Most K Distinct' problem with k = 2.
The fruit types are like characters, and the two
baskets limit us to 2 distinct types."

This shows strong pattern recognition! 🏆

---

📝 Quick Revision Notes

🎯 Core Concept:

"Fruit Into Baskets" = "At Most 2 Distinct Elements". Use variable-size sliding window with HashMap. Expand always, shrink while distinct > 2.

⚡ Quick Implementation:

import java.util.HashMap;

class Test {
  public int totalFruit(int[] a) {
    int res = 0;
    int left = 0;
    int right = 0;
    int len = a.length;
    HashMap<Integer, Integer> map = new HashMap<>();

    while (right < len) {
      // put incoming number in map
      map.put(a[right], map.getOrDefault(a[right], 0) + 1);

      if (map.size() <= 2) {
        res = Math.max(res, right - left + 1);
      } else {
        // shrink the window till map comes to size = 2
        while (left <= right && map.size() > 2) {
          // update map and res
          map.put(a[left], map.get(a[left]) - 1);
          if (map.get(a[left]) == 0) {
            map.remove(a[left]);
          }

          left++;

          if (map.size() <= 2) {
            res = Math.max(res, right - left + 1);
          }
        }
      }

      right++;
    }

    return res;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.totalFruit(new int[] { 1, 2, 3, 2, 2 }));
    System.out.println(t.totalFruit(new int[] { 1, 2, 1 }));
    System.out.println(t.totalFruit(new int[] { 0, 1, 2, 2 }));
  }
}

🔑 Key Insights:

• Problem translation: Two baskets → at most 2 distinct
• HashMap: fruit type → count in window
• Distinct count: HashMap.size()
• Expand: Always add right fruit
• Shrink: While basket.size() > 2
• Remove from map: When count becomes 0
• Update maxFruits: After shrinking (when valid)
• Time: O(n) - each fruit visited at most twice
• Space: O(1) - HashMap stores at most 3 types
• Same as: LC 340 (k distinct) with k = 2

🎪 Memory Aid:

"Two BASKETS = Two DISTINCT! Shrink when OVER 2!"
Think: "It's just 'At Most K Distinct' with k = 2!"

💡 Pattern Recognition:

Keywords that indicate "At Most K Distinct":
- "Two baskets" → k = 2
- "Each basket holds one type" → distinct constraint
- "Maximum fruits" → longest subarray
- "Pick from every tree" → contiguous

Recognize this pattern instantly in interviews!

---

Related Patterns

• Longest Substring with At Most K Distinct Characters (LC 340)
• Longest Substring with At Most Two Distinct Characters (LC 159)
• Longest Substring Without Repeating Characters (LC 3)
• Subarrays with K Different Integers (LC 992)

---

Happy practicing! 🎯