Log inSign up
easyLeetCodeNot Started

Contains Duplicate

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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.

Example 1 · Duplicate Present (Early Return):

Input: nums = [1, 2, 3, 1]
Output: true
Explanation: The element 1 occurs at index 0 and index 3, so the array contains a duplicate.

Example 2 · All Distinct Elements:

Input: nums = [1, 2, 3, 4]
Output: false
Explanation: Every element in the array is distinct, so we return false.

Example 3 · Multiple Duplicate Elements:

Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true
Explanation: Multiple elements (1, 2, 3, 4) appear more than once.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array traversal and linear scanning
  • Hash Set data structure and membership checks (contains/has)
  • Comparison of Time vs Space trade-offs (O(N) time with O(N) space vs O(N log N) time with O(1) space)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the use of Hash Sets for O(1) membership and existence queries.
  • Understand in-place sorting as an O(1) space alternative for duplicate detection.
  • Implement early-exit patterns that terminate immediately upon finding a collision.
  • Write standard, clean solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If extra memory is allowed -> Use a Hash Set (O(N) time, O(N) space).
  • If strictly O(1) extra space is required -> Sort the array in-place and check adjacent elements nums[i] == nums[i+1] (O(N log N) time, O(1) space).
  • If array elements are bounded in [1, N] -> Use in-place sign negation or cycle detection.

Connected Patterns:

Hash Set MembershipSorting & Adjacent ComparisonContains Duplicate II (Window Distance K)Find the Duplicate Number

1. Brute Force — Check All Pairs

Intuition

Compare each element with every other element using nested loops to detect duplicates.

Algorithm

  1. Loop with index i from 0 to N - 1.
  2. Nested loop with index j from i + 1 to N - 1.
  3. If nums[i] == nums[j], return true immediately.
  4. If all pairs are checked without equality, return false.

Brute Force All Pairs Equality Scan

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 1]
Current operationSTEP 1 OF 6
Phase 1 — No match Advance j to index 2: Pair (0, 1): Fix i=0 (value 1)
Visual state
Values and pointers at this exact step
array
S
1
2
3
1
0
↑ i=0 (val 1)
1
↑ j=1 (val 2)
2
3
Variables at this step
Fixed i
0 (val 1)
Inner j
1 (val 2)
Match
NO
Check / comparison
nums[0] == nums[1] -> 1 == 2 is FALSE.
Decision / next transition
No match. Advance j to index 2.
Why this step matters

Phase 1 — No match Advance j to index 2: Pair (0, 1): Fix i=0 (value 1). Test j=1 (value 2). Elements differ. Increment j.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force: Check all pairs
6bool containsDuplicate(const vector<int>& nums) {
7 int n = nums.size();
8 for (int i = 0; i < n; i++) {
9 for (int j = i + 1; j < n; j++) {
10 if (nums[i] == nums[j]) {
11 return true; // Duplicate found
12 }
13 }
14 }
15 return false; // All distinct
16}
17
18int main() {
19 vector<int> nums = {1, 2, 3, 1};
20 cout << "Contains Duplicate: " << (containsDuplicate(nums) ? "true" : "false") << endl;
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(N²) — Compares all pairs (i, j) with j > i, performing N × (N - 1) / 2 comparisons = O(N²) quadratic time.
  • Space complexity: O(1) — No auxiliary data structures are used. Memory is strictly constant O(1).

Why Brute Force Doesn't Scale:

For N = 100,000, checking every pair takes (100,000 × 99,999) / 2 ≈ 5,000,000,000 operations (5 billion comparisons), exceeding online judge execution limits.

By leveraging a Hash Set (which has O(1) average lookup), we only need to inspect each number once, finding duplicates in linear O(N) time with immediate early termination.

For N = 105: Brute force takes ~5B ops (TLE). Hash Set takes ~100K ops (~3ms).

2. Better — Sort & Check Adjacent

Intuition

Sort the array ascending. If any duplicates exist, they will end up at adjacent indices: nums[i] == nums[i+1].

Algorithm

  1. Sort the array nums in ascending order.
  2. Loop with index i from 0 to N - 2.
  3. If nums[i] == nums[i + 1], return true.
  4. If loop ends, return false.

Sorting and Adjacent Pair Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 2, 3]
Current operationSTEP 1 OF 6
Phase 1 — Sorting: Sort array in $O(N \log N)$ time
Visual state
Values and pointers at this exact step
array
S
1
1
2
3
0
↑ Sort Pass
1
2
3
Variables at this step
Original
[1, 2, 3, 1]
Sorted
[1, 1, 2, 3]
Phase
Sorted
Check / comparison
Sort input array: [1, 2, 3, 1] -> [1, 1, 2, 3].
Decision / next transition
Duplicates are now guaranteed to be adjacent.
Why this step matters

