#217

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Contains Duplicate

Determine if an integer array contains any duplicate values by efficiently scanning with a hash lookup to ensure fast detection.

array hash table sorting

Problem Statement

Given an array of integers, write a function that returns true if any element appears more than once in the array, and false if all elements are unique. The goal is to efficiently detect duplicates using scanning and hash-based lookup without unnecessary overhead.

For example, for nums = [1,2,3,1], the function should return true because the value 1 occurs at multiple indices. For nums = [1,2,3,4], the function should return false since every element is distinct. Constraints include array lengths up to 105 and integer values between -109 and 109.

Examples

Example 1

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

Output: true

The element 1 occurs at the indices 0 and 3.

Example 2

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

Output: false

All elements are distinct.

Example 3

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

Output: true

Example details omitted.

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solution Approach

Hash Set Tracking

Initialize an empty hash set and iterate through the array. For each number, check if it exists in the set; if so, return true. Otherwise, add it to the set. This guarantees O(n) time with O(n) extra space.

Sorting and Adjacent Comparison

Sort the array first, then iterate and compare each element with its neighbor. If any two consecutive elements are equal, return true. This reduces extra space usage but increases time complexity to O(n log n).

Early Exit During Scan

While scanning, immediately exit upon detecting the first duplicate. This avoids full traversal for arrays with early duplicates and ensures minimal operations, reinforcing the array scanning plus hash lookup pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Using a hash set, the time complexity is O(n) since each element is visited once, and space complexity is O(n) for storing unique elements. Sorting first yields O(n log n) time and O(1) space if in-place sorting is allowed, highlighting the trade-off between speed and memory.

What Interviewers Usually Probe

Expect candidates to use a hash set for linear-time duplicate detection.
Watch for proper handling of edge cases with minimal and maximal array sizes.
Consider discussions around early exit optimization and space versus time trade-offs.

Common Pitfalls or Variants

Common pitfalls

Using nested loops leads to O(n^2) time, which is unnecessary for this pattern.
Forgetting to handle negative integers or zero in the array can cause incorrect results.
Not implementing early exit may waste time on large arrays even when duplicates exist early.

Follow-up variants

Return the indices of the first duplicate instead of a boolean.
Count the total number of duplicates rather than just detecting one.
Detect duplicates within a sliding window of size k instead of the whole array.

FAQ

What is the most efficient way to solve Contains Duplicate?

Using a hash set while scanning the array is most efficient, ensuring O(n) time and O(n) space for immediate detection.

Can sorting help detect duplicates?

Yes, sorting allows adjacent comparisons, reducing extra space to O(1) but increasing time complexity to O(n log n).

How does GhostInterview reinforce the array scanning plus hash lookup pattern?

It emphasizes scanning each element with immediate hash checks and early exit to detect duplicates efficiently.

What should I watch out for in large arrays?

Be careful with space usage and ensure early exit to avoid unnecessary full traversal when duplicates appear early.

Are negative numbers handled in this problem?

Yes, the solution must correctly detect duplicates for all integer values, including negatives and zero.

terminal

Solution

Solution 1: Sorting

First, we sort the array `nums`.

1

2

3

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return any(a == b for a, b in pairwise(sorted(nums)))

Solution 2: Hash Table

We traverse the array and record the elements that have appeared in the hash table $s$. If an element appears for the second time, it means that there are duplicate elements in the array, and we directly return `true`.

1

2

3

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return any(a == b for a, b in pairwise(sorted(nums)))

Continue Practicing

#229 majority element ii #169 majority element #268 missing number