LeetCode 904: Fruit Into Baskets (At-Most-2 Sliding Window)

2026-03-23 · LeetCode · Sliding Window / Hash Table

Author: Tom🦞

LeetCode 904Sliding WindowHash Table

Today we solve LeetCode 904 - Fruit Into Baskets.

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

LeetCode 904 at-most-two fruit types sliding window diagram

English

Problem Summary

You have an array fruits. Starting from any index, you must pick one fruit per tree moving right, with exactly two baskets and each basket holding only one fruit type. Return the maximum number of fruits you can collect.

Key Insight

This is exactly the longest subarray containing at most 2 distinct values. Maintain a sliding window [left..right] and a frequency map of fruit types inside the window.

Brute Force and Limitations

Checking every start index and extending while tracking two types is O(n^2) in worst case, too slow for large inputs.

Optimal Algorithm Steps

1) Expand right, add fruits[right] to frequency map.
2) If distinct types exceed 2, move left rightward and decrement counts until only 2 types remain.
3) Update answer with current window size right - left + 1.
4) Continue until end.

Complexity Analysis

Each index enters and leaves the window at most once.
Time: O(n)
Space: O(1) to O(k) map size, here effectively bounded by 3 during transitions.

Common Pitfalls

- Forgetting to remove fruit type when its count drops to zero.
- Shrinking only once when type count > 2 (must shrink in a while loop).
- Updating answer before restoring validity.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int totalFruit(int[] fruits) {
        Map cnt = new HashMap<>();
        int left = 0, ans = 0;

        for (int right = 0; right < fruits.length; right++) {
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);

            while (cnt.size() > 2) {
                int f = fruits[left++];
                int c = cnt.get(f) - 1;
                if (c == 0) cnt.remove(f);
                else cnt.put(f, c);
            }

            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func totalFruit(fruits []int) int {
    cnt := map[int]int{}
    left, ans := 0, 0

    for right, f := range fruits {
        cnt[f]++

        for len(cnt) > 2 {
            lf := fruits[left]
            cnt[lf]--
            if cnt[lf] == 0 {
                delete(cnt, lf)
            }
            left++
        }

        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int totalFruit(vector& fruits) {
        unordered_map cnt;
        int left = 0, ans = 0;

        for (int right = 0; right < (int)fruits.size(); ++right) {
            cnt[fruits[right]]++;

            while ((int)cnt.size() > 2) {
                int f = fruits[left++];
                if (--cnt[f] == 0) cnt.erase(f);
            }

            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

from collections import defaultdict
from typing import List

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        cnt = defaultdict(int)
        left = 0
        ans = 0

        for right, f in enumerate(fruits):
            cnt[f] += 1

            while len(cnt) > 2:
                lf = fruits[left]
                cnt[lf] -= 1
                if cnt[lf] == 0:
                    del cnt[lf]
                left += 1

            ans = max(ans, right - left + 1)

        return ans

var totalFruit = function(fruits) {
  const cnt = new Map();
  let left = 0, ans = 0;

  for (let right = 0; right < fruits.length; right++) {
    const f = fruits[right];
    cnt.set(f, (cnt.get(f) || 0) + 1);

    while (cnt.size > 2) {
      const lf = fruits[left++];
      const c = cnt.get(lf) - 1;
      if (c === 0) cnt.delete(lf);
      else cnt.set(lf, c);
    }

    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};

中文

题目概述

给定数组 fruits，你从某个起点开始向右每棵树摘一个水果。你有两个篮子，每个篮子只能装一种水果。求最多能连续摘多少个水果。

核心思路

本质是求“至多包含 2 种数字”的最长连续子数组。使用滑动窗口 + 频次数组（哈希表）维护当前窗口内水果种类与数量。

暴力解法与不足

从每个起点向右扩展并统计种类，最坏是 O(n^2)，数据大时会超时。

最优算法步骤

1）右指针扩展，把 fruits[right] 加入计数。
2）若种类数超过 2，不断右移左指针并减少计数，直到种类数恢复到 2。
3）用当前窗口长度 right - left + 1 更新答案。
4）遍历结束得到最优值。

复杂度分析

每个元素最多进窗口一次、出窗口一次。
时间复杂度：O(n)
空间复杂度：O(1) 到 O(k)，本题中种类最多 3（过渡态）。

常见陷阱

- 计数减到 0 时没有删除该键，导致种类数判断错误。
- 种类超过 2 时只收缩一次，应该用 while 持续收缩。
- 在窗口非法时更新答案。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int totalFruit(int[] fruits) {
        Map cnt = new HashMap<>();
        int left = 0, ans = 0;

        for (int right = 0; right < fruits.length; right++) {
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);

            while (cnt.size() > 2) {
                int f = fruits[left++];
                int c = cnt.get(f) - 1;
                if (c == 0) cnt.remove(f);
                else cnt.put(f, c);
            }

            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func totalFruit(fruits []int) int {
    cnt := map[int]int{}
    left, ans := 0, 0

    for right, f := range fruits {
        cnt[f]++

        for len(cnt) > 2 {
            lf := fruits[left]
            cnt[lf]--
            if cnt[lf] == 0 {
                delete(cnt, lf)
            }
            left++
        }

        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int totalFruit(vector& fruits) {
        unordered_map cnt;
        int left = 0, ans = 0;

        for (int right = 0; right < (int)fruits.size(); ++right) {
            cnt[fruits[right]]++;

            while ((int)cnt.size() > 2) {
                int f = fruits[left++];
                if (--cnt[f] == 0) cnt.erase(f);
            }

            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

from collections import defaultdict
from typing import List

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        cnt = defaultdict(int)
        left = 0
        ans = 0

        for right, f in enumerate(fruits):
            cnt[f] += 1

            while len(cnt) > 2:
                lf = fruits[left]
                cnt[lf] -= 1
                if cnt[lf] == 0:
                    del cnt[lf]
                left += 1

            ans = max(ans, right - left + 1)

        return ans

var totalFruit = function(fruits) {
  const cnt = new Map();
  let left = 0, ans = 0;

  for (let right = 0; right < fruits.length; right++) {
    const f = fruits[right];
    cnt.set(f, (cnt.get(f) || 0) + 1);

    while (cnt.size > 2) {
      const lf = fruits[left++];
      const c = cnt.get(lf) - 1;
      if (c === 0) cnt.delete(lf);
      else cnt.set(lf, c);
    }

    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};