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

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Thinking Process

We need to detect if any element appears more than once. Three standard approaches:

  1. Hash set – insert elements one by one, return true the moment we see a duplicate. Early exit.
  2. Sorting – sort the array, then adjacent duplicates are next to each other.
  3. One-liner – build a set from the array and compare sizes.
Array + hash map 2 7 11 map hash map for O(1) lookups

Approach 1: Hash Set – O(n)

Insert elements and check for duplicates in one pass. Early exit on first duplicate.

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

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: We need to detect if any element appears more than once. Three standard approaches:

How the code works:

  1. Hash set – insert elements one by one, return true the moment we see a duplicate. Early exit.
  2. Sorting – sort the array, then adjacent duplicates are next to each other.
  3. One-liner – build a set from the array and compare sizes.

Walkthrough — input nums = [1,2,3,1], expected output true:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Hash Map – O(n)

Same idea but tracks counts. Slightly more than needed here, but useful when the problem asks how many duplicates.

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

Time: O(n) Space: O(n)

Approach 3: Sorting – O(n log n)

Sort first, then duplicates become adjacent.

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

Time: O(n log n) Space: O(1) (in-place sort, modifies input)

Approach 4: One-Liner – O(n)

Build a set and compare sizes. Clean but no early exit.

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()
        for x in nums:
            if x in seen:
                return True
            seen.add(x)
        return False

Time: O(n) Space: O(n)

Comparison

Approach Time Space Early Exit? Modifies Input?
Hash Set O(n) O(n) Yes No
Hash Map O(n) O(n) Yes No
Sorting O(n log n) O(1) Yes Yes
One-Liner O(n) O(n) No No

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • Hash set with early exit is the best general approach – O(n) time with short-circuit on first duplicate
  • Sorting trades time for space (O(1) extra) but modifies the input
  • The one-liner is elegant but always processes the entire array

References

Template Reference