Find The Duplicate Number!

Leetcode is a must for us engineers these days. Will you encounter it in EVERY software engineering interview? Probably not. Will you encounter DS&A (Data Structures and Algorithms) to some degree in most? Probably.

Here, I will give you two quick explanations (with code), to solving a medium problem -- Find The Duplicate Number.

It asks for O(1) space, but that solution is far more complicated. Our job is not to memorize complicated algorithms like the tortoise and the hare, but to solve problems that need to be solved. Most of the time, space is not an issue... so let's go ahead and solve this!

Using a Set

Sets are simple, yet powerful. It is a collection of UNIQUE items. Sets are treated as their own object in JavaScript, and can be invoked with new Set(). Sets are also based on HashMaps, which provide a constant lookup time. This makes sure they don't add time to the problem.

const findDuplicate = function(nums) {
    const mySet = new Set();

    for (let i = 0; i < nums.length; i++) {
        if (mySet.has(nums[i])) {
            return [nums[i]];
        } else {
            mySet.add(nums[i]);
        }
    }
};

So first off, we create a new set that will hold all our unique numbers. Then, a for loop will go through and check if the Set has the value. Lucky for us, JavaScript has the built-in method .has() that checks if the Set contains the value, and returns a boolean. If the Set has the value, this means we have encountered the value before and found our duplicate value! Our solution falls into O(n) time because of the for loop, and the Set requires O(n) space.

Sorting and Being Clever

Sorting algorithms are an entire branch on their own. There are many different types of them, and JavaScript Arrays have their own built-in sort method. The best sorting algorithms can really do is O(n * logn) time, which is already worse than our previous method. However, this takes constant space, O(1), so it's a tradeoff... but you're still probably better off using the Set method as time is nearly always more important than space.

const findDuplicate = function (nums) {
    nums.sort(); // O (n * log n)!

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            return nums[i];
        }
    }
};

Let's take an example array: [3, 1, 2, 3]. After sorting, we have [1, 2, 3, 3]. Now, we know that if we have a duplicate, they'll be right next to each other! Hence, the threes are now adjacent to each other at the end of the array. Now, when we run our for loop, we compare our value to the previous value to see if there is a match.

On the first run, you have 1 checked against undefined. Then 2 compared to 1. Then 3 compared to 2. And finally, we find our duplicate value on the last iteration when 3 is compared to 3! Mwahaha. It's a fun, cheeky solution.

Thanks for reading!

NOTE: You may be tempted to say the last algorithm's time complexity is O(n * n * log n). This could be inferred from the sorting algorithm taking O(n * logn) time, and the loop taking O(n) time. However, this actually results in O((n * logn) + n) time, which just shortens to O(n * logn) time as the extra loop is not considered in Big O notation.