algoadvance

Leetcode 904. Fruit Into Baskets

Problem Statement

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented as an integer array fruits where fruits[i] is the type of fruit the i-th tree produces.

You want to collect as much fruit as possible. However, the restriction is that each basket can only hold one type of fruit and you have only two baskets. Therefore, you have to choose two types of fruits and collect as many of these fruits as possible from the array.

You need to write a function that returns the maximum number of fruits you can collect using the two baskets.

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we had started at the first tree, we would only collect [0, 1].

Example 3:

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we had started at the first tree, we would only collect [1, 2].

Constraints:

Clarifying Questions

  1. Are all elements in the fruits array positive integers?
    • Yes, all elements in the array are integers and within the constraint 0 <= fruits[i] < fruits.length.
  2. Can we assume that the array fruits is never empty?
    • Yes, based on the constraints 1 <= fruits.length.
  3. Is there any specific order we need to maintain while picking fruits?
    • No, you can start collecting from any point but you can pick only fruits of two types contiguously for maximal collection.

Strategy

To solve this problem, we can use the sliding window approach:

  1. Initialize two baskets using a hashmap to keep track of the count of each type of fruit within the window.
  2. Use two pointers, one to expand the window (right) and the other to contract the window (left).
  3. Expand the window by including more elements from the right until the hashmap contains more than two types of fruits.
  4. If there are more than two types of fruits, move the left pointer to reduce the window size until only two types of fruits remain.
  5. During this process, keep track of the maximum size of the window containing only two types of fruits.

Code

#include <unordered_map>
#include <vector>
#include <algorithm>

int totalFruit(std::vector<int>& fruits) {
    std::unordered_map<int, int> basket;
    int left = 0, right = 0, max_fruit = 0;

    while (right < fruits.size()) {
        basket[fruits[right]]++;
        
        while (basket.size() > 2) {
            basket[fruits[left]]--;
            if (basket[fruits[left]] == 0) {
                basket.erase(fruits[left]);
            }
            left++;
        }
        
        max_fruit = std::max(max_fruit, right - left + 1);
        right++;
    }
    
    return max_fruit;
}

Time Complexity

The time complexity of this approach is O(N), where N is the length of the fruits array. This is because both pointers (left and right) only move from the start to the end of the array once.

The space complexity is O(1) as the hashmap will at most contain two keys at any time (representing the two types of fruits).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI