Introduction

LeetCode 904: Fruit Into Baskets is a classic sliding window problem that tests your ability to track a limited number of distinct elements in a subarray.

The problem can be rephrased as:

Find the longest subarray containing at most 2 distinct types of elements.

This is a great example of using HashMap + sliding window to efficiently track counts of elements while expanding and shrinking the window.

If you’d like to try solving the problem first, you can attempt it here:

Try the problem on LeetCode:

https://leetcode.com/problems/fruit-into-baskets/

Problem Understanding

You are given:

1. An array fruits where fruits[i] represents the type of fruit from tree i
2. Two baskets, each can hold only one type of fruit

Rules:

1. Start at any tree and move only to the right
2. Pick exactly one fruit from each tree while moving
3. Stop when a tree’s fruit cannot fit in your baskets

Goal: Return the maximum number of fruits you can pick.

Examples:

A naive approach would check all subarrays, count distinct fruits, and pick the max →

1. Time Complexity: O(n²) → too slow for fruits.length up to 10⁵

Key Idea: Sliding Window with At Most Two Types

Instead of brute-force:

1. Track the number of each fruit type in the current window using a HashMap
2. Use two pointers i and j for the window
3. Expand j by adding fruits[j] to the map
4. If the number of distinct types mp.size() exceeds 2:
5. Shrink the window from the left (i) until mp.size() <= 2
6. The window length j - i + 1 gives the max fruits collected so far

Intuition:

1. Only two baskets → window can contain at most 2 distinct fruits
2. The sliding window efficiently finds the longest subarray with ≤ 2 distinct elements

Approach (Step-by-Step)

1. Initialize i = 0, j = 0 for window pointers
2. Initialize HashMap mp to store fruit counts
3. Initialize co = 0 → maximum fruits collected
4. Iterate j over fruits:
5. Add fruits[j] to the map
6. Check mp.size():
7. If ≤ 2 → update co = max(co, j - i + 1)
8. If > 2 → shrink window from i until mp.size() <= 2
9. Continue expanding the window
10. Return co as the maximum fruits collected

Optimization:

1. HashMap keeps track of counts → no need to scan subarray repeatedly
2. Sliding window ensures linear traversal

Implementation (Java)

Dry Run Example

Input:

Execution:

Output:

Complexity Analysis

1. Time Complexity: O(n) → Each element is added and removed at most once
2. Space Complexity: O(1) → HashMap stores at most 2 types of fruits

Edge Cases Considered

1. Array with ≤ 2 types → entire array can be picked
2. Array with all same type → window length = array length
3. Zeros or non-continuous fruit types → handled by sliding window
4. Large arrays up to 10⁵ elements → O(n) solution works efficiently

Sliding Window Pattern Importance

This problem demonstrates the sliding window + frequency map pattern:

1. Track limited number of distinct elements
2. Expand/shrink window dynamically
3. Efficiently compute max subarray length with constraints

It’s directly related to problems like:

1. Max consecutive ones with flips
2. Longest substring with k distinct characters
3. Fruit collection / subarray problems with type limits

Conclusion

By tracking fruit counts with a HashMap in a sliding window, we efficiently find the maximum fruits collectible in O(n) time.

Mastering this pattern allows solving many array and string problems with constraints on distinct elements in a linear and elegant way.