Log inSign up
mediumLeetCodeNot Started

Fruit Into Baskets

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 fruits where fruits[i] is the type of fruit the i-th 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. There is no limit on the amount of fruit each basket can hold. - 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. The picked fruits must fit in one of your baskets. - Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees [1,2,1] with types 1 and 2.

Example 2:

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2] (length 3). If we started at tree 0, we could only pick [0,1] (length 2).

Example 3:

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2] (length 4). If we started at tree 0, we would only pick [1,2] (length 2).

Constraints:

  • 1 <= fruits.length <= 105
  • 0 <= fruits[i] < fruits.length

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window & Two Pointers technique
  • Hash Map frequency tracking
  • Subarray length calculations — right - left + 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate real-world story problems into formal sliding window constraints (At Most K Distinct Elements).
  • Master dynamic frequency hash map updates inside a two-pointer sliding window.
  • Understand why hash map space is strictly O(1) when key count is bounded by 3.
  • Differentiate standard shrinking window from the non-shrinking sliding window optimization.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Longest contiguous subarray with at most K distinct elements (here K = 2).
  • Contiguous picking rule ("from every tree moving right").
  • Dynamic frequency map tracking distinct keys.

Algorithmic Decision Tree:

  • If checking all subarrays -> O(N2) brute force (times out).
  • If finding longest contiguous window with at most K distinct elements -> Sliding Window (Two Pointers) in O(N).
  • Since K = 2 is fixed, Hash Map size <= 3, yielding strict O(1) auxiliary space.

Connected Patterns:

Longest Substring with At Most K Distinct CharactersSubarrays with K Different IntegersLongest Substring Without Repeating Characters

1. Brute Force (All Subarrays with Set)

Intuition

Try every possible start tree i. For each start tree, pick fruits sequentially with tree j, adding fruit types to a set. As soon as the set contains > 2 types, break and record length j - i.

Algorithm

  1. Step 1: Initialize maxFruits = 0.
  2. Step 2: Loop i from 0 to n - 1:
  3. - Create set distinct.
  4. - Loop j from i to n - 1:
  5. - Add fruits[j] to distinct.
  6. - If distinct.size() > 2, break.
  7. - maxFruits = max(maxFruits, j - i + 1).
  8. Step 3: Return maxFruits.

