Find duplicates in O(n) time
Filed under Zoho
Free read 2 of 3Check if modifying the input array in-place is permitted to achieve O(1) space.
The question
Given an array of size n containing elements from 0 to n-1, find all duplicate elements in O(n) time and O(1) extra space.
Constraints
- Array elements are in the range [0, n-1]
- Time complexity must be O(n)
- Auxiliary space complexity must be O(1)
Examples
- Input
- nums = [1, 2, 3, 1, 3]
- Output
- [1, 3]
- Why
- 1 and 3 appear more than once in the array.
Approach
Check if modifying the input array in-place is permitted to achieve O(1) space.
Use nested loops to check frequency of each element, taking O(n^2) time.
Use the array indices as hash keys. Iterate through the array, take the absolute value of the element at index `abs(nums[i])`, and if it's negative, `abs(nums[i])` is a duplicate. Otherwise, negate the value at that index.
Array with all identical elements; empty array.
Tips
- What they are testing: Test arrays with multiple duplicates, single duplicate, and no duplicates.
- Common mistake: Modifying the array destructively if modification is not allowed, or failing to handle multiple duplicate counts cleanly.
Related Zoho questions
Collected from public candidate posts and coding forums. Updated Nov 2026.