Find all duplicates in an array Time (O(n)) & Space( O(1))


  • 1
    R

    Since the input of the array is from range 1 to N, we can map each element to its correct index and mark that index. If a number is repeated twice or more than twice then the respective index is already marked. We can push all the elements that are already marked to the result array.

    vector<int> findDuplicates(vector<int>& nums) {
            std::vector<int> result;
            const int size = nums.size();
            for(int i=0; i< size; ++i){
                if(nums[abs(nums[i]) - 1] < 0){
                    result.push_back(abs(nums[i]));
                }
                else{
                    nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
                }
            }
            return result;
        }
    

    Time Complexity: Since we traverse each element of an array only once the time complexity of the solution is O(n).

    Space Complexity: O(1) no extra space is used.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.