Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Rephrase: find the longest contiguous subarray with at most 2 distinct values.
  2. 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);
    }
}

Solve Fruit Into Baskets online · All practice problems