Fruit Into Baskets |🔥 C++ | Sliding Window | Map | Easy explanation | Leetcode

codesplash

·

Follow

1 min read

·

Mar 30, 2024

--

Listen

Share

Intuition

We will keep plucking one fruit while traversing from left to right and put it into one type of basket (map) between the two baskets. If at any point we need more than two baskets, we will start removing that type of fruit until one basket is freed up.

Why Sliding Window?

Maximum fruit insert in k (2 size basket) and it can be from any subarray.

Approach

=> Take map as two basket
=> i & j for traversing
=> we will keep moving with j for plucking & i for removing fruits
from basket(map)
=> If basket size is < 2, count the maximum fruit in the basket with j-i+1

Complexity

Time complexity: O (N)

Space complexity: O (1)-> Only keeping 2 types of fruit in the map at any point of time.

Code

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        map<int,int> m;
        int i=0,j=0;
        int ans=0;
        while(j<fruits.size()){
            m[fruits[j]]++;
            while(m.size()>2){
                m[fruits[i]]--;
                if(m[fruits[i]]==0)m.erase(fruits[i]);
                i++;
            }
            ans=max(ans,j-i+1);
            j++;
        }
        return ans;
    }
};