Merged Departure Board

Easytwo pointersAlso known as Remove Duplicates from Sorted Array

A small station shows its departures on one screen. The times come from two feeds, the train company and the bus company, merged into one list sorted by time. Each time is written as minutes after midnight, so 6:05 is 365.

Some departures share a time, and the screen ends up with rows like 365, 365. The screen only has room for one row per time. The board's tiny controller cannot afford a second list, so it must clean up the one it has.

Your task

Write dedupeBoard(times). times is sorted from earliest to latest. Change it in place so it holds each distinct time exactly once, still in sorted order, and nothing else. The list gets shorter when there are repeats. Return nothing.

Do not build a second list. Overwrite values inside times, then cut off the leftover tail (in JavaScript set times.length; in Python use del times[k:], where k is how many times you kept).

dedupeBoard(times: int[]) → void (changes times in place)

Examples

Example 1

Input

times = [365, 365, 410, 455, 455, 455, 520]

Output

[365, 410, 455, 520]

Why

365 appears twice and 455 three times. Keep one of each: 365, 410, 455, 520. The list shrinks from 7 entries to 4.

Example 2

Input

times = [480, 495, 510]

Output

[480, 495, 510]

Why

No time repeats, so the list stays exactly as it was.

Constraints

0 ≤ times.length ≤ 10,000
0 ≤ times[i] ≤ 1,439
times is sorted in non-decreasing order.

Start with brute force

Walk the list, and each time an entry equals the one before it, delete it (splice in JavaScript, del or pop(i) in Python).

It works, but every delete shifts all the later entries one place left. A board of 10,000 entries that are almost all repeats does close to 10,000 deletes, each shifting thousands of entries: about 50 million moves. Deciding where each entry goes once, and writing it there once, avoids the shifting.

Hints

0 of 4 shown

Hint 1
Look at [365, 365, 410]. Because the list is sorted, where can a repeat of 365 be? Could one show up after 410?
Hint 2
In a sorted list, equal values sit next to each other. A value is new exactly when it differs from the last value you decided to keep.
Hint 3
Picture two fingers. One reads every entry from left to right. The other marks the next free spot in the cleaned-up front part of the list. The writing finger never gets ahead of the reading one.
Hint 4
Keep a write index w, starting at 0. For each read index r: if w is 0 or times[r] differs from times[w - 1], copy it to times[w] and add 1 to w. At the end, shorten the list to length w.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Split the list into two zones: a cleaned front part, times[0..w-1], holding each time once, and the unread rest. A read index r scans everything. Since the list is sorted, an entry is new exactly when it differs from the last kept one, times[w - 1].

Trace [365, 365, 410, 455, 455, 455, 520]:

r = 0, 365. Nothing kept yet, so keep it: slot 0 = 365, w = 1.
r = 1, 365. Same as the last kept value. Skip.
r = 2, 410. New: slot 1 = 410, w = 2.
r = 3, 455. New: slot 2 = 455, w = 3.
r = 4 and 5, both 455. Skip both.
r = 6, 520. New: slot 3 = 520, w = 4.

The list is now [365, 410, 455, 520, 455, 455, 520]. The first 4 slots are the answer and the rest is leftover. Cut the list to length 4: [365, 410, 455, 520].

Writing never overtakes reading (w ≤ r), so you never overwrite an entry you still need to read.

Reference solution

function dedupeBoard(times) {
  let w = 0; // next free slot in the cleaned front part
  for (let r = 0; r < times.length; r++) {
    if (w === 0 || times[r] !== times[w - 1]) {
      times[w] = times[r];
      w++;
    }
  }
  times.length = w; // cut off the leftover tail
}

def dedupe_board(times):
    w = 0  # next free slot in the cleaned front part
    for r in range(len(times)):
        if w == 0 or times[r] != times[w - 1]:
            times[w] = times[r]
            w += 1
    del times[w:]  # cut off the leftover tail

TimeO(n)One pass, and each entry is read once and written at most once.

SpaceO(1)Two indexes. The list is reused in place.

Learn the idea: Two Pointers Arrays

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code