Arrays tutorial

Welcome to the Arrays world. First move: two pointers and the sliding window.

Walk the array once, keeping a little state, instead of restarting at every position. On a sorted row, put a pointer at each end. Pair too small? Move the left one in. Too big? Move the right one in. A window grows on the right and shrinks on the left; its running sum adds what enters and subtracts what leaves.

The clue: a contiguous subarray or substring, a pair in a sorted array, or the best so far in one pass.

Each pointer only moves one way, so it's linear time and constant extra space.

Now let's use it on Best Time to Buy and Sell Stock.