Phase 1 — Sorting: Sort array in O(N log N) time. Any identical values will now sit next to each other.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Better: Sort and check adjacent elements
7bool containsDuplicate(vector<int>& nums) {
8 sort(nums.begin(), nums.end());
9 int n = nums.size();
10
11 for (int i = 0; i < n - 1; i++) {
12 if (nums[i] == nums[i + 1]) {
13 return true; // Adjacent duplicate found
14 }
15 }
16 return false;
17}
18
19int main() {
20 vector<int> nums = {1, 2, 3, 1};
21 cout << "Contains Duplicate: " << (containsDuplicate(nums) ? "true" : "false") << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting the array takes O(N log N) time. The subsequent adjacent scan takes O(N) time. Overall time complexity is dominated by sorting: O(N log N).
  • Space complexity: O(1) or O(log N) — Sorting in-place requires O(1) auxiliary space beyond the O(log N) recursion stack used by sorting algorithms.

3. Optimal — Hash Set (One-Pass Lookup)

Intuition

Maintain a Hash Set of seen numbers. For each element, if it exists in the set, return true; otherwise add it to the set.

Algorithm

  1. Initialize an empty Hash Set seen.
  2. Iterate through each number num in nums.
  3. If num is present in seen, return true immediately.
  4. Add num to seen.
  5. If loop ends without any duplicate, return false.

One-Pass Hash Set Lookup Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 1]
Current operationSTEP 1 OF 6
Phase 1 — Insert 1 into seen set: seen = { 1 }: Step 1: Inspect index 0 (value 1)
Visual state
Values and pointers at this exact step
array
S
1
2
3
1
0
↑ i=0 (val 1)
1
2
3
Variables at this step
Current Idx
0
Val
1
seen
{ 1 }
Duplicate
NO
Check / comparison
Is 1 in seen set? seen = {}. Answer: NO.
Decision / next transition
Insert 1 into seen set: seen = { 1 }.
Why this step matters

Phase 1 — Insert 1 into seen set: seen = { 1 }: Step 1: Inspect index 0 (value 1). Seen set is empty. Add 1 to set.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3#include <vector>
4using namespace std;
5
6// Optimal: Hash Set
7bool containsDuplicate(const vector<int>& nums) {
8 unordered_set<int> seen;
9
10 for (int num : nums) {
11 // If already seen, duplicate found
12 if (seen.find(num) != seen.end()) {
13 return true;
14 }
15 seen.insert(num);
16 }
17 return false;
18}
19
20int main() {
21 vector<int> nums = {1, 2, 3, 1};
22 cout << "Contains Duplicate: " << (containsDuplicate(nums) ? "true" : "false") << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(N) avg — The array is traversed once. Each hash set lookup and insertion takes O(1) average time. Total time = N × O(1) = O(N) average time.
  • Space complexity: O(N) — In the worst case where all elements are distinct, the Hash Set stores N elements, using O(N) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Compare All PairsO(N²)O(1)Compare every element with all subsequent elements using nested loops.Performs N(N - 1)/2 pair comparisons.
2.Better — Sort & Check AdjacentO(N log N)O(1)Sort array ascending, bringing identical elements next to each other. Check if nums[i] == nums[i+1].Sorting overhead.
3.Optimal — Hash Set Single PassOptimalO(N) avgO(N)Iterate through nums. If element is already in Hash Set, return true. Otherwise add to set.Trades memory for linear time speed.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to return true immediately when seen.has(num) is true.

Pitfall 2:

Using nested loops (O(N²)) which results in TLE for arrays with 105 elements.

Pitfall 3:

Assuming set insertion in Java is boolean check; in Java, set.add(num) conveniently returns false if already present.

Crucial Edge Cases to Validate:

  • Single element array (nums = [1]) -> cannot contain duplicates, returns false.
  • Array where every element is identical (nums = [7, 7, 7, 7]) -> returns true on 2nd element.
  • Negative numbers and zeroes (nums = [-5, 0, 5, -5]) -> returns true.
  • Large array of size 105 with duplicate at the very end ([1, 2, 3, ..., 100000, 1]).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State both the Hash Set approach (O(N) time, O(N) space) and the Sorting approach (O(N log N) time, O(1) space) to show you understand space-time trade-offs.
  2. Mention early termination: if a duplicate appears in the first few elements, the Hash Set solution returns in O(1) time.
  3. In Python, mention that len(set(nums)) < len(nums) is a fast one-liner, but loop with early return is more optimal for early duplicates.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Contains Duplicate?

2.Why is the brute force approach suboptimal for large inputs in Contains Duplicate?

3.Which data structure or technique enables the optimal solution for Contains Duplicate?

Back to DSA Sheet