Fruit Into Baskets (at most k distinct)

Medium

Problem

fruits[i] is the type of the ith tree in a row. You have two baskets, each holding one type (the general version allows k types). Start anywhere and pick one fruit from each tree moving right, stopping when a fruit fits no basket. Return the most fruit you can pick — the longest subarray with at most 2 distinct values.

Example 1

Input:  [1, 2, 1]
Output: 3

Example 2

Input:  [1, 2, 3, 2, 2]
Output: 4

[2, 3, 2, 2].

Test cases

Case 1

Input:    [1,2,1]
Expected: 3

Case 2

Input:    [0,1,2,2]
Expected: 3

Case 3

Input:    [1,2,3,2,2]
Expected: 4

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Window with a count map

Time O(n)Space O(k)

Longest subarray with at most 2 (generally k) distinct values: shrink while the map has more than k keys.

function totalFruit(fruits, k = 2) {
const cnt = new Map();
let l = 0, best = 0;
for (let r = 0; r < fruits.length; r++) {
cnt.set(fruits[r], (cnt.get(fruits[r]) ?? 0) + 1);
while (cnt.size > k) {
const f = fruits[l++];
cnt.set(f, cnt.get(f) - 1);
if (cnt.get(f) === 0) cnt.delete(f);
}
best = Math.max(best, r - l + 1);
}
return best;
}