Find All Duplicates in an Array LeetCode Solution

Problem Statement

The problem, Find All Duplicates in an Array LeetCode Solution states that you are given an array of size n containing elements in the range [1,n]. Each integer can appear either once or twice and you need to find all the elements that appear twice in the array.

Examples for Find All Duplicates in an Array LeetCode Solution

Test Case 1 –

Input – [4, 3, 2, 7, 8, 2, 3, 1]

Output – [2, 3]

Test Case 2 –

Input – [1, 1, 2]

Output – [1]

Test Case 3 –

Input – [1]

Output – []

Approach

Idea

1. The first catch in the question is that the numbers present in the array are from 1 to n inclusive, where n is the size of the array. So we can do some manipulations on the indices of the array.
2. Consider the test case – [1, 2, 3, 4, 4]. The corresponding indices will be 0, 1, 2, 3, 3 i.e. nums[i] - 1.
3. As we traverse the array, we mark the index corresponding to that element. By marking, we mean nums[abs(nums[i])-1] = -1*nums[abs(nums[i])-1].
4. In the same traversal, if we encounter a negative element at some index, it means that the index has already been marked earlier and is a duplicate element. So we push that element (index) to the output array.

if an element x occurs just once in the array, the value at index abs(x)-1 becomes negative and remains so for all of the iterations that follow.

1. Traverse through the array. When we see an element x for the first time, we’ll negate the value at the index abs(x)-1.
2. But, the next time we see an element, we don’t need to negate it again! If the value at the index abs(x)-1 is already negative, we know that we’ve seen element x before.

Code for Find All Duplicates in an Array LeetCode Solution

C++

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        int n = nums.size();
        for(int i=0;i<n;i++){
            if(nums[abs(nums[i])-1] < 0) ans.push_back(abs(nums[i]));
            nums[abs(nums[i])-1] = -1*nums[abs(nums[i])-1];
        }
        return ans;
    }
};

JAVA

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        for(int i=0;i<n;i++){
            if(nums[Math.abs(nums[i])-1] < 0) ans.add(Math.abs(nums[i]));
            nums[Math.abs(nums[i])-1] = -1*nums[Math.abs(nums[i])-1];
        }
        return ans;
    }
}

Python

class Solution(object):
    def findDuplicates(self, nums):
        ans = []
        for i in nums:
            if nums[abs(i)-1] < 0:
                ans.append(abs(i))
            nums[abs(i)-1] = -1*nums[abs(i)-1]
        return ans
        """
        :type nums: List[int]
        :rtype: List[int]
        """

Complexity Analysis for Find All Duplicates in an Array LeetCode Solution

Time Complexity

Since we are traversing the array only once, the time complexity for the approach is O(n).

Space Complexity

We are not using any auxiliary space in the algorithm, so the space complexity is O(1).