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 i^th 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.

Example 1:

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

Example 2:

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:

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

Constraints:

1 <= fruits.length <= 10⁵
0 <= fruits[i] < fruits.length

Solution

/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function(fruits) {
    const map = {}; // store count of fruit (max 3 entries)
    let count = 0; // size of map
    let max = 0; // max number of fruits that can be picked
    let l = 0; // left of window
    let r = 0; // right of window

    for (; r < fruits.length; r++) {
        let fruit = fruits[r];
        if (!(fruit in map)) {
            map[fruit] = 0;
            count++;
        }
        map[fruit]++;

        // find new l that makes window valid
        while (count === 3) {
            fruit = fruits[l];
            map[fruit]--;
            if (!map[fruit]) {
                delete map[fruit];
                count--;
            }
            l++;
        }
        max = Math.max(max, r - l + 1);
    }
    return max;
};

We will implement a sliding window solution. We want to ensure that within our window [l, r], there are only <= 2 types of fruit trees (ie. can pick everything in window with two baskets). To do so, we use map to keep track of the individual count of the two tree types that are in the window, and count for the number of entries in map. We keep sliding r and updating map until count == 3 (ie. three tree types in window, window is no longer valid); when this happens, we slide l until there are again only two tree types in the window (also delete the tree type that is no longer in the window from map).

Problem​

Solution​

Problem

Solution