Fruit Into Baskets

Medium
49.

Fruit Into Baskets

Fruit Into Baskets is a medium coding problem on arrays, hash table and sliding window.

You are visiting a row of fruit trees; fruits[i] is the type of fruit the i-th tree produces. You have two baskets, each holding only one type. Starting from any tree and moving right, you pick one fruit per tree until a tree forces a third type.

Return the maximum number of fruits you can pick.

Example 1

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

Example 2

Input
fruits = [0,1,2,2]
Output
3
Explanation
Pick from trees [1,2,2].

Example 3

Input
fruits = [1,2,3,2,2]
Output
4
Explanation
Pick from trees [2,3,2,2].

Constraints

  • 1 <= fruits.length <= 40
  • 0 <= fruits[i] <= 6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function(fruits) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Fruit Into Baskets — Solution in Python, Java & C++

Fruit Into Baskets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Fruit Into Baskets is a medium coding problem on arrays, hash table and sliding window.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Sliding Window
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are visiting a row of fruit trees; fruits[i] is the type of fruit the i-th tree produces. You have two baskets, each holding only one type. Starting from any tree and moving right, you pick one fruit per tree until a tree forces a third type.

Return the maximum number of fruits you can pick.

Example 1

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

Example 2

Input: fruits = [0,1,2,2]
Output: 3
Explanation: Pick from trees [1,2,2].

Example 3

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: Pick from trees [2,3,2,2].

Constraints

  • 1 <= fruits.length <= 40
  • 0 <= fruits[i] <= 6

Hints for Fruit Into Baskets

  1. Hint 1

    This is 'longest subarray with at most 2 distinct values' in disguise.

  2. Hint 2

    Track type counts in the window; shrink while there are 3 distinct types.

How to solve Fruit Into Baskets

Strip away the story and this is "longest contiguous subarray containing at most two distinct values". Two baskets means two allowed types; picking until a third appears means the window must stay within that limit. Slide a window, keeping a count per type, and shrink whenever a third type sneaks in.

Approach

  1. Keep a frequency table for the types inside the window plus a count of how many distinct types it holds.
  2. Advance the right edge; if the incoming type was absent, the distinct count grows.
  3. While the distinct count exceeds two, advance the left edge, decrementing that type's frequency and lowering the distinct count when it hits zero.
  4. Record the window length once the invariant holds again.
  5. The largest such window is the answer.

Why it works

Every valid picking run is a contiguous block with at most two types, and every such block is a valid run — so the two maxima coincide. The window only shrinks to restore the invariant, never speculatively, so for each right edge it holds the longest valid block ending there; taking the maximum over all right edges covers every candidate. Each index enters and leaves once, keeping it linear despite the inner loop.

Complexity

  • Time — O(n)
  • Space — O(1) — at most three types are ever tracked

Pitfalls

  • Decrement the distinct count only when a type's frequency actually reaches zero, not on every removal.
  • Measure the window after restoring the invariant, or you count runs that need three baskets.
  • You may start at any tree, which is exactly what makes this a subarray problem rather than a prefix one.
  • Fewer than two distinct types in the whole array is fine — the answer is then the entire array.

Reference solution

Python

from typing import List

def totalFruit(fruits: List[int]) -> int:
    count = {}
    l = 0
    best = 0
    for r, f in enumerate(fruits):
        count[f] = count.get(f, 0) + 1
        while len(count) > 2:
            g = fruits[l]
            count[g] -= 1
            if count[g] == 0:
                del count[g]
            l += 1
        best = max(best, r - l + 1)
    return best

Java

public static int totalFruit(int[] fruits) {
    int[] count = new int[64];
    int distinct = 0, l = 0, best = 0;
    for (int r = 0; r < fruits.length; r++) {
        if (count[fruits[r]] == 0) distinct++;
        count[fruits[r]]++;
        while (distinct > 2) {
            count[fruits[l]]--;
            if (count[fruits[l]] == 0) distinct--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

C++

int totalFruit(vector<int>& fruits) {
    vector<int> count(64, 0);
    int distinct = 0, l = 0, best = 0;
    for (int r = 0; r < (int) fruits.size(); r++) {
        if (count[fruits[r]] == 0) distinct++;
        count[fruits[r]]++;
        while (distinct > 2) {
            count[fruits[l]]--;
            if (count[fruits[l]] == 0) distinct--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

JavaScript

var totalFruit = function(fruits) {
    const count = new Map();
    let l = 0, best = 0;
    for (let r = 0; r < fruits.length; r++) {
        count.set(fruits[r], (count.get(fruits[r]) || 0) + 1);
        while (count.size > 2) {
            const f = fruits[l];
            count.set(f, count.get(f) - 1);
            if (count.get(f) === 0) count.delete(f);
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets