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.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.
This Python solution iterates through the list, converting the number at the index derived from each element into its negative. If an index points to an already negative number, it indicates the presence of a duplicate, and hence, the number is added to the duplicates list.
C
C++
Java
C#
JavaScript
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.
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.
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.
C
C++
Java
C#
JavaScript
Time Complexity: O(n) due to swapping.
Space Complexity: O(1) as no extra space except for output.
| Approach | Complexity |
|---|---|
| Negation Marking | Time Complexity: O(n) as it traverses the list once. |
| Index-Based Value Reordering | Time Complexity: O(n) due to swapping. |
Find the Duplicate Number - Floyd's Cycle Detection - Leetcode 287 - Python • NeetCode • 342,283 views views
Watch 9 more video solutions →Practice Find All Duplicates in an Array with our built-in code editor and test cases.
Practice on FleetCode