Fruit Into Baskets

How it works

Since we only track two fruit types, we can avoid using a hash map entirely. Instead, we store the two fruit types and the last index where each appeared. When a third type appears, we can immediately jump the left pointer to just after the earlier of the two last indices.

This approach uses O(1) space and handles the window adjustment in constant time by directly computing where the new window should start.

Steps

1. Track fruit1, fruit2, and their last indices fruit1_lastIdx, fruit2_lastIdx.
2. Initialize l = 0 and res = 1.
3. For each index r:
   • If fruits[r] matches fruit1, update fruit1_lastIdx.
   • Else if it matches fruit2 (or fruit2 is unset), update accordingly.
   • Else (third type found):
     • The fruit with the smaller last index gets replaced.
     • Update l to be one past that smaller index.
     • Set the new fruit and its index.
   • Update res with r - l + 1.
4. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Not Removing Zero-Count Entries from the Map

When shrinking the window and decrementing fruit counts, forgetting to remove entries with count zero from the hash map causes the map size to incorrectly indicate more than two fruit types. Always check if a count becomes zero and remove that key from the map before checking the size constraint.

Off-by-One Errors in Window Size Calculation

The window size is r - l + 1, not r - l. Forgetting the +1 leads to undercounting the maximum fruits by one. This is especially easy to miss in the advanced sliding window approach where the final answer is n - l, which correctly accounts for the inclusive nature of the window.

Confusing "At Most Two Types" with "Exactly Two Types"

The problem asks for at most two distinct fruit types, not exactly two. Some solutions incorrectly handle the case where all fruits are the same type (only one type present). The window should still be valid when containing just one fruit type, so the condition should check count.size() > 2, not count.size() != 2.

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        l = 0
        fruit1_lastIdx = 0
        fruit2_lastIdx = -1
        fruit1 = fruits[0]
        fruit2 = -1
        total = res = 1

        for r in range(len(fruits)):
            f = fruits[r]
            if f == fruit1:
                total += 1
                fruit1_lastIdx = r
            elif f == fruit2 or fruit2 == -1:
                total += 1
                fruit2_lastIdx = r
                fruit2 = f
            else:
                if fruit2_lastIdx == min(fruit1_lastIdx, fruit2_lastIdx):
                    fruit1_lastIdx, fruit2_lastIdx = fruit2_lastIdx, fruit1_lastIdx
                    fruit1, fruit2 = fruit2, fruit1

                total -= (fruit1_lastIdx - l + 1)
                l = fruit1_lastIdx + 1
                fruit1 = f
                fruit1_lastIdx = r
            res = max(res, r - l + 1)

        return res

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int l = 0, fruit1_lastIdx = 0, fruit2_lastIdx = -1;
        int fruit1 = fruits[0], fruit2 = -1, total = 1, res = 1;

        for (int r = 0; r < fruits.size(); r++) {
            int f = fruits[r];
            if (f == fruit1) {
                total++;
                fruit1_lastIdx = r;
            } else if (f == fruit2 || fruit2 == -1) {
                total++;
                fruit2_lastIdx = r;
                fruit2 = f;
            } else {
                if (fruit2_lastIdx == min(fruit1_lastIdx, fruit2_lastIdx)) {
                    swap(fruit1_lastIdx, fruit2_lastIdx);
                    swap(fruit1, fruit2);
                }
                total -= (fruit1_lastIdx - l + 1);
                l = fruit1_lastIdx + 1;
                fruit1 = f;
                fruit1_lastIdx = r;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};