Coding Interview Questions | Contains Duplicate

January 4th, 2024

Contains Duplicate Problem Introduction:

This summary will talk about my solution to the contains duplicate problem as seen on leetcode here.

How do you solve the Contains Duplicate Problem in O(n) time?:

Solution:

function containsDuplicate(nums: number[]): boolean {
  const seenNumberSet = new Set<number>();

  for (const num of nums) {
    if (seenNumberSet.has(num)) {
      return true;
    }
    seenNumberSet.add(num);
  }

  return false;
}

Contains Duplicate Solution Summary:

Below is a breakdown of the key aspects of the solution above:

1. Set for Tracking Seen Numbers: The solution utilizes a Set data structure, named seenNumberSet, to keep track of unique numbers encountered during the iteration.
2. Iterative Check for Duplicates: The algorithm iterates through the given array (nums) and checks whether each number has been previously seen. If a number is found in the set, indicating a duplicate, the function returns true.
3. Updating the Set: If a number is not in the set, it is added to seenNumberSet, ensuring that the set contains distinct elements as the iteration progresses.

Complexities

1. Time Complexity: The time complexity of the solution is O(n), where n is the length of the input array. The algorithm iterates through the array once.
2. Space Complexity: The space complexity is O(n), as in the worst case, the set may store all unique elements from the array.