Solution For Find All Duplicates In An Array

Problem Statement:

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example 1:

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

Output:
[2,3]

Solution:

The idea is to mark numbers as visited by negating the value of that index. For example, if we encounter the value 2, we will go to the index 2-1 and negate the value at that index. This will be our tentative visit of number 2. If we encounter the value 2 again, we will go to the index 2-1, see that the value is already negative, and mark that the number 2 has been seen again.

Now let’s look at the implementation.

Step 1: Loop over the array, and at each element, mark the value at index (element – 1) as negative.

Step 2: If we encounter a value again, that means we have seen it before and the index (element – 1) will have already been marked negative. We add the value to our result list.

Step 3: Return the result list.

Code:

class Solution {
public:
vector findDuplicates(vector& nums) {

    vector<int> result;

    for(int i = 0; i < nums.size(); ++i) {
        int index = abs(nums[i]) - 1;
        if(nums[index] < 0) {
            result.push_back(index+1);
        } else {
            nums[index] = -nums[index];   
        }
    }

    return result;
}

};

The time complexity of this solution is O(n) because we are looping over the array only once. The space complexity is O(1) because we are not using any additional space, except for the result list.

Step by Step Implementation For Find All Duplicates In An Array

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

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        # create an empty list to store the duplicates
        duplicates = []
        
        # go through each number in the list
        for num in nums:
            # if the number is negative, make it positive 
            # (this is because the list is 1-indexed)
            if num < 0:
                num = -num
                
            # if the number at the index of the number is negative, 
            # it means that the number has been visited before
            if nums[num-1] < 0:
                # so add it to the list of duplicates
                duplicates.append(num)
            else:
                # otherwise, mark the number at the index of the number as negative
                # to indicate that it has been visited
                nums[num-1] = -nums[num-1]
                
        # return the list of duplicates
        return duplicates

//Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

//Find all the elements that appear twice in this array.

//Could you do it without extra space and in O(n) runtime?

//Example:
//Input:
//[4,3,2,7,8,2,3,1]

//Output:
//[2,3]

var findDuplicates = function(nums) {
    let output = [];
    
    for (let i = 0; i < nums.length; i++) {
        let index = Math.abs(nums[i]) - 1;
        
        if (nums[index] < 0) {
            output.push(Math.abs(index + 1));
        }
        
        nums[index] = -nums[index];
    }
    
    return output;
};

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

public class Solution {
    public IList FindDuplicates(int[] nums) {
        // Create a list to store the duplicates
        List duplicates = new List();
        
        // Iterate through the array
        for(int i = 0; i < nums.Length; i++) {
            // Get the absolute value of the current number
            // We do this because if the number has already been
            // marked as a duplicate, it will be negative
            int abs = Math.Abs(nums[i]);
            
            // Check if the number at the index abs - 1
            // is negative, meaning it has already been marked
            // as a duplicate
            if(nums[abs - 1] < 0) {
                // Add it to the list of duplicates
                duplicates.Add(abs);
            }
            else {
                // Otherwise, mark the number at the index
                // abs - 1 as negative to indicate that it
                // is a duplicate
                nums[abs - 1] *= -1;
            }
        }
        
        // Return the list of duplicates
        return duplicates;
    }
}