Paul SerbanSoftware Engineer

Contains Duplicate: A Deep Dive into Hash Sets, Sorting, and Algorithmic Trade-offsFrom `O(n^2)` Brute Force to `O(n)` Elegance - Solving LeetCode 217 Across Four Languages

Introduction

Few algorithmic problems reveal as much about a developer's instincts as "Contains Duplicate". On the surface, it is trivially simple: given an array of integers, return true if any value appears more than once. A junior engineer might stop at the first working solution, but a senior engineer sees the problem differently - as a lens through which to examine data structure selection, time-space trade-offs, and the practical limits of each approach at scale.

This problem, catalogued as LeetCode 217 and featured prominently in NeetCode's Roadmap, is a foundational exercise. It teaches you to reason about whether you can afford extra memory to buy faster lookups, whether sorting is worth the preprocessing cost, and how language-specific idioms can express intent more cleanly than raw algorithmic constructs. Understanding it deeply is not about memorizing an answer - it is about internalizing a decision-making framework that applies to much harder problems.

In this article we will work through multiple approaches in JavaScript, TypeScript, Python, and Bash, analyze their time and space complexities, and discuss when each is appropriate. We will also examine the engineering trade-offs that often go unmentioned in competitive programming circles.

Problem Overview and Constraints

LeetCode 217 - Contains Duplicate - is stated as follows: given an integer array nums, return true if any value appears more than once in the array, otherwise return false. The constraints specify that the array length can range from 0 to 10^5 and that each integer falls between -10^9 and 10^9.

These constraints are not cosmetic. An array of up to 100,000 elements rules out any O(n^2) approach in performance-sensitive systems. With n = 10^5, a brute-force nested-loop solution performs up to 10^10 comparisons in the worst case - well beyond the tolerance of any interactive or real-time system. The integer range is wide enough that you cannot use a simple boolean bitmap indexed by value without additional offset arithmetic; more importantly, the range rules out any assumption of small values that might otherwise allow counting sort or similar tricks.

The problem also presents a degenerate edge case worth noting: an empty array or single-element array can never contain duplicates, and any correct solution must handle these without crashing or returning a false positive. This matters in production code where defensive handling of edge cases is not optional.

Deep Technical Explanation

Why Brute Force Fails at Scale

The most intuitive approach - compare every element against every other element - runs in O(n^2) time. For each element at index i, you scan indices i+1 through n-1 looking for a match. This is straightforward to reason about and requires O(1) extra space, but it does not scale. At n = 10^5, a modern CPU executing roughly 10^8 simple operations per second would require approximately 100 seconds to process the worst case. This is unacceptable even for batch jobs, let alone interactive systems.

The deeper lesson here is that brute force is not a solution you "optimize later". It is a baseline that reveals what information you are failing to exploit. In this case, the opportunity is early termination - once you find one duplicate, you stop - but even with early termination, worst-case complexity remains quadratic. The real insight is that comparisons are the wrong primitive. You want membership queries, and the right data structure for membership queries is a hash set.

Hash Set: Trading Space for Time

A hash set (or hash table in its key-only form) provides O(1) amortized insert and O(1) amortized lookup. This is the key insight: if you maintain a set of values you have already seen, you can determine in constant time whether the current element is a duplicate. The overall algorithm then runs in O(n) time, performing a single pass through the array. The cost is O(n) auxiliary space, since in the worst case - a fully unique array - you store all n elements before concluding there are no duplicates.

In most practical scenarios this trade-off is entirely acceptable. Memory is cheap, and the performance gain from linear-time lookups over quadratic comparisons is enormous at scale. The hash set approach also has excellent cache locality compared to sorting-based approaches, because you access the set sequentially rather than performing scattered comparisons across a rearranged array.

Sorting: A Middle Ground

Sorting the array first and then scanning for adjacent equal elements runs in O(n log n) time and - depending on whether you sort in-place - O(1) or O(log n) auxiliary space (for the call stack in recursive sorts like Timsort or quicksort). This is asymptotically worse than the hash set approach but can be advantageous when memory is the binding constraint.

The sorting approach also has a useful property: it is deterministic. Hash tables have amortized O(1) operations, but worst-case behavior for hash tables with poor hash functions degrades to O(n) per operation due to collision chains. In adversarial inputs or security-sensitive contexts, a deterministic O(n log n) algorithm can be preferable to a probabilistic O(n) one. Python's sorted() uses Timsort, which is O(n log n) worst case with proven stability guarantees - a known quantity.

Implementation and Practical Examples

JavaScript

JavaScript's Set object provides O(1) average-case add and has operations, making it the natural choice for the hash set approach. The implementation is concise and idiomatic:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function containsDuplicate(nums) {
  const seen = new Set();
  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

This function iterates the array once, performing a membership test and an insert at each step. The for...of loop is idiomatic modern JavaScript, and early return on the first duplicate avoids unnecessary work. The Set constructor also allows a one-liner alternative: return new Set(nums).size !== nums.length, which constructs the set from the array and compares sizes. This is elegant for competitive programming but creates the full set before making any determination, sacrificing early-exit optimization. In production code where large arrays are common, the explicit loop with early return is preferable.

