Pattern this teaches:Sliding Window
Fruit Into Baskets
A medium Sliding Window interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sliding Window
- Sheets
- 1
- Core for
- 6 roles
The problem
Given an array representing types of fruits on a tree, find the maximum number of fruits you can collect using two baskets, each holding only one type of fruit.
Example 1
- Input
- fruits = [3,4,3]
- Output
- 3
- Why
- Only two kinds of fruit, so every tree can be picked.
Example 2
- Input
- fruits = [5,6,7,7]
- Output
- 3
- Why
- Starting at the 6, the baskets hold 6 and 7: three trees.
Constraints
- 1 <= fruits.length <= 10^5
- 0 <= fruits[i] < fruits.length
How to think about it
Updated 2026-09-29The collection rule requires any valid harvest to be a contiguous slice containing at most two distinct values. Moving the right boundary grows the variety, and whenever a third variety appears, only sliding the left boundary forward can eliminate one of the earlier types.
Approaches, worst first
Exhaustive subarray scan
time O(n^2) · space O(1)
For each starting tree, step forward while tracking distinct fruit types in a set, stopping when a third type is reached. Re-traverses identical segments repeatedly.
Two-pointer frequency mapWrite this one
time O(n) · space O(1)
Expand right while inserting fruit types into a frequency map. When the map holds more than two distinct keys, decrement counts from left and remove keys that reach zero before maximizing length.
Where people lose marks · 3
- Failing to delete the key from the map when its frequency drops to zero leaves the map size stuck above two.
- Assuming fruit types are only digits 0, 1, or 2; types can be any integer up to the length of the array, requiring a map or large count array.
- Resetting the left pointer back to the right pointer instead of advancing it gradually discards valid sequences that share the most recent fruit type.
The theory behind it
Sliding Window — the ground this problem stands on. All Sliding Window problems
What Sliding Window is
A sliding window is an adjustable magnifying lens placed over a continuous segment of a sequence. Rather than recalculating metrics for every potential subsection from scratch, the window expands rightward by absorbing fresh elements and contracts leftward to expel stale entries. Only data currently framed within the window borders contributes to the active calculation.
When to reach for it
Reach for a sliding window when a question asks for the longest, shortest, or optimal contiguous subarray or substring matching a constraint. Key signals include fixed window sizes like maximum sum across k consecutive values, or dynamic criteria like finding the shortest substring holding all target characters. If the target subset must form an unbroken continuous run, window mechanics replace repetitive segment rescanning.
How the pattern works
Maintain two boundary indices, left and right, defining the active interval alongside a running state accumulator. In each step, expand the right boundary to incorporate the incoming element into state totals. When current state violates the designated problem constraints, increment the left boundary while deducting departing values until validity is restored. Update your tracking metric, whether minimum window length or maximum score, only during valid intervals.
More Sliding Window problems
Target Roles
Core requirement for 6 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .