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

  • 1

    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){
                    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.