Fruit Into Baskets Problem

Problem

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 ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

  • 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.

Examples

Example 1:

1
2
3
4
5

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

Example 2:

1
2
3
4
5
6

Input:
fruits = [0,1,2,2]
Output:
 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

Example 3:

1
2
3
4
5
6

Input:
fruits = [1,2,3,2,2]
Output:
 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

Solution

Method 1 – Sliding Window with HashMap

Intuition

We want the longest subarray with at most two types of fruits. This is a classic sliding window problem where we expand the window to include new fruits and shrink it from the left when we have more than two types.

Approach

  1. Use a hashmap to count the number of each fruit in the current window.
  2. Expand the window by moving the right pointer and adding fruits.
  3. If there are more than two types, shrink the window from the left until only two types remain.
  4. Track the maximum window size during the process.
  5. Return the maximum size found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> cnt;
        int ans = 0, left = 0;
        for (int right = 0; right < fruits.size(); ++right) {
            cnt[fruits[right]]++;
            while (cnt.size() > 2) {
                cnt[fruits[left]]--;
                if (cnt[fruits[left]] == 0) cnt.erase(fruits[left]);
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func totalFruit(fruits []int) int {
    cnt := map[int]int{}
    ans, left := 0, 0
    for right, f := range fruits {
        cnt[f]++
        for len(cnt) > 2 {
            cnt[fruits[left]]--
            if cnt[fruits[left]] == 0 {
                delete(cnt, fruits[left])
            }
            left++
        }
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0, left = 0;
        for (int right = 0; right < fruits.length; right++) {
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
            while (cnt.size() > 2) {
                cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
                if (cnt.get(fruits[left]) == 0) cnt.remove(fruits[left]);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun totalFruit(fruits: IntArray): Int {
        val cnt = mutableMapOf<Int, Int>()
        var ans = 0
        var left = 0
        for (right in fruits.indices) {
            cnt[fruits[right]] = cnt.getOrDefault(fruits[right], 0) + 1
            while (cnt.size > 2) {
                cnt[fruits[left]] = cnt[fruits[left]]!! - 1
                if (cnt[fruits[left]] == 0) cnt.remove(fruits[left])
                left++
            }
            ans = maxOf(ans, right - left + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)
        ans = left = 0
        for right, f in enumerate(fruits):
            cnt[f] += 1
            while len(cnt) > 2:
                cnt[fruits[left]] -= 1
                if cnt[fruits[left]] == 0:
                    del cnt[fruits[left]]
                left += 1
            ans = max(ans, right - left + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use std::collections::HashMap;
impl Solution {
    pub fn total_fruit(fruits: Vec<i32>) -> i32 {
        let mut cnt = HashMap::new();
        let (mut ans, mut left) = (0, 0);
        for (right, &f) in fruits.iter().enumerate() {
            *cnt.entry(f).or_insert(0) += 1;
            while cnt.len() > 2 {
                let l = fruits[left];
                *cnt.get_mut(&l).unwrap() -= 1;
                if cnt[&l] == 0 { cnt.remove(&l); }
                left += 1;
            }
            ans = ans.max(right - left + 1);
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    totalFruit(fruits: number[]): number {
        const cnt = new Map<number, number>();
        let ans = 0, left = 0;
        for (let right = 0; right < fruits.length; right++) {
            cnt.set(fruits[right], (cnt.get(fruits[right]) ?? 0) + 1);
            while (cnt.size > 2) {
                cnt.set(fruits[left], cnt.get(fruits[left])! - 1);
                if (cnt.get(fruits[left]) === 0) cnt.delete(fruits[left]);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of trees, since each tree is visited at most twice.
  • 🧺 Space complexity: O(1) to O(2) (or O(k) for k types), but at most 2 types are kept in the map at any time.

Method 2 – Last Two Types Tracking

Intuition

Instead of a hashmap, we can track the last two types and their most recent positions. This can be more space-efficient and sometimes faster in practice.

Approach

  1. Track the last two fruit types and their last seen positions.
  2. When a new type is encountered, move the left pointer to just after the last occurrence of the older type.
  3. Update the answer as we go.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int ans = 0, left = 0;
        int type1 = -1, type2 = -1, last1 = -1, last2 = -1;
        for (int right = 0; right < fruits.size(); ++right) {
            if (fruits[right] == type1 || fruits[right] == type2) {
                // do nothing
            } else {
                left = min(last1, last2) + 1;
            }
            if (fruits[right] == type1) {
                last1 = right;
            } else if (fruits[right] == type2) {
                last2 = right;
            } else {
                if (last1 < last2) {
                    type1 = fruits[right];
                    last1 = right;
                } else {
                    type2 = fruits[right];
                    last2 = right;
                }
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func totalFruit(fruits []int) int {
    ans, left := 0, 0
    type1, type2 := -1, -1
    last1, last2 := -1, -1
    for right, f := range fruits {
        if f == type1 || f == type2 {
            // do nothing
        } else {
            if last1 < last2 {
                left = last1 + 1
            } else {
                left = last2 + 1
            }
        }
        if f == type1 {
            last1 = right
        } else if f == type2 {
            last2 = right
        } else if last1 < last2 {
            type1 = f
            last1 = right
        } else {
            type2 = f
            last2 = right
        }
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int totalFruit(int[] fruits) {
        int ans = 0, left = 0;
        int type1 = -1, type2 = -1, last1 = -1, last2 = -1;
        for (int right = 0; right < fruits.length; right++) {
            if (fruits[right] == type1 || fruits[right] == type2) {
                // do nothing
            } else {
                left = Math.min(last1, last2) + 1;
            }
            if (fruits[right] == type1) {
                last1 = right;
            } else if (fruits[right] == type2) {
                last2 = right;
            } else if (last1 < last2) {
                type1 = fruits[right];
                last1 = right;
            } else {
                type2 = fruits[right];
                last2 = right;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun totalFruit(fruits: IntArray): Int {
        var ans = 0
        var left = 0
        var type1 = -1
        var type2 = -1
        var last1 = -1
        var last2 = -1
        for (right in fruits.indices) {
            if (fruits[right] == type1 || fruits[right] == type2) {
                // do nothing
            } else {
                left = minOf(last1, last2) + 1
            }
            if (fruits[right] == type1) {
                last1 = right
            } else if (fruits[right] == type2) {
                last2 = right
            } else if (last1 < last2) {
                type1 = fruits[right]
                last1 = right
            } else {
                type2 = fruits[right]
                last2 = right
            }
            ans = maxOf(ans, right - left + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        ans = left = 0
        type1 = type2 = last1 = last2 = -1
        for right, f in enumerate(fruits):
            if f == type1 or f == type2:
                pass
            else:
                left = min(last1, last2) + 1
            if f == type1:
                last1 = right
            elif f == type2:
                last2 = right
            elif last1 < last2:
                type1 = f
                last1 = right
            else:
                type2 = f
                last2 = right
            ans = max(ans, right - left + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn total_fruit(fruits: Vec<i32>) -> i32 {
        let (mut ans, mut left) = (0, 0);
        let (mut type1, mut type2) = (-1, -1);
        let (mut last1, mut last2) = (-1, -1);
        for (right, &f) in fruits.iter().enumerate() {
            if f == type1 || f == type2 {
                // do nothing
            } else {
                left = std::cmp::min(last1, last2) + 1;
            }
            if f == type1 {
                last1 = right as i32;
            } else if f == type2 {
                last2 = right as i32;
            } else if last1 < last2 {
                type1 = f;
                last1 = right as i32;
            } else {
                type2 = f;
                last2 = right as i32;
            }
            ans = ans.max(right as i32 - left as i32 + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    totalFruit(fruits: number[]): number {
        let ans = 0, left = 0;
        let type1 = -1, type2 = -1, last1 = -1, last2 = -1;
        for (let right = 0; right < fruits.length; right++) {
            if (fruits[right] === type1 || fruits[right] === type2) {
                // do nothing
            } else {
                left = Math.min(last1, last2) + 1;
            }
            if (fruits[right] === type1) {
                last1 = right;
            } else if (fruits[right] === type2) {
                last2 = right;
            } else if (last1 < last2) {
                type1 = fruits[right];
                last1 = right;
            } else {
                type2 = fruits[right];
                last2 = right;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of trees, since each tree is visited at most twice.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.