Problem Description

You're visiting a farm with fruit trees arranged in a single row from left to right. Each tree produces a specific type of fruit, represented by an integer array fruits where fruits[i] indicates the fruit type of the i-th tree.

You want to collect the maximum amount of fruit possible, but you must follow these rules:

1. Two baskets only: You have exactly two baskets, and each basket can hold only one type of fruit (but unlimited quantity of that type).

2. Sequential picking: Starting from any tree of your choice, you must pick exactly one fruit from every consecutive tree while moving to the right. You cannot skip trees.

3. Stopping condition: You must stop picking when you encounter a tree with a fruit type that cannot fit in either of your baskets (i.e., it would be a third type of fruit).

The goal is to find the maximum number of fruits you can collect by choosing the optimal starting position and picking fruits consecutively until you're forced to stop.

Example visualization:

• If fruits = [1, 2, 3, 2, 2, 1, 4]
• Starting from index 1: You could pick fruits [2, 3, 2, 2] (types 2 and 3) = 4 fruits
• Starting from index 3: You could pick fruits [2, 2, 1] (types 2 and 1) = 3 fruits
• The maximum would be 4 fruits

The problem essentially asks for the length of the longest contiguous subarray that contains at most 2 distinct values.

Intuition

The key insight is recognizing that we're looking for the longest contiguous subarray containing at most 2 distinct values. Since we must pick fruits consecutively without skipping, this becomes a classic sliding window problem.

Think about it this way: imagine you're walking along the row of trees with your two baskets. As you walk, you keep expanding your picking range to the right by including more trees. But when you encounter a third type of fruit, you need to adjust your starting position (move it forward) until you're back to having only 2 types.

The sliding window technique naturally fits this scenario:

• The window represents the range of trees we're currently picking from
• We expand the window by moving the right boundary (i) forward as we include each new tree
• When we have more than 2 fruit types, we shrink the window from the left by moving j forward

Why does this work? Because:

1. We want to maximize the window size (number of fruits collected)
2. The window must satisfy the constraint (at most 2 fruit types)
3. By sliding the window through all possible positions, we're guaranteed to find the optimal range

The hash table cnt acts as our "basket tracker" - it tells us which fruit types are currently in our baskets and how many of each we have. When len(cnt) > 2, we know we've encountered a third fruit type and need to drop fruits from the left side of our window until we're back to 2 types.

This approach is efficient because each tree is visited at most twice (once by the right pointer, once by the left pointer), giving us O(n) time complexity.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window solution using two pointers and a hash table to track fruit types in our current window.

Data Structures Used:

• cnt: A Counter (hash table) to store fruit types and their counts in the current window
• j: Left pointer of the sliding window
• i: Right pointer of the sliding window (implicit in the enumeration)
• ans: Variable to track the maximum window size found

Algorithm Steps:

1. Initialize variables:

   • Create an empty Counter cnt to track fruit types
   • Set ans = 0 for the maximum result and j = 0 for the left boundary

2. Expand the window (right pointer):

   • Iterate through the array with enumerate(fruits) where i is the index and x is the fruit type
   • Add each fruit to the window: cnt[x] += 1

3. Shrink the window when needed (left pointer):

   • While we have more than 2 fruit types (len(cnt) > 2):
     • Get the fruit at the left boundary: y = fruits[j]
     • Decrease its count: cnt[y] -= 1
     • If count reaches 0, remove this fruit type completely: cnt.pop(y)
     • Move left boundary forward: j += 1

4. Update the maximum:

   • After ensuring the window is valid (≤ 2 fruit types), calculate current window size: i - j + 1
   • Update the answer: ans = max(ans, i - j + 1)

Example Walkthrough with fruits = [1, 2, 3, 2, 2, 1, 4]:

• Initially: j=0, i=0, cnt={1:1}, window = [1], size = 1
• i=1: cnt={1:1, 2:1}, window = [1,2], size = 2
• i=2: cnt={1:1, 2:1, 3:1} → 3 types! Shrink: remove fruit at j=0, now cnt={2:1, 3:1}, j=1, window = [2,3], size = 2
• i=3: cnt={2:2, 3:1}, window = [2,3,2], size = 3
• i=4: cnt={2:3, 3:1}, window = [2,3,2,2], size = 4
• i=5: cnt={2:3, 3:1, 1:1} → 3 types! Shrink: remove fruits at j=1,2, now cnt={2:2, 1:1}, j=3, window = [2,2,1], size = 3
• i=6: cnt={2:2, 1:1, 4:1} → 3 types! Shrink until valid

The maximum window size found is 4, which corresponds to picking fruits [2,3,2,2].

Example Walkthrough

Let's walk through a simple example with fruits = [3, 3, 1, 1, 2, 2, 1] to illustrate the sliding window approach.

Initial Setup:

• Two pointers: j = 0 (left), i will iterate from 0 to 6 (right)
• Counter cnt = {} to track fruit types in current window
• Maximum answer ans = 0

Step-by-step execution:

i = 0 (fruit = 3):

• Add fruit 3: cnt = {3: 1}
• Window: [3], only 1 fruit type ✓
• Window size: 0 - 0 + 1 = 1
• Update: ans = max(0, 1) = 1

