Fruit Into Baskets

Explanation & Solution

Description

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 nums where nums[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:

You only have two baskets, and each basket can only hold a single type of fruit.
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. You must stop when you encounter a tree with a fruit type that cannot fit into either basket.

Return the maximum number of fruits you can pick.

Input:nums = [1,2,1]

Output: 3

Explanation: We can pick from all 3 trees. The two types are {1, 2}.

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] < nums.length

Approach

Sliding Window pattern

1. Initialize the Sliding Window

Create a Map called basket that maps fruit types to their count within the current window.
Set left = 0 as the start of the window and maxFruits = 0 to track the best result.

2. Expand the Window with the Right Pointer

Iterate right from 0 to nums.length - 1.
Add nums[right] into the basket map, incrementing its count.

3. Shrink When More Than 2 Types

While basket.size > 2, we have too many fruit types.
Remove one count of nums[left] from the basket. If its count reaches 0, delete the entry entirely.
Increment left to shrink the window.

4. Update the Maximum

After ensuring the window has at most 2 types, compute the window size right - left + 1.
Update maxFruits if this window is larger than the previous best.

5. Return the Result

After iterating through all trees, maxFruits holds the maximum number of fruits collectible with only two baskets.

🧠 Key Insight

This is a classic sliding window problem where we maintain a window with at most 2 distinct values. The Map efficiently tracks how many of each type are in the window, and we shrink from the left whenever a third type enters. Each element is added and removed at most once, giving us O(n) time and O(1) space (the map holds at most 3 entries at any time).

Visualization

Input:

[1, 2, 1]

—

Press ▶ or use ← → to step through

Left (L)Right (R)WindowDone

4 steps

Solution Code

Minimum Window Substring

Longest Substring with At Most Two Distinct Characters