Intermediate Level
Implement the fruitIntoBasketsMaxCount method that returns the maximum fruits collected using at most two fruit types.
The input contains an array fruits and its length size. Each value represents a type of fruit on a tree in a row.
You have two baskets, and each basket can contain only one fruit type. Your task is to return the maximum number of fruits you can collect from a continuous section of trees.
This means you need the longest continuous subarray that contains at most two distinct fruit types.
Example 1
Input
fruits (int[]) =
[1,2,1]size (int) =
3Returns (int)
3Example 2
Input
fruits (int[]) =
[0,1,2,2]size (int) =
4Returns (int)
3Example 3
Input
fruits (int[]) =
[1,2,3,2,2]size (int) =
5Returns (int)
4Use a sliding window with a frequency map of fruit types.
Expand the window to include more trees. If the window contains more than two fruit types, move the left pointer forward and update counts until only two types remain.
For every valid window, update the maximum length because that length is the number of fruits collected.
Pseudocode:
function fruitIntoBasketsMaxCount(fruits, size):
left = 0
best = 0
frequency = empty map
for right from 0 to size - 1:
add fruits[right] to frequency
while number of keys in frequency > 2:
decrease frequency of fruits[left]
if frequency of fruits[left] becomes 0:
remove fruits[left] from frequency
left++
best = maximum(best, right - left + 1)
return bestReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run