Scale Engineer

Fruit Into Baskets

Med
#0858Time: 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: O(1), as the `HashMap` will store at most 3 distinct fruit types at any given time.2 companies
Patterns
Sliding Window
Data structures
ArrayHash Table
Companies
Deutsche BankWalmart Labs

Prompt

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 ith 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 <= 105
  • 0 <= fruits[i] < fruits.length

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as the `HashMap` will store at most 3 distinct fruit types at any given time.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem