Fruit Into Baskets

MEDIUM

Description

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by 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 owner has some strict rules that you must follow:

You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

Example 2:

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

Example 3:

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

Constraints:

1 <= fruits.length <= 10⁵
0 <= fruits[i] < fruits.length

Approaches

Checkout 2 different approaches to solve Fruit Into Baskets. Click on different approaches to view the approach and algorithm in detail.

Sliding Window

This problem can be rephrased as finding the longest subarray with at most two distinct elements. This is a classic problem that can be solved efficiently using a sliding window approach. We maintain a "window" (a subarray) and expand it to the right. When the window becomes invalid (contains more than two fruit types), we shrink it from the left until it's valid again, ensuring we only traverse the array once.

Algorithm

Initialize left = 0, maxPicked = 0.
Create a HashMap basket to store counts of fruits in the window.
Iterate with a right pointer from 0 to n-1.
- Add fruits[right] to the basket (or increment its count).
- While the number of distinct fruits in basket is greater than 2:
  - Get the fruit at the left pointer, fruitToRemove.
  - Decrement its count in basket.
  - If its count becomes 0, remove it from basket.
  - Increment left.
- Update maxPicked with the maximum of maxPicked and the current window size (right - left + 1).
Return maxPicked.

We use two pointers, left and right, to define the current window [left, right]. A HashMap is used to store the frequency of each fruit type within this window. We iterate through the fruits array with the right pointer to expand the window. For each fruit fruits[right], we add it to our window and update its count in the HashMap.

After expanding, we check if the window has become invalid, which happens if the number of distinct fruits (map.size()) is greater than 2. If it is, we shrink the window from the left by moving the left pointer. We decrement the count of fruits[left] in the map, and if a fruit's count drops to zero, we remove it entirely from the map. This shrinking process continues until the window is valid again (map.size() <= 2).

At each step, after ensuring the window is valid, we calculate its size (right - left + 1) and update our maxPicked variable if the current window is larger. This single pass through the array ensures that each element is visited by the left and right pointers at most once.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int totalFruit(int[] fruits) {
        if (fruits == null || fruits.length == 0) {
            return 0;
        }
        int maxPicked = 0;
        int left = 0;
        Map<Integer, Integer> basket = new HashMap<>();
        
        for (int right = 0; right < fruits.length; right++) {
            int currentFruit = fruits[right];
            basket.put(currentFruit, basket.getOrDefault(currentFruit, 0) + 1);
            
            while (basket.size() > 2) {
                int leftFruit = fruits[left];
                basket.put(leftFruit, basket.get(leftFruit) - 1);
                if (basket.get(leftFruit) == 0) {
                    basket.remove(leftFruit);
                }
                left++;
            }
            
            maxPicked = Math.max(maxPicked, right - left + 1);
        }
        
        return maxPicked;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of trees. Each element is processed by the `right` pointer once and the `left` pointer at most once, resulting in a linear time complexity.Space Complexity: O(1), as the `HashMap` will store at most 3 distinct fruit types at any given time.

Pros and Cons

Pros:

Optimal time complexity, making it very efficient for large inputs.
Effectively solves the problem by avoiding the redundant computations of the brute-force method.

Cons:

Slightly more complex to conceptualize and implement compared to the brute-force approach.

Code Solutions

Checking out 3 solutions in different languages for Fruit Into Baskets. Click on different languages to view the code.

class Solution {
public
  int totalFruit(int[] fruits) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int j = 0, n = fruits.length;
    for (int x : fruits) {
      cnt.put(x, cnt.getOrDefault(x, 0) + 1);
      if (cnt.size() > 2) {
        int y = fruits[j++];
        cnt.put(y, cnt.get(y) - 1);
        if (cnt.get(y) == 0) {
          cnt.remove(y);
        }
      }
    }
    return n - j;
  }
}

Video Solution

Watch the video walkthrough for Fruit Into Baskets

Patterns:

Sliding Window

Data Structures:

ArrayHash Table

Companies:

Deutsche Bank |Walmart Labs |

Fruit Into Baskets

Description

Approaches

Sliding Window

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Patterns:

Data Structures:

Companies:

On this page

Subscribe to Scale Engineer newsletter