Skip to content

← leetcode

Fruit Into Baskets

· Medium

LeetCode problem 904

One look at the question and you should know the answer{w;} involve a sliding window.

You keep track of two pointers, l and r, and continuously increment r, incrementing the count of fruits[r] in a hashmap.

When there are more than 3 unique elements inside fruits, it implies we need to shrink the left-hand side of the sliding window, meaning we increment l and decrement the count of fruits[l] until there exist only 2 unique elements inside fruits again.

Then, for each valid sliding window, we can just update our ans if it is larger than before.

code

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int l = 0, r = 0, ans = 0, n = fruits.size();
        unordered_map<int, int> baskets;

        while (r < n) {
            ++baskets[fruits[r]];

            while (baskets.size() > 2) {
                --baskets[fruits[l]];
                if (baskets[fruits[l]] == 0) {
                    baskets.erase(fruits[l]);
                }
                ++l;
            }

            ++r;
            ans = max(ans, r-l);
        }

        return ans;
    }
};

complexity

  • Time: O(n) where n denotes the number of elements inside fruits
  • Space: O(1)

time taken

  • 5 minutes and 39 seconds