The Doubled and the Lost
EasyArrays & Hashing
Problem
A locker room has lockers 1 to n, and nums should list each locker number exactly once. A clerk made a single mistake: one number was written twice, which means another number is missing.
Return [doubled, missing]. Use O(1) extra space; you may modify nums.
Example 1
- Input:
- nums = [1, 2, 2, 4]
- Output:
- [2, 3]
2 appears twice and 3 never appears.
Example 2
- Input:
- nums = [1, 1]
- Output:
- [1, 2]
Example 3
- Input:
- nums = [3, 1, 3]
- Output:
- [3, 2]
Constraints
- 2 ≤ n = nums.length ≤ 10^4
- 1 ≤ nums[i] ≤ n
- Exactly one value is doubled and exactly one is missing.
Hint
Show the first hint
Every value v in 1..n has a natural home: index v - 1. Can the array remember which homes were visited?
Walkthrough
How to approach it
01Clarify before coding
- Is the array sorted? No.
- May I modify it? Yes, which enables the sign trick.
- Exactly one duplicate and one missing? Yes.
02Brute force
Count occurrences of each value 1..n with a nested loop, or with a hash map / counting array.
Cost: Nested loop: O(n²) time. Counting array: O(n) time but O(n) extra space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.