442. Find All Duplicates in an Array using Javascript on Leetcode | DSA with JS

In this blog, we will solve the problem [Find All Duplicates in an Array][https://leetcode.com/problems/find-all-duplicates-in-an-array/description/].

The problem

Given an integer array of 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 appear twice.

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

Example:

Example 1:

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

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

Input: nums = [1]
Output: []

Approach

The nums array value range will [1,n] where n is the length. This means the smallest value will be 1 and the largest value will be n. For instance, in the first example, the smallest number is 1, and the biggest number is 8 which is also the length.

We can use this information to our advantage. We also know that the index range of an array is [0,n-1].

This means that every value in the array i - 1 can be used as an index.

Let's use this as an example: [4,3,2,7,8,2,3,1]
For the first value 4 in the array, we can use 4 - 1= 3 as an index to access the value at that index. The value is 7. We can use this value to mark the value at index 3 as negative. This way we can keep track of the values we have seen.

Let's do the same thing for the second number 3. We can use 3 - 1 = 2 as an index to access the value at that index. The value is 2. So, we will make that number negative. In this way, if we ever get directed to a negative number, this means that the current number is a duplicate number.

In the example, we have 3 as a duplicate number. In both instances, they will point to the same index which index 2. So, we can add 3 to the output array.

I recommend checking the video for a better understanding. It will help you understand the problem better.

Pseudo Code

• Create an empty array output
• Loop through the nums array
  • Get the absolute value of the current number
  • Get the index of the current number and subtract 1
  • Get the value at the index
  • If the value at the index is negative,
  • Add the current number to the output array
  • Else:
  • Make the value at the index negative
• Return the output array

Code

var findDuplicates = function (nums) {
    const output = []

    nums.forEach(num => {
        const curr = Math.abs(num)
        const index = curr - 1
        const indexedValue = nums[index]

        if (indexedValue < 0) {
            output.push(curr)
        } else {
            nums[index] = indexedValue * -1
        }
    })

    return output
}

That's it for today.