Two baskets, one row of trees

You are walking along a single row of fruit trees. Each tree is given as a number saying what kind of fruit it grows.

You carry two baskets, and each basket holds only one kind of fruit. You pick exactly one fruit from every tree you pass, starting at a tree of your choosing and stopping as soon as you reach a tree whose fruit fits in neither basket.

How many fruit can you pick at most?

Worked example#

For [1, 2, 1, 2, 3]:

Starting at the first tree you pick 1, 2, 1, 2 and then stop: the 3 is a third kind. That is 4 fruit, and no other starting point does better.

Saying it plainly#

Strip away the baskets and the question is: what is the longest run of consecutive trees using at most two different kinds? Word problems often hide a short question like that, and finding it is most of the work.

The idea#

This is a window that grows and shrinks, rather than one of fixed size. Two pointers mark its ends and a map counts how many of each kind are inside.

Move the right edge one tree at a time and add that fruit to the counts. If the window now holds three kinds, it has gone too far, so move the left edge in, taking fruit out of the counts, until only two kinds remain. Remove a kind from the map entirely when its count hits zero, because "how many kinds are in here" is the size of the map and a leftover zero would lie about it.

After each step the window is valid, so its length is a candidate for the answer.

Each edge only ever moves right, so although there is a loop inside a loop, each tree is added once and removed at most once: one pass, not n squared. That argument is the same one that makes monotonic stacks fast, and it is worth being able to give it out loud.

Constraints#

• 1 <= n <= 100000
• 0 <= trees[i] <= 100000