[Leetcode] 904. Fruit Into Baskets

https://leetcode.com/problems/fruit-into-baskets/description/?envType=daily-question&envId=2025-08-04

initial

this goes back to https://velog.io/@whitehousechef/Read-before-coding-test
i always think of not updating answer along the way. So my initial but correct way is dirty and unnecessarily complex in implementing k-number-of-keys sliding window

also that while loop template of if we meet an invalid case we make that condition as a while loop.

class Solution {
    public int totalFruit(int[] fruits) {
        int n=fruits.length;
        int left=0,right=0;
        int ans=0;
        Map<Integer,Integer> dic = new HashMap<>();
        while(right<n){
            if(!dic.containsKey(fruits[right]) && dic.size()==2){
                int tmp=0;
                for(int value: dic.values()){
                    tmp+=value;
                }
                ans=Math.max(ans,tmp);
                while(dic.size()==2){
                    int val = dic.get(fruits[left])-1;
                    if(val==0){
                        dic.remove(fruits[left]);
                    } else{
                        dic.put(fruits[left],val);
                    }
                    left+=1;
                }
                dic.put(fruits[right],1);
                right+=1;
            } else{
                dic.put(fruits[right],dic.getOrDefault(fruits[right],0)+1);
                right+=1;
            }
        }
        int tmp=0;
        for(int value: dic.values()){
            tmp+=value;
        }
        ans=Math.max(ans,tmp);
        return ans;
    }
}

sol

much easier way is updating answer as u go. And when we have an invalid condition where dictionary size exeeds 2 as we fix the operation of adding each fruit, only then we slide the window.

    public int totalFruit2(int[] tree) {
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        int res = 0, i = 0;
        for (int j = 0; j < tree.length; ++j) {
            count.put(tree[j], count.getOrDefault(tree[j], 0) + 1);
            while (count.size() > 2) {
                count.put(tree[i], count.get(tree[i]) - 1);
                if (count.get(tree[i]) == 0) count.remove(tree[i]);
                i++;
            }
            res = Math.max(res, j - i + 1);
        }
        return res;
    }

complexity

n time. even tho theres nested while loop, left and right just iterates each element once

1 space