Marauder Bot

Problem

You are given an array of integers. Determine whether any value shows up more than once, returning true the moment a repeat exists and false only if every element is distinct.

Example. For [1, 2, 3, 1] the answer is true, since 1 appears at both index 0 and index 3. For [1, 2, 3, 4] the answer is false.

Key idea

Checking every pair of elements against each other answers the question but costs O(n²), and that cost grows fast as the array gets large. Sorting first and then scanning for adjacent equal values gets it down to O(n log n), a solid improvement, but there is a faster route.

Walk the array once, keeping a hash set of every value seen so far. For each new element, check whether it is already in the set before inserting it. If it is, a duplicate has been found and the scan can stop immediately. If the loop finishes without a hit, no duplicates exist. Because a hash set lookup and insert are both average O(1), the whole scan finishes in linear time, trading some memory for speed.

Solution

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

  for (const num of nums) {
    if (seen.has(num)) {
      return true; // this value was already recorded on an earlier iteration
    }
    seen.add(num);
  }

  return false;
}

Complexity

Time: O(n). A single pass with constant-time average set operations.
Space: O(n). The set can grow to hold every distinct element in the worst case.

Watch out for

Check membership before inserting the current value, otherwise every element trivially "finds" itself.
If memory is constrained, sorting in place and scanning for neighbors gives O(n log n) time with no extra space, a reasonable trade when the hash set's O(n) space is unacceptable.
Do not confuse this with counting how many duplicates exist: the problem only asks for a yes-or-no answer, so returning early is both correct and faster in practice.

Pattern

This is the "seen-before" pattern: a hash set that records what has already been visited so a repeat can be recognized in constant time. It is the starting point for a broad family of uniqueness and frequency problems.

Contains Duplicate