Find All Duplicates in an Array | Array |Data Structure

CODE:

 

class Solution {
public:
      vector<int> findDuplicates(vector<int>& nums) {

           vector<int>output;

           for(int i =0;i<nums.size();i++){
                     int index = abs(nums[i]) – 1;
                     if(nums[index] < 0) output.push_back(index+1);

                     nums[index] = -nums[index];
                }

           return output;

       }
};

EXPLANANTION:

The constraint is that the values present in the input array range from 1 to the length of the array i.e. for each value that an element can have in the array we have a possible index = number -1. So, we can keep track of the numbers that have been seen while iteration by making the value at the corresponding index as negative.

int index = abs(nums[i]) – 1;
nums[index] = -nums[index];

 

And if the value present at a particular index is already negative, we know that it has been repeated, hence, we add it to our output array.

if(nums[index] < 0) output.push_back(index+1);

Leave a Reply

Your email address will not be published. Required fields are marked *