Fruit Into Baskets (at most k distinct)
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
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;}