How do you solve Fruit Into Baskets?

Use two pointers to represent a window. For each right index, add `fruits[r]` to `freq`. If the number of distinct keys becomes greater than two, advance `l` while decrementing counts and deleting any key whose count becomes zero. After shrinking, the window is valid again, so update the maximum length. After adding `fruits[r]`, the distinct count can increase by at most one, so it can reach 3 momentarily before shrinking restores it to 2.

What pattern does Fruit Into Baskets use?

The Pattern: Sliding Window (Variable Size with Frequency Map) The Heuristic: Maintain a window that satisfies the problem's constraints by expanding the right pointer and contracting the left pointer only when the constraint is violated, using a frequency map to track distinct elements efficiently.

Fruit Into Baskets — Sliding Window

Q: What is the time complexity of Fruit Into Baskets?

O(n). Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.

Problem

Given an integer array fruits where fruits[i] represents the type of fruit on the ith tree, return the maximum number of fruits you can collect in two baskets such that each basket can only hold one type of fruit and you must pick fruits from consecutive trees.

1 ≤ fruits.length ≤ 10⁵
0 ≤ fruits[i] < fruits.length

Example

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

Output: 4

We want the longest contiguous subarray that contains at most two distinct fruit types. We initialize the sliding window with `l = 0`, an empty frequency map `freq = {}`, and `res = 0`. When `r = 0`, we add fruit `1`, so `freq = {1: 1}`. The window is valid because it contains at most two types, so we update `res = 1`. When `r = 1`, we add fruit `2`, so `freq = {1: 1, 2: 1}`. The window is still valid, so we update `res = 2`. When `r = 2`, we add fruit `3`, so `freq = {1: 1, 2: 1, 3: 1}`. The window is now invalid because it contains three distinct types, so we must shrink from the left. We remove `fruits[l] = 1` by decrementing its count to zero and deleting it, which makes `freq = {2: 1, 3: 1}` and advances `l` to `1`. The window is valid again because it contains only types `2` and `3`. When `r = 3`, we add fruit `2`, so `freq = {2: 2, 3: 1}`. The window remains valid, its length is `r - l + 1 = 3`, and we update `res = 3`. When `r = 4`, we add fruit `2`, so `freq = {2: 3, 3: 1}`. The window remains valid, its length is `r - l + 1 = 4`, and we update `res = 4`. The key idea is that we only move `l` when a third type appears. We shrink until one fruit type fully exits the window (its count becomes zero and is removed from `freq`), and then we continue expanding to maximize the window length.

Approach

Straightforward Solution

A brute-force approach would check all subarrays and count distinct elements, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

The problem reduces to finding the longest contiguous subarray with at most two distinct elements. This is a classic sliding window problem where the window expands to include new elements and contracts when the constraint is violated.

Path to Optimal

Preview

Recognizing the problem as a sliding window with a constraint on distinct elements allows a linear time solution…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers to represent a window. For each right index, add `fruits[r]` to `freq`…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.

Space

O(1)

The frequency map stores counts of fruit types in the current window. Since the problem restricts to at most two types, the map size is bounded by a small constant, resulting in constant auxiliary space.

Solution

Python

1class Solution:
  def totalFruit(self, fruits):
      l = 0
      res = 0
      freq = {}
6
      for r in range(len(fruits)):
          rf = fruits[r]
          freq[rf] = freq.get(rf, 0) + 1
10
          while len(freq) > 2:
              lf = fruits[l]
              freq[lf] -= 1
              if freq[lf] == 0:
                  del freq[lf]
              l += 1
17
          res = max(res, r - l + 1)
19
      return res

Step-by-Step Solution

1

Initialize Sliding Window State

3l = 0
4res = 0
5freq = {}

Objective

To initialize the variables that define the sliding window and store the current window state.

Key Insight

The algorithm maintains a window `[l..r]` and a frequency map `freq` that counts how many of each fruit type are currently inside the window. The variable `res` stores the best valid window length seen so far.

Interview Quick-Check

Core Logic

Set `l = 0`, `res = 0`, and `freq = {}` to define the initial window boundary and prepare the frequency map used to enforce the two-type constraint.

State & Boundaries

Initialize `l` at the start of the array so the window can expand correctly as `r` advances.

Common Pitfalls & Bugs

If `freq` is not reset correctly, the window state becomes inconsistent and the distinct-type check will be incorrect.

2

Expand Window and Track Fruit Frequencies

To iterate through the fruits array, expanding the window by moving the right pointer and updating the frequency map of fruit types.

3

Contract Window to Maintain Two-Type Constraint

To shrink the window from the left when more than two distinct fruit types are present, restoring the constraint.

4

Update Maximum Window Size

To track and update the maximum length of a valid window throughout the iteration.

5

Return the Maximum Number of Fruits Collected

To return the maximum length of a valid window found, representing the maximum fruits collected.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 9 Critical

freq[rf] = freq.get(rf, 0) + 1

Increment the count of the current fruit in the frequency map.

This line is critical because it updates the frequency map to reflect the current window's contents, enabling the algorithm to detect when the window violates the two-type constraint.

Line 13 Critical

freq[lf] -= 1

Decrement the count of the fruit at the left pointer in the frequency map.

This decrement is essential to accurately track the window's fruit composition during contraction, ensuring the frequency map correctly represents the current window.

Line 14 Critical

if freq[lf] == 0:

Check whether the left fruit’s frequency has reached zero so the type can be removed from the map.

This check detects when the left fruit type has fully left the window, which is the condition needed to remove its key and keep `len(freq)` accurate.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why does the algorithm contract the window from the left only when the number of distinct fruit types exceeds two?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Fruit Into Baskets from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Fruit Into Baskets drill

or drill a free problem

1	`class Solution:`
2	`def totalFruit(self, fruits):`
3	`l = 0`
4	`res = 0`
5	`freq = {}`
6
7	`for r in range(len(fruits)):`
8	`rf = fruits[r]`
9	`freq[rf] = freq.get(rf, 0) + 1`
10
11	`while len(freq) > 2:`
12	`lf = fruits[l]`
13	`freq[lf] -= 1`
14	`if freq[lf] == 0:`
15	`del freq[lf]`
16	`l += 1`
17
18	`res = max(res, r - l + 1)`
19
20	`return res`