Sliding Window: Fruits into baskets

Problem Statement:

You are in a farm, the trees are arranged from left to right.

Trees are represented by integer array “fruits” where fruits[i] is the type of fruit the it’h tree produces.

You need to collect as much as fruits possible with below rules:

1. There are 2 baskets available and each basket can have only one kind of fruit with unlimited quantity.

2. Start from any tree, and proceed towards right and select one fruit from each tree.

Stop the picking when a tree has a fruit type that doesn’t fit in the two basket.

Solution Explanation:

We will solve the problem by using sliding window along with HashMap approach.

Initialize 2 pointers left and right for our sliding window.

Use HashMao to store the count of each fruit type and the number of fruits in each type.

If the map has more than 2 types, then shrink the window until we have only 2 types of fruits,

Keep updating the maxLen for each valid window.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

int solution(vector<int>& fruits) 
{
	 int left = 0;
	 int maxLength = 0;
	 int newFruit=  0;
	 unordered_map<int, int>basket;

	 if(fruits.size() == 0) 
	 	return 0;

	 for(int right = 0; right < fruits.size(); right++)
	 {

        basket[fruits[right]]++;

        while (basket.size() > 2) 
        {
            basket[fruits[left]]--;

            if (basket[fruits[left]] == 0) 
            {
                basket.erase(fruits[left]);
            }

            left++;
        }

        	maxLength = max(maxLength, right - left + 1);
        }
	 return maxLength;
}

int main() 
{
    vector<int> A = {1,2,1,2,3};
    cout << solution(A) << endl; 
    return 0;
}

Output

4