#904

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Fruit Into Baskets

The Fruit Into Baskets problem requires finding the maximum number of fruits you can pick from a row of trees under specific rules.

array hash table sliding window

Problem Statement

You are at a farm with a row of fruit trees, each producing a type of fruit represented by integers in the array 'fruits'. The goal is to pick as many fruits as possible while following the rule that you can only pick from two distinct types of fruits at a time. The trees are arranged from left to right, and you must choose a contiguous subarray of trees to collect from.

Given the array of fruits, return the maximum number of fruits you can collect from a continuous subarray containing at most two distinct fruit types. The challenge lies in finding an efficient way to calculate this maximum number using array scanning and hash lookups.

Examples

Example 1

Input: fruits = [1,2,1]

Output: 3

We can pick from all 3 trees.

Example 2

Input: fruits = [0,1,2,2]

Output: 3

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

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

Solution Approach

Sliding Window Approach

Use a sliding window to iterate over the 'fruits' array. The window should expand as long as you have two or fewer distinct fruit types within it. Once more than two types are encountered, the window should contract from the left until you are left with only two types. This keeps track of the longest valid subarray.

Hash Table for Fruit Counts

Use a hash table to store the count of each type of fruit within the current window. The hash table allows efficient updating of the count as the window slides over the array. If the number of distinct fruits exceeds two, the left end of the window is moved to reduce the types to two.

Maximizing the Window Size

Throughout the sliding window process, keep track of the maximum window size that contains at most two distinct fruit types. This gives the maximum number of fruits you can collect while adhering to the rules.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because we are iterating over the array once, expanding and contracting the window as needed. The space complexity is O(k), where k is the number of distinct fruit types, which is typically constant in this problem, making the space complexity O(1).

What Interviewers Usually Probe

Evaluate the candidate's understanding of sliding window techniques and hash tables.
Check if the candidate can optimize the window size and manage hash table updates efficiently.
Assess how the candidate handles edge cases, such as arrays with fewer than two distinct fruit types.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly manage the sliding window, leading to unnecessary re-scanning of parts of the array.
Using a brute force approach that checks all subarrays instead of leveraging the sliding window and hash table.
Overcomplicating the problem by not recognizing that the maximum valid subarray is the one with the largest window containing two distinct fruits.

Follow-up variants

Extend the problem to handle more than two fruit types.
Find the maximum number of fruits that can be picked from any subarray that contains exactly two distinct fruit types.
Optimize the solution for cases where the number of fruit types is dynamically provided as an input.

FAQ

What is the best approach to solve the 'Fruit Into Baskets' problem?

The best approach is to use a sliding window to iterate through the array while maintaining a hash table to track fruit counts, ensuring no more than two distinct fruit types at any time.

Can I use a brute force approach to solve this problem?

A brute force approach would involve checking every possible subarray, but it would be inefficient. The sliding window with a hash table is much more optimal.

What is the time complexity of the optimal solution?

The time complexity is O(n), where n is the number of trees in the array. This is because we are only scanning through the array once.

What if there are more than two types of fruits in the 'Fruit Into Baskets' problem?

If there are more than two types of fruits, you can modify the problem to allow for up to three or more types, adjusting the sliding window and hash table to handle additional types.

How does GhostInterview help with 'Fruit Into Baskets'?

GhostInterview helps by providing step-by-step guidance on the sliding window and hash table techniques, ensuring you understand the problem-solving process and can apply it efficiently in interviews.

terminal

Solution

Solution 1: Hash Table + Sliding Window

We use a hash table $cnt$ to maintain the types and corresponding quantities of fruits in the current window, and use two pointers $j$ and $i$ to maintain the left and right boundaries of the window.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        cnt = Counter()
        ans = j = 0
        for i, x in enumerate(fruits):
            cnt[x] += 1
            while len(cnt) > 2:
                y = fruits[j]
                cnt[y] -= 1
                if cnt[y] == 0:
                    cnt.pop(y)
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Solution 2: Monotonic Variable-Length Sliding Window

In Solution 1, we find that the window size sometimes increases and sometimes decreases, which requires us to update the answer each time.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        cnt = Counter()
        ans = j = 0
        for i, x in enumerate(fruits):
            cnt[x] += 1
            while len(cnt) > 2:
                y = fruits[j]
                cnt[y] -= 1
                if cnt[y] == 0:
                    cnt.pop(y)
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Continue Practicing

#930 binary subarrays with sum #992 subarrays with k different integers #632 smallest range covering elements from k lists