Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]
Example 2:
Input: nums = [1,1,2] Output: [1]
Example 3:
Input: nums = [1] Output: []
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= nnums appears once or twice.The goal of this problem is to identify all elements that appear more than once in an array. A straightforward method is to use a Hash Set or Hash Map to track numbers that have already been seen. As you iterate through the array, check whether the current value already exists in the set. If it does, it is a duplicate. This approach is simple and easy to implement but requires extra memory.
A more optimized strategy takes advantage of the constraint that numbers typically fall within the range 1..n. By using the array itself for bookkeeping, you can mark visited indices by flipping the sign of the value at the corresponding index. If you encounter an index that is already marked, it indicates a duplicate. This in-place marking technique avoids additional data structures and achieves constant extra space.
Both methods run in linear time, but the in-place approach is considered the most space-efficient for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set / Hash Map | O(n) | O(n) |
| In-place Sign Marking | O(n) | O(1) |
NeetCode
Negation Marking: This approach leverages the integer constraints (1 to n) to use the input array itself to track occurrences. Every time an index is visited based on an element's value, we negate the number at that index if it's positive. If we encounter that index again and the number is already negative, it means the number corresponding to this index has been seen before.
Time Complexity: O(n) as it traverses the list once.
Space Complexity: O(1) as it uses no additional space apart from the output list.
1#include <vector>
2#include <cmath>
3
4std::vector<int> findDuplicates(std::vector<int>& nums) {
5 std::vector<int> duplicates;
6 for (int i = 0; i < nums.size(); ++i) {
7 int index = abs(nums[i]) - 1;
8 if (nums[index] < 0) {
9 duplicates.push_back(abs(nums[i]));
10 } else {
11 nums[index] = -nums[index];
12 }
13 }
14 return duplicates;
}The C++ code makes use of the standard vector library to store the duplicates. We iterate over the array using index manipulations similar to the Python code.
Index-Based Value Reordering: In this approach, we aim to place each number at the position corresponding to its value. If a position already holds the correct number, it signifies a duplicate, since we're attempting to place a number in its designated index. This allows us to directly identify duplicates while keeping the array order in check.
Time Complexity: O(n) due to swapping.
Space Complexity: O(1) as no extra space except for output.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The trick works because each value corresponds to a valid index in the array. By marking the value at that index as visited, the algorithm can detect when the same index is encountered again, which signals a duplicate.
Yes, this problem or its variations frequently appear in technical interviews at large tech companies. It tests understanding of arrays, hashing, and space optimization techniques.
A hash set or hash map is the most intuitive data structure for detecting duplicates because it allows constant-time lookups. However, if the problem constraints allow values within a fixed range like 1..n, an in-place array marking technique is more space efficient.
The optimal approach uses the array itself to mark visited numbers by modifying the sign of elements at indexed positions. When the same index is encountered again and already marked, it indicates a duplicate. This method runs in O(n) time and uses O(1) extra space.
This Python solution places each number at its correct index (e.g., 1 at index 0). If a correct position is already occupied by the number, a duplicate is detected.