Find All Duplicates in an Array - LeetCode Daily Challenge

Problem Statement

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2

Input: nums = [1,1,2]
Output: [1]

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        
        List<Integer> answer = new ArrayList<>();

        for(int num : nums) {
            nums[Math.abs(num) - 1] *= -1;
        }

        for(int num : nums) {
            if(nums[Math.abs(num) - 1] > 0) {
                answer.add(Math.abs(num));
                nums[Math.abs(num) - 1] *= -1;
            }
        }

        return answer;
        
    }
}

C++ Code

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

        for (int num : nums) {
            nums[abs(num) - 1] *= -1;
        }

        for (int num : nums) {
            if (nums[abs(num) - 1] > 0) {
                answer.push_back(abs(num));
                nums[abs(num) - 1] *= -1;
            }
        }

        return answer;
    }
};

Python Code

class Solution:
    def findDuplicates(self, nums):
        answer = []

        for num in nums:
            nums[abs(num) - 1] *= -1

        for num in nums:
            if nums[abs(num) - 1] > 0:
                answer.append(abs(num))
                nums[abs(num) - 1] *= -1

        return answer

Javascript Code

var findDuplicates = function(nums) {
    const answer = [];

    for (let num of nums) {
        nums[Math.abs(num) - 1] *= -1;
    }

    for (let num of nums) {
        if (nums[Math.abs(num) - 1] > 0) {
            answer.push(Math.abs(num));
            nums[Math.abs(num) - 1] *= -1;
        }
    }

    return answer;
};

Go Code

func findDuplicates(nums []int) []int {
    answer := make([]int, 0)

    for _, num := range nums {
        nums[abs(num)-1] *= -1
    }

    for _, num := range nums {
        if nums[abs(num)-1] > 0 {
            answer = append(answer, abs(num))
            nums[abs(num)-1] *= -1
        }
    }

    return answer
}

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(1)