A sorting-based alternative in JavaScript looks like this:

function containsDuplicateSort(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) return true;
  }
  return false;
}

Note the spread operator [...nums] to avoid mutating the input - a critical discipline in production code where the original array may be referenced elsewhere. The comparator (a, b) => a - b is required for numeric sort; JavaScript's default .sort() sorts lexicographically, which would incorrectly order numbers like [10, 9, 2] as [10, 2, 9].

TypeScript

TypeScript adds static type annotations without changing the algorithmic logic. The value here is communication - function signatures become contracts that the compiler enforces:

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

For production TypeScript, you might also consider a more defensive variant that validates input shape at runtime - though for this problem, the compiler's type system handles it:

function containsDuplicateGuarded(nums: readonly number[]): boolean {
  if (nums.length <= 1) return false;
  const seen = new Set<number>();
  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

Using readonly number[] signals that the function promises not to mutate the input - an important contract in functional-style TypeScript codebases. The early return for arrays of length 0 or 1 is a micro-optimization that avoids any heap allocation in those cases; in high-throughput pipelines processing millions of short arrays, this matters.

Python

Python's built-in set type is implemented as a hash table and provides the same O(1) amortized operations as JavaScript's Set. Python also offers particularly elegant set-based idioms:

from typing import List

def contains_duplicate(nums: List[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Python's in operator on a set is O(1) amortized, making this equivalent in complexity to the JavaScript version. The one-liner version - return len(set(nums)) != len(nums) - is idiomatic Python and commonly accepted in code reviews, though it again sacrifices early exit.

Python also allows an interesting approach using the Counter class from collections:

from collections import Counter
from typing import List

def contains_duplicate_counter(nums: List[int]) -> bool:
    counts = Counter(nums)
    return any(v > 1 for v in counts.values())

Counter builds a frequency map in O(n) time. This is semantically clear and useful when you need the duplicate count for downstream logic (e.g., "return the element that appears most often"), but it does more work than necessary for a pure boolean answer - it counts every occurrence rather than stopping at the first duplicate. Use this when the full frequency map is genuinely needed.

Bash

Bash is an unusual choice for algorithm problems, but it illustrates how the same problem can be approached with shell primitives - relevant in scripting contexts where you process text files or pipe data through standard tools:

#!/usr/bin/env bash

contains_duplicate() {
  local -a nums=("$@")
  local sorted
  # Sort numerically and look for adjacent duplicates
  sorted=$(printf '%s\n' "${nums[@]}" | sort -n)
  local prev=""
  while IFS= read -r line; do
    if [[ "$line" == "$prev" ]]; then
      echo "true"
      return 0
    fi
    prev="$line"
  done <<< "$sorted"
  echo "false"
}

# Example usage
contains_duplicate 1 2 3 3  # outputs: true
contains_duplicate 1 2 3 4  # outputs: false

Bash lacks native hash sets, so sorting is the natural approach here. The sort -n flag ensures numeric rather than lexicographic ordering. This solution is O(n log n) in time and O(n) in space (the sorted output is stored in a variable). It is not suitable for high-performance applications, but it demonstrates that algorithmic thinking transfers across paradigms: even in shell scripting, sorting before scanning is more efficient than nested loops.

An alternative using awk - which does support associative arrays (hash maps) - gives closer to O(n) behavior in practice:

#!/usr/bin/env bash

contains_duplicate_awk() {
  printf '%s\n' "$@" | awk '
    seen[$0]++ { print "true"; exit }
    END { print "false" }
  '
}

contains_duplicate_awk 1 2 3 3  # outputs: true
contains_duplicate_awk 1 2 3 4  # outputs: false

This awk version uses an associative array seen to track elements, incrementing the count on each visit and exiting immediately when a count exceeds zero - functionally identical to the hash set approach in higher-level languages. awk's associative arrays are implemented as hash tables internally, giving the same O(1) average-case behavior.

Trade-offs and Pitfalls

Mutation of Input

The sorting approach requires sorting the array, and in-place sort is destructive. This is a subtle but serious pitfall. In JavaScript, Array.prototype.sort() sorts in place; calling nums.sort() directly mutates the caller's data. This can introduce bugs that are extremely difficult to trace in complex systems where arrays are shared across components or closures. Always copy before sorting: [...nums].sort(...) in JavaScript, sorted(nums) in Python (which returns a new list), or explicit .slice().sort() if you prefer the explicit copy semantics.

The hash set approach avoids this entirely - it only reads from the input, making it referentially transparent for the input array. In functional programming terms, it is a pure operation on the input. This is an underappreciated advantage in codebases that treat immutability as a design principle.

Hash Collisions and Worst-Case Behavior

JavaScript's Set and Python's set use well-tuned hash functions for primitive types, making collision-induced performance degradation rare in practice. However, it is worth understanding that the O(1) claim is amortized and average-case, not worst-case. An adversarially constructed input - or a custom object type with a poor __hash__ implementation in Python - can degrade lookup to O(n) per operation. For integer inputs as in this problem, standard library hash functions are reliable, but this caveat matters when generalizing the approach to other data types.

Set One-Liner vs. Explicit Loop

The set-size comparison (new Set(nums).size !== nums.length) is frequently cited as the "best" solution in competitive programming contexts because of its brevity. This framing is misleading for production engineering. The explicit loop version with early return can outperform the one-liner by a large constant factor on inputs with duplicates early in the array, because it stops as soon as the first duplicate is found rather than processing all n elements. For random arrays where duplicates are statistically likely to appear in the first half, early return delivers substantial practical speedup even though both solutions have the same Big-O classification.

Best Practices

When approaching problems like Contains Duplicate in production code, the decision between approaches should be driven by explicit reasoning about constraints rather than habit. Ask: Is memory the binding constraint? Is the input already sorted? Is the input immutable? Is early termination important for average-case performance? These questions should guide your choice of data structure and algorithm, not familiarity or code brevity.

Always document the time and space complexity of non-trivial functions in production code. A comment stating // O(n) time, O(n) space - hash set approach is more valuable than verbose inline documentation, because it gives future maintainers the information they need to reason about performance at a glance. This is especially important in data-processing pipelines where a single inefficient function can become a bottleneck under load.

Prefer immutability for inputs. Whether you are working in JavaScript, TypeScript, or Python, avoid mutating the array you receive as a parameter. Use readonly in TypeScript, avoid in-place sort, and treat function inputs as contracts you do not modify. This makes code easier to reason about, test, and parallelize.

Write tests that cover edge cases explicitly: empty array, single-element array, all-same array, no-duplicates array, very large arrays with duplicates only at the end. These cases encode your understanding of the problem's boundary conditions and protect against regressions when the code is modified later.

Finally, resist the temptation to over-engineer. Contains Duplicate does not need memoization, lazy evaluation, or a custom data structure. The hash set solution is correct, efficient, and clear. Engineering judgment includes knowing when the simple solution is the right one.

Analogies and Mental Models

Think of the hash set approach as a guest list at an event. As each guest arrives, you check the list - O(1) lookup - and if their name is already on it, you know they are a duplicate. If not, you add their name. You never need to review the entire list from scratch; you just check and add. This is fundamentally different from the sorting approach, which would be like alphabetizing all the invitations before the event and then scanning for adjacent names that match.

The sorting approach is more like a librarian re-shelving books alphabetically and then walking the shelf looking for two copies of the same title side by side. It requires upfront reorganization (the sort), but the subsequent scan is trivially simple and requires almost no memory beyond the reorganized shelf itself. Both methods find duplicates; they make different bets about which resource - time or space - is more valuable.

Key Takeaways

  1. Choose the hash set approach by default for this problem. O(n) time and O(n) space is the right trade-off in the overwhelming majority of real-world scenarios where memory is not the binding constraint.

  2. Use early return in your loop rather than a set-size comparison. Early return is asymptotically equivalent but practically faster on inputs with duplicates near the beginning of the array.

  3. Never mutate the input array when using a sort-based approach. Copy first, sort the copy, then scan. This is a defensive habit that prevents subtle bugs in shared-state systems.

  4. Understand Big-O as a framework, not a verdict. O(n log n) with low constant factors can outperform O(n) with high constant factors for small n. Always profile if performance is critical.

  5. Generalize the pattern. The hash set membership pattern - "have I seen this before?" - applies to dozens of LeetCode problems including Longest Consecutive Sequence, Two Sum, and Group Anagrams. Mastering the pattern here accelerates learning elsewhere.

80/20 Insight

Eighty percent of algorithmic problem-solving reduces to a handful of patterns, and the hash set membership check is one of the most valuable. If you deeply understand why inserting into a set and checking membership gives you O(1) amortized performance - because a good hash function distributes keys uniformly across buckets, making the average bucket size O(1) - you have the conceptual foundation to solve two-sum, group anagrams, longest consecutive sequence, and dozens of other problems.

The single most important insight from Contains Duplicate is this: when a problem requires you to answer "have I seen X before?" for a stream of values, reach for a hash set first. The trade-off - linear space for linear time - is almost always worth it, and the cases where it is not (memory-constrained embedded systems, adversarial inputs requiring worst-case guarantees) are identifiable and rare.

Conclusion

Contains Duplicate is a small problem with large pedagogical value. It teaches you to recognize when a brute-force approach is asymptotically inadequate, to reason about time-space trade-offs, and to select data structures based on the operations you actually need rather than familiarity. The hash set solution is elegant not because it is clever, but because it matches the problem's structure: you need membership queries, and hash sets are built for membership queries.

Across JavaScript, TypeScript, Python, and Bash, the same algorithmic thinking applies with minor syntactic variations. The hash set is idiomatic and efficient in all three high-level languages; Bash requires either the sort-and-scan approach or delegation to awk for hash map behavior. Understanding these implementations across languages sharpens your sense of what is a language feature and what is an algorithm - a distinction that matters when you move between codebases or evaluate new tools.

The next time you encounter a problem that feels like "have I seen this before?" - deduplicate a list, find the first non-repeating character, count unique visitors in a log - return to this pattern. Build the set, check before inserting, exit early. It is one of the most reliable tools in an engineer's algorithmic toolkit.

References