904. Fruit Into Baskets

Version #3 Two Pointers
Time O(n)

38.04 %
class Solution {
    public int totalFruit(int[] tree) {
// (left, right] is a valid subarray that only contains at most two kinds of fruits
// key-fruit id, value-count
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
int k = 2;
int left = -1, right = 0;
for (right = 0; right < tree.length; right++) {
int count = map.getOrDefault(tree[right], 0);
if (count == 0) k--; // a new type of fruit added
map.put(tree[right], count + 1);
while (k < 0) {
left++;
count = map.getOrDefault(tree[left], 0) - 1;
if (count == 0) k++; // this type of fruit is totally removed
map.put(tree[left], count);
}
// k == 0
max = Math.max(max, right - left);
}
return max;
}
}



Version #2 LinkedHashMap
Time O(n)

public int totalFruit(int[] tree) {
        if (tree == null) {
            return 0;
        }
        int maxLength = 0;
        FruitLinkedHashMap<Integer, Integer> map = new FruitLinkedHashMap<>(16, .75f, true, 3);
        map.put(-1, -1);
        for (int i = 0; i < tree.length; i++) {
            map.put(tree[i], i);
            try {
                maxLength = Math.max(maxLength, map.getLastViaReflection() - map.getFirstViaReflection());
            } catch (Exception e) {
                return 0;
            }
        }
        return maxLength;
    }

Helper class:

import java.lang.reflect.Field;
import java.util.LinkedHashMap;
import java.util.Map;

class FruitLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_ENTRIES;

    public FruitLinkedHashMap(
            int initialCapacity, float loadFactor, boolean accessOrder, int maxEntries) {
        super(initialCapacity, loadFactor, accessOrder);
        this.MAX_ENTRIES = maxEntries;
    }
    @Override
    public boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    public V getFirstViaReflection() throws NoSuchFieldException, IllegalAccessException {
        Field head = LinkedHashMap.class.getDeclaredField("head");
        head.setAccessible(true);
        return ((Map.Entry<K, V>)head.get(this)).getValue();
    }

    public V getLastViaReflection() throws NoSuchFieldException, IllegalAccessException {
        Field tail = LinkedHashMap.class.getDeclaredField("tail");
        tail.setAccessible(true);
        return ((Map.Entry<K, V>)tail.get(this)).getValue();
    }
}

Version #1 HashMap LastOccurance
Time O(kn)

class Solution {
    public int totalFruit(int[] tree) {
        // Find the longest sub array [start, end] that only has 2 kinds of fruits
        if (tree == null || tree.length == 0) {
            return 0;
        }
        int result = 0;
        int start = 0, end = 0;
        // key -> fruit id, value -> index of last occurance
        Map<Integer, Integer> lastOccurance = new HashMap<>();
        for (end = 0; end < tree.length; end++) {
            lastOccurance.put(tree[end], end);
            if (lastOccurance.size() > 2) {
                start = 1 + lastOccurance.remove(tree[Collections.min(lastOccurance.values())]);
            }
            result = Math.max(result, end - start + 1);
        }
        return result;
    }
}