Missing And Repeating (Arrays)
An easy Arrays interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Arrays
- Sheets
- 2
- Core for
- 26 roles
The problem
Given an array of size n containing numbers from 1 to n, one number is missing and one appears twice. Find both.
Example 1
- Input
- [1,2,2,4]
- Output
- missing=3, repeating=2
Example 2
- Input
- [3,1,3,4]
- Output
- missing=2, repeating=3
Example 3
- Input
- [1,5,3,2,2]
- Output
- missing=4, repeating=2
Constraints
- 2 <= n <= 10^5
- 1 <= arr[i] <= n
How to think about it
Updated 2026-09-29Because every expected integer falls in [1, n], each value can be regarded as an address pointing to a cell inside the array itself. Stepping through the values and placing each one into its home position arr[val - 1] via cyclic swaps routes every number to its natural seat, immediately exposing which seat has a duplicate occupant and which sits empty.
Approaches, worst first
Boolean visited array
time O(n) · space O(n)
Maintain a boolean array of length n + 1 initialized to false. Mark seen values on a first pass to identify the duplicate, then scan the boolean array to find the unmarked index representing the missing number. Requires O(n) supplementary memory.
Index sign inversion
time O(n) · space O(1)
For each number, flip the sign of the value at index abs(val) - 1. If that slot is already negative, abs(val) is the repeating number. In a second pass, the single index that remains positive reveals the missing number without auxiliary memory allocations.
Cyclic placement swapWrite this one
time O(n) · space O(1)
While arr[i] != arr[arr[i] - 1], swap arr[i] with the element at its target index. Once every possible number is parked at arr[i] == i + 1, a single linear sweep flags the mismatched position where arr[i] is the duplicate and i + 1 is missing.
Where people lose marks · 3
- In the sign-inversion approach, forgetting to use `abs(arr[i])` when determining the target index will attempt to access negative indices and crash.
- In cyclic sort, failing to check `arr[i] != arr[arr[i] - 1]` before swapping leads to an infinite loop when duplicate values encounter each other.
- Confusing 0-based array indices with 1-based numerical values introduces an off-by-one error on the missing number output.
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
More Arrays problems
Target Roles
Core requirement for 26 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .