DSA Tracker

Visualize

Missing And Repeating

The array indexes itself — signs as checkboxes

time O(n)space O(1)

The constraint that every value lies in 1..n is the whole gift: a value is also an address. Walk the array and, for each value v, flip the sign of cell v-1 to mean "v has been seen". A cell that is already negative when you reach it means its value arrived twice, and after the walk the one cell still positive names the value that never arrived. Reads take ABS so a cell the cursor has not visited yet can be marked safely. The sum-and-sum-of-squares identity solves the same problem without touching the input, but its squares overflow on large n; this trades that risk for temporarily scrambled signs.

Details

Animated on: A = [4,6,6,3,1,7,5] holds the numbers 1..7 with exactly one value repeated and one missing — find both.

Problem:Missing And RepeatingEasy

The array indexes itself — signs as checkboxes

step 1 / 11

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

A=[4,6,6,3,1,7,5] holds the numbers 1..7, one of them twice and one not at all. Every value is itself a legal index here — value v belongs in cell v-1 — so the array can carry its own bookkeeping: flipping cell v-1 negative records "v has been seen", and no second structure is needed.

Pseudocode
1FUNCTION repeatAndMissing(A)
2  FOR i <- 0 TO LENGTH(A) - 1
3    v <- ABS(A[i])
4    IF A[v - 1] < 0
5      repeat <- v
6    ELSE
7      A[v - 1] <- -A[v - 1]
8  FOR j <- 0 TO LENGTH(A) - 1
9    IF A[j] > 0
10      missing <- j + 1
11  RETURN repeat, missing

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. A=[4,6,6,3,1,7,5] holds the numbers 1..7, one of them twice and one not at all. Every value is itself a legal index here — value v belongs in cell v-1 — so the array can carry its own bookkeeping: flipping cell v-1 negative records "v has been seen", and no second structure is needed.
  2. A[0] is 4, so the value seen is 4 and its home is cell 3. That cell was 3 and is now -3: only the sign moved, the magnitude 3 is untouched — which is exactly why every read starts with ABS, and why marking a cell the scan has not reached yet is harmless.
  3. A[1] is 6, so the value seen is 6 and its home is cell 5. That cell was 7 and is now -7: only the sign moved, the magnitude 7 is untouched — which is exactly why every read starts with ABS, and why marking a cell the scan has not reached yet is harmless.
  4. A[2] carries value 6, but cell 5 is already -7 — an earlier element flipped it, so this is the SECOND arrival of 6. That makes 6 the repeated number, and nothing is flipped this time so the tally stays honest.
  5. A[3] is -3, so the value seen is 3 and its home is cell 2. That cell was 6 and is now -6: only the sign moved, the magnitude 6 is untouched — which is exactly why every read starts with ABS, and why marking a cell the scan has not reached yet is harmless.
  6. A[4] is 1, so the value seen is 1 and its home is cell 0. That cell was 4 and is now -4: only the sign moved, the magnitude 4 is untouched — which is exactly why every read starts with ABS, and why marking a cell the scan has not reached yet is harmless.
  7. A[5] is -7, so the value seen is 7 and its home is cell 6. That cell was 5 and is now -5: only the sign moved, the magnitude 5 is untouched — which is exactly why every read starts with ABS, and why marking a cell the scan has not reached yet is harmless.
  8. A[6] is -5, so the value seen is 5 and its home is cell 4. That cell was 1 and is now -1: only the sign moved, the magnitude 1 is untouched — which is exactly why every read starts with ABS, and why marking a cell the scan has not reached yet is harmless.
  9. Cell 0 is -4, negative, so value 1 was claimed during the first pass and is present. Keep walking — exactly one cell can survive unflipped.
  10. Cell 1 is still positive (6): across the whole first pass nothing ever claimed it, so the value 2 never appeared anywhere in the array. That is the missing number — read the cell's POSITION, not its contents, because 6 is just leftover input data that happens to sit here.
  11. Two passes, no extra memory: 6 is repeated — caught at index 2, its second arrival — and 2 is missing, named by the one cell nothing flipped. The array is left carrying flipped signs, so a caller that needs the input intact pays one more pass taking ABS of every cell: a real cost worth naming, since the sum-and-sum-of-squares alternative leaves the input alone but can overflow on large n.

Now solve it yourself

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

Solve Missing And Repeating in the editorAll Arrays problemsBack to roadmap