Leetcode Daily - August 6, 2020

Find All Duplicates In An Array

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - store seen numbers in a hash table

(Submission - Accepted)

I thought about using techniques such as sorting the array, with time complexity of O(nlog(n)), but decided to utilize hash tables which take virtually O(1) to retrieve values if given a key.

Since we are looking for duplicates, we only need to traverse the array once (in O(n) time) and check if we have seen a number before. If we haven't seen it, we add it to our hash table. If we have seen it, we add it to an array holding numbers we've identified as duplicates. Then we can return the array of duplicates to complete the function.

Javascript:

var findDuplicates = function(nums) {
    // use a hash table to store numbers we've seen 
    let hash = {}

    // now go through the array once 
    let dupes = [] 

    for (let i = 0; i < nums.length; i++) {
        if (hash[nums[i].toString()]) {
            // if it is a duplicate, add it to dupes
            dupes.push(nums[i])
        } else {
            // if it is not a duplicate, add it to hash 
            hash[nums[i].toString()] = true 
        }
    }

    return dupes
};

Attempt 2 - try and not use extra space for O(n) solution

(Submission - Accepted)

I tried to take advantage of the fact that the numbers are only integers between 1 and the length of the array, N. Therefore, it can map one to one with the indices of the array unless there are duplicates.

For example, the number 1 belongs in index 0, so the number k belongs in index k - 1.

1. I first create a container to hold duplicates.
2. I then iterate through the array.
   • If the number i is in index i-1, I leave it alone
   • If the number i is not in index i-1:
   • I check index i-1:
     • If index i-1 holds number i: this number i is a duplicate
     • If index i-1 doesn't hold number i, I swap the numbers so that i is now in index i-1
   • After the swap I check the current index again using the same criteria. I continue to swap until current index either:
     • Holds the right number
     • Is a dupe because index i-1 holds i
   • Finally, continue to next index and repeat i. and ii.

var findDuplicates = function(nums) {
    // try to match the numbers to index = nums[i]-1

    // now go through the array once 
    let dupes = [] 

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i+1) {
            // is the number in the right place? 
            // for example: 1 belongs in index 0
            // if so, ignore. if not, try to place all 
            // numbers in a chain correctly

            // nums[i] belongs in index nums[i]-1
            // try to put it in index nums[i]-1 
            let newIndex = nums[i]-1
            if (nums[newIndex] === nums[i]) { 
                if (!dupes.includes(nums[i])) {
                   dupes.push(nums[i]) 
                }
            } else {
                let temp = nums[i]
                nums[i] = nums[newIndex]
                nums[newIndex] = temp 
                i --
            }
        } 
    }

    return dupes
};

I may not be allowed to store the duplicates in an extra array if I wanted to meet the challenge of using no extra storage space as well as having O(n) time complexity. However, I would iterate through the array again and splice out any numbers that were not in their assigned positions (number k would be in index k-1) then return the spliced array.

Discussion and Conclusions

Using hash tables (in the case of Javascript, Objects) to quickly access data is a powerful tool that I was first introduced to in the first problem I ever tried on Leetcode, Two Sums. By using the hash table instead of a nested iterative loop, we can frequently reduce O(n²) tasks to O(n).

I still need to think about how to do this problem without using extra space. I tried to use the fact that all numbers integers from 1 to the length of the array, N. My implementation spent time during the for loop (O(n) operation) to reassign values to where they would be, and swapping places with the number in the correct position if it's not a duplicate. I think this approach is still O(n) because there aren't an infinite numbers to swap, since you would stop swapping if the number were in the right position.