i = 1 (fruit = 3):

• Add fruit 3: cnt = {3: 2}
• Window: [3, 3], only 1 fruit type ✓
• Window size: 1 - 0 + 1 = 2
• Update: ans = max(1, 2) = 2

i = 2 (fruit = 1):

• Add fruit 1: cnt = {3: 2, 1: 1}
• Window: [3, 3, 1], 2 fruit types ✓
• Window size: 2 - 0 + 1 = 3
• Update: ans = max(2, 3) = 3

i = 3 (fruit = 1):

• Add fruit 1: cnt = {3: 2, 1: 2}
• Window: [3, 3, 1, 1], 2 fruit types ✓
• Window size: 3 - 0 + 1 = 4
• Update: ans = max(3, 4) = 4

i = 4 (fruit = 2):

• Add fruit 2: cnt = {3: 2, 1: 2, 2: 1}
• Window has 3 fruit types! Need to shrink from left.
• Shrinking phase:
  • Remove fruits[0] = 3: cnt = {3: 1, 1: 2, 2: 1}, j = 1
  • Remove fruits[1] = 3: cnt = {1: 2, 2: 1} (3 removed as count = 0), j = 2
• Now window: [1, 1, 2], 2 fruit types ✓
• Window size: 4 - 2 + 1 = 3
• Update: ans = max(4, 3) = 4

i = 5 (fruit = 2):

• Add fruit 2: cnt = {1: 2, 2: 2}
• Window: [1, 1, 2, 2], 2 fruit types ✓
• Window size: 5 - 2 + 1 = 4
• Update: ans = max(4, 4) = 4

i = 6 (fruit = 1):

• Add fruit 1: cnt = {1: 3, 2: 2}
• Window: [1, 1, 2, 2, 1], 2 fruit types ✓
• Window size: 6 - 2 + 1 = 5
• Update: ans = max(4, 5) = 5

Result: Maximum fruits collected = 5 (the subarray [1, 1, 2, 2, 1] from indices 2 to 6)

The algorithm efficiently finds the longest contiguous subarray with at most 2 distinct fruit types by expanding the window when possible and shrinking it only when necessary to maintain the constraint.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the fruits array.

The algorithm uses a sliding window approach with two pointers (i and j). The outer loop iterates through each element exactly once with pointer i, contributing O(n) operations. The inner while loop moves pointer j forward, but critically, j can only move from position 0 to position n-1 throughout the entire execution of the algorithm. Each element is visited at most twice - once by pointer i and once by pointer j. Therefore, despite the nested loop structure, the total number of operations is bounded by 2n, which simplifies to O(n).

Space Complexity: O(1)

The algorithm uses a Counter (hash map) to store the frequency of fruit types in the current window. Since the problem constraint is to maintain at most 2 different fruit types in the window (the while loop ensures len(cnt) > 2 never persists), the Counter will contain at most 3 entries at any point (momentarily 3 before reducing back to 2). This means the space used by the Counter is constant and independent of the input size n. The remaining variables (ans, i, j, x, y) all use constant space. Therefore, the overall space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Properly Handling Counter Cleanup

The Pitfall: A common mistake is forgetting to remove fruit types from the counter when their count reaches zero. Simply decrementing the count without removing zero-count entries leads to incorrect window validation.

Incorrect Implementation:

# WRONG: Just decrementing without cleanup
while len(fruit_count) > 2:
    fruit_count[fruits[left]] -= 1
    left += 1
    # Missing: removal of zero-count entries!

This causes len(fruit_count) to still count fruit types with 0 occurrences, making the algorithm incorrectly think there are still 3+ fruit types in the window.

Correct Solution:

while len(fruit_count) > 2:
    left_fruit = fruits[left]
    fruit_count[left_fruit] -= 1
  
    # Critical: Remove the fruit type when count reaches 0
    if fruit_count[left_fruit] == 0:
        del fruit_count[left_fruit]
  
    left += 1

2. Off-by-One Error in Window Size Calculation

The Pitfall: Calculating the window size as right - left instead of right - left + 1.

Incorrect:

# WRONG: Missing the +1
max_fruits = max(max_fruits, right - left)

For a window from index 2 to 5, the size should be 4 (indices 2,3,4,5), but 5-2=3 gives the wrong answer.

Correct Solution:

# Correct: Include both endpoints
max_fruits = max(max_fruits, right - left + 1)

3. Using Regular Dictionary Instead of Counter

The Pitfall: Using a regular dictionary without proper initialization can cause KeyError when incrementing counts.

Incorrect:

# WRONG: Will raise KeyError
fruit_count = {}
for right, fruit_type in enumerate(fruits):
    fruit_count[fruit_type] += 1  # KeyError if fruit_type not in dict

Correct Solutions:

# Option 1: Use Counter (recommended)
from collections import Counter
fruit_count = Counter()

# Option 2: Use defaultdict
from collections import defaultdict
fruit_count = defaultdict(int)

# Option 3: Check existence before incrementing
fruit_count = {}
fruit_count[fruit_type] = fruit_count.get(fruit_type, 0) + 1