Problem

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

OR

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:

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

Example 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:

  1. Traverse the array.
  2. For each element at index i, negate the element at index nums[i] if it is not already negative.
  3. 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

Java
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]
    }
}
Python
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)