287 Leetcode Solution using JavaScript

287. Find the Duplicate Number LeetCode Solution using JS

Let's look at the problem statement:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Some examples:

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

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

Naive Solution

Here is a simple solution using a Set to keep track of numbers seen:

var findDuplicate = function(nums) {
  const seen = new Set();

  for (let num of nums) {
    if (seen.has(num)) {
      return num;
    }
    seen.add(num); 
  }
}

We iterate through the input array once. For each number, we check if it exists in the Set. If so, we found the duplicate and returned it. Otherwise, we add it to the Set.

Time complexity is O(n) and space is O(n) for the Set.

Optimal Solution

We can optimize space usage by modifying the array in-place. The key insight is that we can use the sign of each number as a hashmap.

var findDuplicate = function(nums) {

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

}

We iterate through the array, taking the absolute value of each number as an index. If that index already has a negative value, it means we've seen this index before so it is a duplicate. Otherwise, we negate the value at that index to mark it as seen.

This uses the input array itself to track numbers seen so far. Time and space complexity are both optimal O(n).

Summary

This demonstrates how we can optimize solutions to use minimal extra space, modifying the input array if permitted by the problem. The optimal O(n) time and O(n) space solution is efficient and meets all problem constraints.