Find duplicates in an array of integers within range 0 to n-1

Problem

Given an array of integers in range [0, n-1), find out duplicates in it. where n is the length of the array.

Given an array of n elements which contains elements ranging from 0 to n-1, where any of these numbers can appear multiple times, find the repeating numbers in O(n) time using only constant memory space.

Examples

Example 1:

1
2


Input: nums = [4, 6, 2, 1, 2, 5]
Output: 2

Example 2:

1
2


Input: nums = [1, 6, 5, 2, 3, 3, 2]
Output: [2, 3]

Solution

We have already seen the solutions at Find duplicates in a given array. We can see method1, method2 and method3 already. But this is a special case, so we can do better.

Method 4 - Using array index and negation

Since the array elements range between 0 and n-1, we can use the array indices to track duplicates.

This approach works for arrays with positive integers where all elements are between 0 and n-1, where n is the array size.

Here are the steps:

Traverse the array.
For each element at index i, negate the element at index nums[i] if it is not already negative.
If an element at index nums[i] is already negative, it indicates a duplicate.

Note:

This method does not handle arrays containing 0. To manage this, replace 0 with INT_MIN while traversing. If INT_MIN is encountered, it means 0 is duplicated in the array.

Similar approach used in problem : If array has all consecutive numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        for (int num : nums) {
            int index = Math.abs(num);  // Use the value as index
            if (nums[index] < 0) {  // If the value at this index is already negative, it's a duplicate
                duplicates.add(index);
            } else {
                nums[index] = -nums[index];  // Negate the value at this index to mark it as visited
            }
        }
        return duplicates;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] nums1 = {2, 3, 1, 0, 2, 5, 3};
        System.out.println("Duplicates in the array are: " + solution.findDuplicates(nums1));  // Output: [2, 3]

        int[] nums2 = {0, 3, 1, 2, 2};
        System.out.println("Duplicates in the array are: " + solution.findDuplicates(nums2));  // Output: [2]

        int[] nums3 = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println("Duplicates in the array are: " + solution.findDuplicates(nums3));  // Output: [2, 3]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def findDuplicates(self, nums):
        duplicates = []
        for num in nums:
            index = abs(num)  # Use the value as index
            if nums[index] < 0:  # If the value at this index is already negative, it's a duplicate
                duplicates.append(index)
            else:
                nums[index] = -nums[index]  # Negate the value at this index to mark it as visited
        return duplicates

# Example usage
solution = Solution()
nums1 = [2, 3, 1, 0, 2, 5, 3]
print(f"Duplicates in the array are: {solution.findDuplicates(nums1)}")  # Output: [2, 3]

nums2 = [0, 3, 1, 2, 2]
print(f"Duplicates in the array are: {solution.findDuplicates(nums2)}")  # Output: [2]

nums3 = [4, 3, 2, 7, 8, 2, 3, 1]
print(f"Duplicates in the array are: {solution.findDuplicates(nums3)}")  # Output: [2, 3]

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 4 - Using array index and negation#

Code#

Complexity#