619. The Closest Two Words
A list of n words is given, along with two DIFFERENT words x and y, each appearing at
least once in the list.
Print the smallest distance between a position holding x and a position holding y, where the
distance between positions i and j is |i - j|.
the quick brown fox quick, x = quick, y = fox -> 1
a x x x b, x = a, y = b -> 4
## The nested loop, and what replaces it
Comparing every occurrence of x with every occurrence of y is O(n^2) in the worst case,
which a list of 100000 alternating words reaches exactly.
Instead, read the list once and remember the MOST RECENT position of each word:
px = -1, py = -1, best = infinity
for i, w in the list:
if w == x:
px = i
if py >= 0: best = min(best, px - py)
if w == y:
py = i
if px >= 0: best = min(best, py - px)
## Why only the most recent occurrence matters
When position i holds x, the best partner for it among positions BEFORE i is the latest
y before i, because any earlier y is further away. So one remembered position per word is
enough, and older ones can be forgotten as soon as a newer one appears.
Every pair is therefore considered, in the sense that matters: for each occurrence, its best possible partner is examined at the moment that occurrence is read.
## Two separate ifs, not an else
Both conditions are tested independently. Using else if would be wrong in general, and it is
only safe here because the statement promises x and y are different words, so no position
can be both.
Writing two plain ifs makes the code survive that promise being relaxed, which is worth the
one extra comparison.
## Why the pointers never rewind
px and py only ever move forward, and the list is read once. This is the same discipline as
the array sweeps in this topic, with the "pointers" stored as remembered indices rather than
loop variables.
## Boundaries
Adjacent occurrences give 1, the smallest possible answer, since the words are different and so cannot share a position.
A single x and a single y give their fixed distance, however large.
## Cost
Time O(n) with one pass. Space O(1) beyond the input.
Constraints - `2 ≤ n ≤ 200000` - each word is 1 to 20 lowercase letters - `x` and `y` are different and each appears at least once
Input
The first line contains an integer n.
The second line contains n words separated by spaces.
The third line contains the two words x and y, separated by a space.
Output
Print one integer, the smallest distance between an occurrence of x and one of y.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.