In an in-place sweep collapsing consecutive equal timestamps in a sorted log, what does the slow index mark?

## The setting A sensor log arrives sorted by timestamp, and repeated timestamps mean the same instant was reported more than once. You want one reading per timestamp, collapsed in place, with no second buffer. The sweep uses two indices moving the same direction: `fast` reads every entry; `slow` marks the frontier of the surviving prefix. ## The invariant, stated properly After the iteration that has just consumed `log[fast]`: > `log[0 .. slow]` contains exactly the distinct-timestamp collapse of the original `log[0 .. fast]`, in the original order, and `slow <= fast`. Everything else follows. The `slow <= fast` half is what makes writing safe: the write frontier never reaches a slot the scanner has not already read, so mutating during the traversal cannot destroy unread input. The first half is what makes the answer correct: at the end, `fast` has consumed the whole log, so the kept prefix is the collapse of the whole log. ## Where the off-by-one lives There are two defensible conventions, and the bug is always the seam between them. **Convention A — `slow` is the last written index.** Initialise `slow = 0` (the first reading is always kept), start `fast` at 1, and on a new timestamp do `slow = slow + 1` *before* the copy. At the end the survivors occupy `log[0 .. slow]`, which is `slow + 1` entries, so you return `slow + 1`. **Convention B — `slow` is the next free slot.** Initialise `slow = 0`, compare each candidate against `log[slow - 1]` (guarding the first write), copy to `log[slow]`, then increment. At the end you return `slow`, because `slow` counts what was written. Both are correct. Returning `slow` under A undercounts by one and silently drops the last surviving reading; returning `slow + 1` under B invents a slot that was never written. When an interviewer asks "what exactly does slow point at?", this is what they are checking — not vocabulary, but whether you can name the frontier and derive the returned length from it rather than guessing. ## Base cases - **Empty log.** Under convention A, `slow = 0` asserts that a first reading exists. On a zero-length log that is a lie, and `slow + 1` reports a length of one for an array with nothing in it. The guard belongs before the initialisation, not inside the loop. - **One reading.** The loop never executes, `slow` stays 0, and the answer is 1 with zero writes performed. Good sweeps do nothing on inputs that need nothing. - **All timestamps equal.** One survivor; the scanner walks the whole log and the frontier never moves. This is also the case where a self-copy `log[slow] = log[fast]` would be redundant, which is why the write is guarded by the inequality test rather than performed unconditionally. - **All timestamps distinct.** Every entry is kept, `slow` trails `fast` by exactly zero, and every write is a self-copy. Some implementations skip the write when `slow == fast` to avoid pointless stores; that is an optimisation, not a correctness matter. ## The precondition nobody states This sweep removes **adjacent** duplicates only. On an unsorted log, two entries with the same timestamp separated by a third will both survive, and a candidate who claims the sweep "removes duplicates" without qualification has just failed a boundary question. If the input is not ordered by the collapse key, you need a different tool — an ordering pass first, or a membership structure with its own cost and its own worst case. ## The stale tail After the sweep, positions past the new length still hold copies of entries that were moved down. This is not corruption; the function's contract is *the prefix of the returned length is valid*. Clearing the tail costs another linear pass and buys nothing unless the entries hold references whose lifetime you care about. What you must not do is hand the buffer to a caller without the length — the length **is** the result, and losing it turns a correct sweep into a data bug. ## Order and cost The sweep preserves the relative order of survivors, because entries are copied strictly leftward in the order they were scanned. Time is linear: one full read pass and at most `n` writes. Auxiliary space is O(1) — two indices, no second buffer. That last property is the entire reason to reach for this shape instead of building a fresh output; when the caller can tolerate a copy, the copying version is easier to review and asymptotically identical.