Practice › Sliding Window
Fruit Into Baskets
Medium · Sliding Window · Asked at Amazon, Google, Microsoft
Trees stand in a row; a[i] is the type of fruit on tree i. You have two baskets, each holding only one type of fruit (any amount). Start at any tree and pick one fruit from every tree moving right, stopping when a fruit fits neither basket. Print the maximum number of fruits you can pick.
Input
First line: n. Second line: n space-separated integers.
Output
The maximum number of fruits.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] < n
It is the longest subarray with at most 2 distinct values.
Example 1
Input
3 1 2 1
Output
3
Example 2
Input
5 1 2 3 2 2
Output
4
Hints
- Rephrase: find the longest contiguous subarray with at most 2 distinct values.
- Keep counts of the values in the window; when there are 3 distinct values, shrink from the left until one value disappears.
Approach
Sliding window with a frequency map. Add a[r]. While the map has more than two keys, decrement a[l] (deleting it at zero) and advance l. The window is then valid; record r − l + 1. Since values are < n, an array works as the map.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n), cnt(n + 1, 0);
for (auto &x : a) cin >> x;
int l = 0, distinct = 0, best = 0;
for (int r = 0; r < n; r++) {
if (cnt[a[r]]++ == 0) distinct++;
while (distinct > 2)
if (--cnt[a[l++]] == 0) distinct--;
best = max(best, r - l + 1);
}
cout << best << "\n";
return 0;
}Python solution
import sys
from collections import defaultdict
data = list(map(int, sys.stdin.read().split()))
a = data[1:]
cnt = defaultdict(int)
l = best = 0
for r, x in enumerate(a):
cnt[x] += 1
while len(cnt) > 2:
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
del cnt[a[l]]
l += 1
best = max(best, r - l + 1)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n], cnt = new int[n + 1];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
int l = 0, distinct = 0, best = 0;
for (int r = 0; r < n; r++) {
if (cnt[a[r]]++ == 0) distinct++;
while (distinct > 2)
if (--cnt[a[l++]] == 0) distinct--;
best = Math.max(best, r - l + 1);
}
System.out.println(best);
}
}