class Solution {
public:
    int totalFruit(vector<int>& tree) {
        map<int, int> idx; // {fruit -> last_index}
        int ans = 0;
        int cur = 0;
        for (int i = 0; i < tree.size(); ++i) {
            int f = tree[i];
            if (!idx.count(f)) {
                if (idx.size() == 2) {
                    auto it1 = begin(idx);
                    auto it2 = next(it1);
                    if (it1->second > it2->second) swap(it1, it2);
                    cur = i - it1->second - 1;
                    idx.erase(it1);
                }
            }
            idx[f] = i;
            ans = max(++cur, ans);
        }
        return ans;
    }
};

// Solution: Hashtable + Sliding window
// Time complexity: O(n)
// Space complexity: O(1)
// Keep track of the last index of each element. If a third type of fruit comes in, the new window starts after the fruit with smaller last index. Otherwise extend the current window.
// [1 3 1 3 1 1] 4 1 4 ... <- org window, 3 has a smaller last index than 1.
// 1 3 1 3 [1 1 4] 1 4 ... <- new window
class Solution {
    public int totalFruit(int[] tree) {
        TreeMap<Integer, Integer> idx = new TreeMap<>(); // {fruit -> last_index}
        int ans = 0;
        int cur = 0;
        for (int i = 0; i < tree.length; ++i) {
            int f = tree[i];
            if (!idx.containsKey(f)) {
                if (idx.size() == 2) {
                    Map.Entry<Integer, Integer> it1 = idx.firstEntry();
                    Map.Entry<Integer, Integer> it2 = idx.lastEntry();
                    if (it1.getValue() > it2.getValue()) {
                        Map.Entry<Integer, Integer> tmp = it1;
                        it1 = it2;
                        it2 = tmp;
                    }
                    cur = i - it1.getValue() - 1;
                    idx.remove(it1.getKey());
                }
            }
            idx.put(tree[i], i);
            ans = Math.max(++cur, ans);
        }
        return ans;
    }
}

add FruitIntoBaskets.java