Detecting Duplicates with Sets

Welcome to the second module of the course. Having established a framework for algorithmic reasoning, we'll now begin building your toolbox of specific patterns. This module focuses on solving problems efficiently using arrays, strings, and hash-based data structures, which are fundamental in technical interviews.

Today's lesson addresses a foundational problem: detecting duplicates. The main goal is to learn how to use a Set to check for previously seen values in a single pass. As an experienced JavaScript developer, you're certainly familiar with Set, Map, and Object. Our focus here will be to analyze these structures through an algorithmic lens—specifically, how their performance characteristics allow us to write code that is not just correct, but also highly efficient.

The Problem: Contains Duplicate

Let's start with a classic interview problem, often presented as LeetCode #217, "Contains Duplicate":

Given an integer array nums, return true if any value appears at least twice in the array, and false if every element is distinct.

For example:

• [1, 2, 3, 1] -> true (because 1 appears twice)
• [1, 2, 3, 4] -> false (all elements are unique)
• [1, 1, 1, 3, 3, 4, 3, 2, 4, 2] -> true (multiple duplicates exist)

Before trying to find the best solution, consider the most direct, brute-force approach. How would you check for duplicates using nested loops? Think about the time complexity.

The video below explains this initial thought process.

An $O(n^2)$ solution involves comparing every element with every other element. For an input of size $10^5$ (a common constraint in these problems), this would mean around $10^{10}$ operations, which is far too slow. The bottleneck is clear: for each element, we are re-scanning the rest of the array to find a match. The core question we're repeatedly asking is, "Have I seen this number before?"

How can we answer that question more efficiently? Instead of searching the input array over and over, we can use a data structure optimized for fast lookups.

The Power of Fast Lookups with Set

In JavaScript, several data structures can store and retrieve data. Let's look at their properties from an algorithmic perspective.

As the table shows, while an array's .includes() method is easy to use, its performance is $O(n)$ because it may have to scan the entire array. In contrast, Set, Map, and Object offer $O(1)$, or constant-time, average lookups. This means that, on average, the time it takes to check for an element's existence doesn't depend on the number of items in the collection.

A Set is perfectly suited for our problem for two reasons:

1. It stores only unique values.
2. It provides a .has() method that checks for the existence of an element in average $O(1)$ time.

This combination allows us to design a new algorithm that processes the array in a single pass.

The "Seen Set" Algorithm:

1. Initialize an empty Set, which we'll call seen.
2. Iterate through the input array nums from left to right.
3. For each num in nums:
   • Check if seen.has(num).
   • If it does, you've found a duplicate. You can immediately return true.
   • If it doesn't, add the number to the set: seen.add(num). This records that you've now encountered this number.
4. If the loop completes without finding any duplicates, it means all elements were unique. Return false.

This image illustrates the process. As we iterate through the input [5, 3, 7, 3, 8, 1], we add each new number to the Hash Set. When we encounter the second 3, the set already contains 3, so we've found our duplicate.

The following video provides a clear, dynamic walkthrough of this exact logic.

Implementation and Complexity

Now, let's turn this logic into code. The following resource provides a clean implementation in TypeScript and analyzes its efficiency.

As the article explains, this algorithm has:

• Time Complexity: $O(n)$. We iterate through the array of n elements once. Each set operation (.has() and .add()) is $O(1)$ on average.
• Space Complexity: $O(n)$. In the worst-case scenario (an array with no duplicates), our seen set will grow to contain all n elements from the input array.

This is a classic time-space tradeoff. We use extra memory (the set) to reduce our time complexity from a quadratic $O(n^2)$ to a much faster linear $O(n)$.

An Elegant Alternative

Given your deep experience with JavaScript, you'll appreciate that the language often provides concise ways to express common patterns. Since a Set can be constructed directly from an iterable (like an array), we can find a duplicate by comparing the size of the resulting set with the length of the original array.

function containsDuplicate(nums: number[]): boolean {
  const uniqueElements = new Set(nums);
  return uniqueElements.size < nums.length;
}

This works because new Set(nums) automatically discards all duplicate values. If any duplicates were present in nums, the resulting set's size will be smaller than the original array's length.

This approach is explored in the following video, which contrasts the iterative map/set approach with this more direct one.

Both the iterative method and the Set constructor method have the same time and space complexity, but the latter is often preferred in code golf or when clarity isn't sacrificed. For an interview, being able to explain both is ideal. The iterative "seen set" approach is more fundamental and demonstrates the underlying step-by-step logic, which is a crucial skill.

Key Takeaways

• The "Contains Duplicate" problem is a classic entry point for using hash-based data structures.
• The brute-force $O(n^2)$ solution is too slow for typical constraints. The bottleneck is the repeated linear search to answer "have I seen this before?".
• A Set provides average $O(1)$ time for both insertions (.add()) and lookups (.has()), making it the ideal tool to optimize this check.
• The "seen set" pattern involves iterating through a collection while using a set to keep track of elements encountered so far. This is a fundamental pattern you will use often.
• This pattern improves time complexity to $O(n)$ at the cost of $O(n)$ auxiliary space—a very common and worthwhile tradeoff in algorithmic problems.

In our next lesson, we will build on this idea. Instead of just checking if we've seen a value before, we'll want to count how many times we've seen it. This will lead us to the "frequency counting" pattern, which typically involves using a Map or a plain Object.