697. Stretches That Miss Nothing

Let D be the number of DISTINCT values in the whole array. Count the contiguous stretches that contain all D of them.

1 3 1 2 2 -> 4 D = 3 5 5 5 5 -> 10 D = 1, so every stretch qualifies 1 2 1 2 -> 6 1 2 3 1 -> 3

## The extension rule

Fix a left end lo. If the stretch lo .. hi already contains every value, then so does lo .. hi+1, and lo .. hi+2, and so on, because extending never removes anything.

So for each lo there is a SMALLEST qualifying right end r(lo), and the stretches starting at lo that qualify are exactly lo..r(lo) through lo..n-1. There are n - r(lo) of them.

Counting a whole family per left end, instead of testing each stretch, is what makes this linear.

## r is non decreasing

Moving lo right can only remove a value, never add one, so r(lo) never moves LEFT. That is what lets one right pointer sweep forward across the entire run without resetting.

## The sweep

hi = 0; counts = empty; have = 0 for lo in 0 .. n-1: while have < D and hi < n: counts[a[hi]] += 1 if counts[a[hi]] == 1: have += 1 hi += 1 if have < D: break # no left end from here on can qualify answer += n - hi + 1 # hi sits one past r(lo) counts[a[lo]] -= 1 if counts[a[lo]] == 0: have -= 1

The break matters: once the suffix starting at lo cannot contain everything, no later lo can either, and continuing would read past the end.

## The two ways to get the count wrong

The loop leaves hi one PAST the smallest qualifying end, so the count is n - hi + 1, not n - hi. Writing the second is the common slip, and 1 2 answering 0 instead of 1 is how it shows.

The other is recomputing the distinct count per window, which turns a linear sweep back into quadratic work.

## Why a single value gives a triangular number

When D = 1 every non empty stretch qualifies, so the answer is n * (n + 1) / 2. For 5 5 5 5 that is 10, and it is the fastest check that the counting is right.

## Overflow

With n = 200000 and one distinct value the answer is about 2 * 10^10, past a signed 32 bit integer. This is the problem's real trap, and it is in the ANSWER rather than in any intermediate value.

## Cost

Time O(n). Space O(V) for the counts.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 2000`