Coding Interview PatternsContains Duplicate
EasyHash Maps

Contains Duplicate

Explanation & Solution

Practice Problem

Description

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

Input:nums = [1,2,3,1]
0
1
1
2
2
3
3
1

Output: true

Explanation: The element 1 appears at index 0 and index 3.

Constraints

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

Approach

Hash Maps pattern

1. Create a Hash Set

  • Initialize an empty Set to track numbers we have already encountered
  • A set provides O(1) average time for both insertion and lookup

2. Iterate Through the Array

  • For each number num in the array:
  • Check if num is already in the set
  • If yes, we found a duplicate — return true immediately
  • If no, add num to the set and continue

3. No Duplicates Found

  • If we finish iterating through the entire array without finding any duplicate, return false
  • Every element in the array is distinct

Key Insight

  • A brute-force approach comparing every pair takes O(n²). Sorting first and checking adjacent elements takes O(n log n). Using a hash set solves it in O(n)
  • The set acts as a "memory" of previously seen values — each element is checked against all prior elements in constant time
Time
O(n)single pass through the array
Space
O(n)the set stores at most n elements

Visualization

Input:
[1, 2, 3, 1]
10213213
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Group Anagrams
Next
Longest Consecutive Sequence