904. Fruit Into Baskets

/**

 * 904. Fruit Into Baskets

 * In a row of trees, the i-th tree produces fruit with type tree[i].

 * You start at any tree of your choice, then repeatedly perform the following steps:

 * Add one piece of fruit from this tree to your baskets.  If you cannot, stop. Move to the next tree to the right of

 * the current tree.  If there is no tree to the right, stop. Note that you do not have any choice after the initial

 * choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you

 * stop.

 * You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one

 * type of fruit each.

 * What is the total amount of fruit you can collect with this procedure?

 * /

See solution to the problem on git hub here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/FruitIntoBasket.java

This pattern used to solve this question is common. The approach is to use a sliding window as you move from left to right in the array while calculating two fruit pairs that enable the highest count.

The algorithm is:

1. Create a map that contains key as fruit id and value as count of fruits we have seen so far
2. Create left and right indices which indicate that is used for the sliding window to measure the count of fruits seen so far.
3. If the size of fruit map created in 1 is greater than 2, keep deleting fruits at left index while advancing the left index until the map count becomes 2
4. Advance the right index forward while map count is 2 or less while recording the total fruit count so far between left and right indices. If the current fruit count is greater than max count, set it as the max count.

Here is the code:

public int totalFruit(int[] tree) {
    Map<Integer, Integer> mapIntegers = new HashMap<>();
    int left = 0, right = 0;
    int maxFruits = 0;
    int currCount = 0;
    for (; left < tree.length && right < tree.length; ) {
        while (mapIntegers.size() > 2 && left < tree.length) {
            int fruit = tree[left];
            int count = mapIntegers.get(fruit);
            count--;
            currCount--;
            if (count == 0) {
                mapIntegers.remove(fruit);
            } else {
                mapIntegers.put(fruit, count);
            }
            left++;
        }
        while (mapIntegers.size() < 3 && right < tree.length) {
            int fruit = tree[right];
            int count = mapIntegers.getOrDefault(fruit, 0);
            count++;
            currCount++;
            mapIntegers.put(fruit, count);
            if (mapIntegers.size() < 3) {
                maxFruits = Math.<em>max</em>(maxFruits, currCount);
            }
            right++;
        }
    }
    return maxFruits;
}