DSA Tracker

Visualize

Missing And Repeating (Arrays)

Cyclic placement — send every value to its own index

time O(n)space O(1)

Values are 1..n and indices are 0..n-1, so value v has one obvious home: cell v-1. Walk the array and keep swapping the value under the cursor into its home; the cursor only advances once the value sitting there is already home, or once home is blocked by an identical value. That block is the duplicate announcing itself. When the placement pass ends, exactly one cell disagrees with A[k] = k+1, and it names both answers at once: the value it holds is the repeated one, and its own position plus one is the missing one. Sign-marking solves the same problem in the same bounds and leaves magnitudes intact; this method scrambles the order instead, which is the right trade only when the caller does not need the input back.

Details

Animated on: A = [3,1,2,5,4,6,6] should hold 1..7 but one value repeats and one is absent — find both.

Problem:Missing And Repeating (Arrays)Easy

Cyclic placement — send every value to its own index

step 1 / 13

3
[0]
1
[1]
2
[2]
5
[3]
4
[4]
6
[5]
6
[6]

A=[3,1,2,5,4,6,6] should be a permutation of 1..7, but one value shows up twice and one never shows up. Because every legal value v has exactly one home — cell v-1 — the array can be sorted by PLACEMENT rather than comparison: keep sending each value home and the two anomalies fall out of the one cell that stays wrong.

Pseudocode
1FUNCTION findMissingAndRepeating(A)
2  i <- 0
3  WHILE i < LENGTH(A)
4    home <- A[i] - 1
5    IF A[i] != A[home]
6      SWAP A[i] AND A[home]
7    ELSE
8      i <- i + 1
9  FOR j <- 0 TO LENGTH(A) - 1
10    IF A[j] != j + 1
11      RETURN A[j], j + 1

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. A=[3,1,2,5,4,6,6] should be a permutation of 1..7, but one value shows up twice and one never shows up. Because every legal value v has exactly one home — cell v-1 — the array can be sorted by PLACEMENT rather than comparison: keep sending each value home and the two anomalies fall out of the one cell that stays wrong.
  2. A[0] held 3, whose home is cell 2, and that cell held 2 — a different value, so the swap is productive: 3 lands home for good and 2 comes back to index 0 to be dealt with next. The cursor does NOT advance, because the value now under it has not been placed yet.
  3. A[0] held 2, whose home is cell 1, and that cell held 1 — a different value, so the swap is productive: 2 lands home for good and 1 comes back to index 0 to be dealt with next. The cursor does NOT advance, because the value now under it has not been placed yet.
  4. A[0] is 1 and its home is cell 0 — that is this very cell, so 1 is already where it belongs. Nothing to move, so the cursor advances to 1.
  5. A[1] is 2 and its home is cell 1 — that is this very cell, so 2 is already where it belongs. Nothing to move, so the cursor advances to 2.
  6. A[2] is 3 and its home is cell 2 — that is this very cell, so 3 is already where it belongs. Nothing to move, so the cursor advances to 3.
  7. A[3] held 5, whose home is cell 4, and that cell held 4 — a different value, so the swap is productive: 5 lands home for good and 4 comes back to index 3 to be dealt with next. The cursor does NOT advance, because the value now under it has not been placed yet.
  8. A[3] is 4 and its home is cell 3 — that is this very cell, so 4 is already where it belongs. Nothing to move, so the cursor advances to 4.
  9. A[4] is 5 and its home is cell 4 — that is this very cell, so 5 is already where it belongs. Nothing to move, so the cursor advances to 5.
  10. A[5] is 6 and its home is cell 5 — that is this very cell, so 6 is already where it belongs. Nothing to move, so the cursor advances to 6.
  11. A[6] is 6, so it wants cell 5 — but cell 5 already holds 6. Home is taken by an identical value, so swapping would loop forever; that stalemate IS the duplicate being caught. Leave 6 stranded at index 6 and move on.
  12. Placement is finished, so now read the array as a checklist. Cells 0..5 each satisfy A[k] = k+1 — values 1,2,3,4,5,6 all reached their homes — so none of them is missing or repeated. Skip past them.
  13. Cell 6 holds 6 instead of 7 — the one cell that disagrees, and it answers both halves at once. 6 is the repeated value: its second copy had nowhere of its own to go, so it stalled here. 7 is the missing value: this cell is its home and nothing ever came to claim it.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Missing And Repeating (Arrays) in the editorAll Arrays problemsBack to roadmap