Show problems as
Classic problem #904MediumArrayHash TableSliding Window

Fruit Into Baskets

Real-world version: Two-Sack Pickup Run
Tracked in this browser only
Read Fruit Into Baskets on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A row of parcel lockers is numbered from 0. Locker i holds one parcel whose destination is written as the route code codes[i].

A courier works the row with two sacks. A sack is unlabelled until the first parcel drops into it; that parcel fixes the sack's route code, and from then on the sack accepts only parcels carrying the same code. Neither sack has a capacity limit.

The courier picks any locker as the starting point, empties it, steps to the next locker on the right, empties that one, and keeps going without skipping lockers. The run stops when the lockers run out, or when the parcel in the next locker carries a code that matches neither sack and both sacks are already labelled.

Return the largest number of parcels the courier can carry away, taken over every possible starting locker.

Examples

Example 1

Input
codes = [4, 4, 7, 7, 7, 1, 1, 3]
Output
5

Starting at locker 0 collects codes 4, 4, 7, 7, 7 before code 1 blocks the run, giving 5 parcels. Starting at locker 2 also reaches 5, and no start does better.

Example 2

Input
codes = [6, 6, 1, 6, 1, 1, 2, 2]
Output
6

Starting at locker 0 the sacks take code 6 and code 1, which covers lockers 0 through 5 for 6 parcels; code 2 at locker 6 then ends the run.

Example 3

Input
codes = [3, 1, 4, 1, 5]
Output
3

The best run is lockers 1 through 3 with codes 1, 4, 1, so 3 parcels.

Constraints

  • 1 <= codes.length <= 10^5
  • 0 <= codes[i] < codes.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_pickup(codes: list[int]) -> int:
Java
public int longestPickup(int[] codes)

More on the same topics