Brute Force (All Subarrays with Set) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 7, 11, 15, 1, 8]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
2
7
11
15
1
8
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
2
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=2. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <algorithm>
5
6class Solution {
7public:
8 int totalFruit(std::vector<int>& fruits) {
9 int n = fruits.size();
10 int maxFruits = 0;
11
12 for (int i = 0; i < n; i++) {
13 std::unordered_set<int> distinct;
14 for (int j = i; j < n; j++) {
15 distinct.insert(fruits[j]);
16 if (distinct.size() > 2) {
17 break;
18 }
19 maxFruits = std::max(maxFruits, j - i + 1);
20 }
21 }
22 return maxFruits;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::vector<int> fruits = {1, 2, 3, 2, 2};
29 std::cout << "Max Fruits: " << sol.totalFruit(fruits) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (All Subarrays with Set).
  • Space complexity: O(1) — Space complexity for Brute Force (All Subarrays with Set).

Why Brute Force Doesn't Scale:

For N = 100,000 trees, checking every subarray takes 1010 operations (over 10 seconds). Sliding window processes each tree at most twice (one enter, one exit), taking ~200,000 operations (< 10 ms).

For N = 100,000: Brute force takes ~10 billion operations; Sliding window completes in ~200,000 operations (~50,000x speedup).

2. Better (Standard Sliding Window with Shrink While Loop)

Intuition

Two pointers left and right define the window. Expand right, adding fruit to the map. When map.size > 2, shrink left and decrement frequencies, removing keys when count hits 0. Update maxFruits at each step.

Algorithm

  1. Step 1: Initialize left = 0, maxFruits = 0, and frequency map count.
  2. Step 2: For each right from 0 to n - 1:
  3. - Increment count[fruits[right]].
  4. - While count.size() > 2:
  5. - Decrement count[fruits[left]].
  6. - If count[fruits[left]] == 0, erase fruits[left] from map.
  7. - Increment left.
  8. - maxFruits = max(maxFruits, right - left + 1).
  9. Step 3: Return maxFruits.

Standard Sliding Window on [1, 2, 3, 2, 2]

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [fruits = [1, 2, 3, 2, 2]]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
fruits = [1, 2, 3, 2, 2]
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
fruits = [1, 2, 3, 2, 2]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
6class Solution {
7public:
8 int totalFruit(std::vector<int>& fruits) {
9 std::unordered_map<int, int> count;
10 int left = 0;
11 int maxFruits = 0;
12
13 for (int right = 0; right < (int)fruits.size(); right++) {
14 count[fruits[right]]++;
15
16 while (count.size() > 2) {
17 count[fruits[left]]--;
18 if (count[fruits[left]] == 0) {
19 count.erase(fruits[left]);
20 }
21 left++;
22 }
23 maxFruits = std::max(maxFruits, right - left + 1);
24 }
25 return maxFruits;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<int> fruits = {1, 2, 3, 2, 2};
32 std::cout << "Better Max Fruits: " << sol.totalFruit(fruits) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Standard Sliding Window with Shrink While Loop).
  • Space complexity: O(N) — Space complexity for Better (Standard Sliding Window with Shrink While Loop).

3. Optimal (Non-Shrinking Lazy Sliding Window)

Intuition

Since we only care about the MAXIMUM window length, we never need to shrink the window size. When an invalid fruit enters, we simply shift the entire window one step to the right by incrementing left by 1 and decrementing count[fruits[left]]. The final answer is simply fruits.length - left.

Algorithm

  1. Step 1: Initialize left = 0 and frequency map count.
  2. Step 2: Loop right from 0 to fruits.length - 1:
  3. - Increment count[fruits[right]].
  4. - If count.size() > 2:
  5. - Decrement count[fruits[left]].
  6. - If count[fruits[left]] == 0, erase from map.
  7. - Increment left.
  8. Step 3: Return fruits.length - left.

Non-Shrinking Window on [1, 2, 3, 2, 2]

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [fruits = [1, 2, 3, 2, 2]]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
fruits = [1, 2, 3, 2, 2]
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
fruits = [1, 2, 3, 2, 2]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7 int totalFruit(std::vector<int>& fruits) {
8 std::unordered_map<int, int> count;
9 int left = 0;
10 int n = fruits.size();
11
12 for (int right = 0; right < n; right++) {
13 count[fruits[right]]++;
14
15 if (count.size() > 2) {
16 count[fruits[left]]--;
17 if (count[fruits[left]] == 0) {
18 count.erase(fruits[left]);
19 }
20 left++;
21 }
22 }
23 return n - left;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::vector<int> fruits = {1, 2, 3, 2, 2};
30 std::cout << "Optimal Max Fruits: " << sol.totalFruit(fruits) << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (Non-Shrinking Lazy Sliding Window).
  • Space complexity: O(1) — Space complexity for Optimal (Non-Shrinking Lazy Sliding Window).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (All Subarrays with Set)O(N^2)O(1)For each starting tree i, iterate j and add to set. Stop when set size > 2. Track maximum length.Nested iteration over all O(N2) subarrays.
2.Better (Standard Sliding Window with Shrink While Loop)O(N)O(1)Expand right pointer. When distinct types > 2, while loop shrinks left pointer until distinct types == 2.Pointer movement.
3.Optimal (Non-Shrinking Lazy Sliding Window)OptimalO(N)O(1)Window only expands or shifts right by 1 when invalid. Never shrinks, ending with window size = max length.Single pass scan bound.

Common Pitfalls & Crucial Edge Cases

Not deleting fruit key from map when count reaches 0

In Python/JS/Java, if count[fruit] == 0 is left in the map, map.size() or len(count) still counts it as a distinct type.

Assuming fruit types are always 0, 1, or 2

Fruit types can be arbitrary large integers (fruits[i] <= 10^5), so direct array indexing without careful size allocation will cause buffer out of bounds. Use a hash map.

Resetting window to index `i + 1` instead of sliding

Resetting back to start destroys the linear O(N) complexity.

Crucial Edge Cases to Validate:

  • All trees produce the same fruit type (fruits = [1, 1, 1, 1]): Map size stays 1; returns entire length n.
  • Only 2 distinct fruit types in total (fruits = [1, 2, 1, 2]): Map size never exceeds 2; returns n.
  • Every single tree has a different fruit type (fruits = [1, 2, 3, 4, 5]): Window size stays 2 throughout, returns 2.
  • Single tree (fruits = [0]): Returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Immediately state the rephrased problem: "This is the classic Longest Subarray with at Most K Distinct Elements where K = 2."
  2. Explain the importance of deleting the key from the map when its frequency drops to 0 (otherwise map.size() remains 3).
  3. Mention the non-shrinking sliding window optimization as a bonus to demonstrate deep mastery of two-pointer mechanics.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the abstract data structure problem that Fruit Into Baskets directly maps to?

2.Why is the space complexity of the hash map in the optimal sliding window O(1)?

3.In the non-shrinking sliding window variant, why does fruits.length - left give the correct maximum window length at the end?

Back to DSA Sheet