904 - Fruit Into Baskets

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.

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

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]

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: we can pick from trees [2,3,2,2]

Constraints:

• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length

Approach

Behind the story it just asks for the longest run of neighbouring trees holding at most two different kinds of fruit. Picking from every tree as you walk right means the trees you pick from sit next to each other, two baskets means at most two kinds, and one fruit per tree means the answer is the length of that run.

So move r forward and count each kind inside the window. Once a third kind shows up, move l forward, dropping trees, until one kind is gone completely. Then check the length. Drop a kind from the counts the moment it reaches 0, else it still counts as a kind that’s in the window when it has already been left behind - the same thing that matters in 2461.

fruits = [1,2,3,2,2]
r=0  [1]          kinds {1}                  best=1
r=1  [1,2]        kinds {1,2}                best=2
r=2  [1,2,3]      kinds {1,2,3} -> drop 1
     [2,3]        kinds {2,3}                best=2
r=3  [2,3,2]      kinds {2,3}                best=3
r=4  [2,3,2,2]    kinds {2,3}                best=4
answer = 4

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> mp;
        const int n = fruits.size();
        int maxi = 0;
        for (int r = 0, l = 0; r < n; r++) {
            mp[fruits[r]]++;
            while (mp.size() > 2) {
                int out = fruits[l];
                if (--mp[out] == 0) mp.erase(out);
                l++;
            }
            maxi = max(maxi, r - l + 1);
        }
        return maxi;
    }
};

• time: O(n) - each tree enters once and leaves at most once
• space: O(1) - the map never holds more than three kinds

Counting with a vector

Since fruits[i] < fruits.length, a kind can be used as an index straight into a vector, which skips hashing altogether. mp.size() has no counterpart here, so keep a distinct counter and change it when a count leaves 0 or comes back to it.

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        const int n = fruits.size();
        vector<int> cnt(n, 0);
        int distinct = 0, maxi = 0;
        for (int r = 0, l = 0; r < n; r++) {
            if (cnt[fruits[r]]++ == 0) distinct++;
            while (distinct > 2) {
                if (--cnt[fruits[l]] == 0) distinct--;
                l++;
            }
            maxi = max(maxi, r - l + 1);
        }
        return maxi;
    }
};

This trades space for speed: O(n) instead of O(1), so at the top of the constraints it’s a single 10^5 int vector, about 400 KB, zeroed once in one pass. That pass costs far less than the hashing it saves, but the map version is the one to keep if the values were unbounded or spread thin, since then the vector would be mostly empty.

• time: O(n)
• space: O(n)