Contains Duplicate

🎯

Contains Duplicate

easyHASH_MAPAmazonAppleGoogle

Imagine you are managing a guest list for an event and want to quickly check if someone has already RSVP'd to avoid duplicates.

💡 This problem is about detecting if any element appears more than once in a list. Beginners often struggle because they try to compare every pair, which is inefficient. Using a hash set to track seen elements is a key insight that simplifies the problem.

📋

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.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1,2,3,1]"

Outputtrue

The number 1 appears twice.

Input"[1,2,3,4]"

Outputfalse

All elements are distinct.

Input"[1,1,1,3,3,4,3,2,4,2]"

Outputtrue

Multiple duplicates exist.

• Single element array → false
• All elements are the same → true
• Large array with no duplicates → false
• Array with duplicates at the start or end → true

⚠️

Common Mistakes

Using nested loops without breaking early

Unnecessary comparisons increase runtime

✅ Return immediately when a duplicate is found

Not handling empty or single-element arrays

May cause incorrect results or errors

✅ Check array length and return false if less than 2

Using == instead of === in JavaScript

May cause unexpected type coercion bugs

✅ Use strict equality === for accurate comparison

Sorting array without specifying numeric comparator in JavaScript

Sorts lexicographically, causing wrong order

✅ Use nums.sort((a,b) => a - b) for numeric sort

Using a list to track seen elements instead of a set

Membership checks become O(n), leading to O(n^2) time

✅ Use a hash set for O(1) membership checks

🧠

Brute Force (Nested Loops)

💡 This approach exists to establish a baseline understanding by checking every pair for duplicates, which is intuitive but inefficient.

Intuition

Check every pair of elements to see if any two are equal.

Algorithm

1. Iterate over each element in the array.
2. For each element, iterate over all subsequent elements.
3. Compare the current pair; if equal, return true immediately.
4. If no duplicates found after all comparisons, return false.

💡 The nested loops make it hard to see efficiency issues at first, but it's a direct way to find duplicates.

</>

Code

def containsDuplicate(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False

# Driver code
if __name__ == '__main__':
    print(containsDuplicate([1,2,3,1]))  # True
    print(containsDuplicate([1,2,3,4]))  # False

Line Notes

n = len(nums)Store length to avoid recomputing in loops

for i in range(n)Outer loop picks each element to compare

for j in range(i + 1, n)Inner loop compares current element with all following elements

if nums[i] == nums[j]Check if a duplicate pair is found

return TrueImmediately return upon finding a duplicate

return FalseNo duplicates found after full search

import java.util.*;
public class Solution {
    public static boolean containsDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(containsDuplicate(new int[]{1,2,3,1})); // true
        System.out.println(containsDuplicate(new int[]{1,2,3,4})); // false
    }
}

Line Notes

int n = nums.length;Cache array length for efficiency

for (int i = 0; i < n; i++)Outer loop selects each element

for (int j = i + 1; j < n; j++)Inner loop compares with subsequent elements

if (nums[i] == nums[j])Check for duplicate pair

return true;Return immediately on finding duplicate

return false;Return false if no duplicates found

#include <iostream>
#include <vector>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<int> v1 = {1,2,3,1};
    vector<int> v2 = {1,2,3,4};
    cout << boolalpha << containsDuplicate(v1) << endl; // true
    cout << boolalpha << containsDuplicate(v2) << endl; // false
    return 0;
}

Line Notes

int n = nums.size();Store vector size once

for (int i = 0; i < n; i++)Outer loop picks each element

for (int j = i + 1; j < n; j++)Inner loop compares with elements after i

if (nums[i] == nums[j])Check for duplicate

return true;Return immediately if duplicate found

return false;Return false if no duplicates

function containsDuplicate(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] === nums[j]) {
                return true;
            }
        }
    }
    return false;
}

// Test cases
console.log(containsDuplicate([1,2,3,1])); // true
console.log(containsDuplicate([1,2,3,4])); // false

Line Notes

const n = nums.length;Cache length for loop efficiency

for (let i = 0; i < n; i++)Outer loop selects element

for (let j = i + 1; j < n; j++)Inner loop compares with subsequent elements

if (nums[i] === nums[j])Check for duplicates

return true;Return immediately on duplicate

return false;Return false if none found

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each up to n iterations lead to n*(n-1)/2 comparisons, which is O(n^2). No extra space is used.

💡 For n=20, this means about 190 comparisons, which is manageable, but for n=100000, it becomes 5 billion comparisons, which is too slow.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem and sets the stage for optimization.

🧠

Sorting + Single Pass

💡 Sorting the array first groups duplicates together, making it easy to detect duplicates by checking adjacent elements.

Intuition

Sort the array so duplicates become neighbors, then scan once to find any equal adjacent pair.

Algorithm

1. Sort the input array.
2. Iterate through the array from start to end - 1.
3. Compare each element with the next one.
4. If any pair is equal, return true.
5. If no duplicates found, return false.

💡 Sorting changes the problem from comparing all pairs to just checking neighbors, simplifying the search.

</>

Code

def containsDuplicate(nums):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

# Driver code
if __name__ == '__main__':
    print(containsDuplicate([1,2,3,1]))  # True
    print(containsDuplicate([1,2,3,4]))  # False

Line Notes

nums.sort()Sort array to bring duplicates together

for i in range(len(nums) - 1)Iterate through array except last element

if nums[i] == nums[i + 1]Check adjacent elements for equality

return TrueReturn immediately if duplicate found

return FalseReturn false if no duplicates

import java.util.*;
public class Solution {
    public static boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(containsDuplicate(new int[]{1,2,3,1})); // true
        System.out.println(containsDuplicate(new int[]{1,2,3,4})); // false
    }
}

Line Notes

Arrays.sort(nums);Sort array to group duplicates

for (int i = 0; i < nums.length - 1; i++)Loop through array except last element

if (nums[i] == nums[i + 1])Check adjacent elements for duplicates

return true;Return true immediately if duplicate found

return false;Return false if none found

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < (int)nums.size() - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

int main() {
    vector<int> v1 = {1,2,3,1};
    vector<int> v2 = {1,2,3,4};
    cout << boolalpha << containsDuplicate(v1) << endl; // true
    cout << boolalpha << containsDuplicate(v2) << endl; // false
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort vector to bring duplicates together

for (int i = 0; i < (int)nums.size() - 1; i++)Loop through all but last element

if (nums[i] == nums[i + 1])Check adjacent elements for equality

return true;Return true immediately if duplicate found

return false;Return false if none found

function containsDuplicate(nums) {
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i + 1]) {
            return true;
        }
    }
    return false;
}

// Test cases
console.log(containsDuplicate([1,2,3,1])); // true
console.log(containsDuplicate([1,2,3,4])); // false

Line Notes

nums.sort((a, b) => a - b);Sort array numerically to group duplicates

for (let i = 0; i < nums.length - 1; i++)Loop through array except last element

if (nums[i] === nums[i + 1])Check adjacent elements for duplicates

return true;Return true immediately if duplicate found

return false;Return false if none found

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n) time, then a single pass O(n) to check neighbors. Space depends on sort implementation.

💡 For n=100000, sorting is feasible and much faster than brute force, making this approach practical.

Interview Verdict: Accepted, but not optimal

This approach is efficient enough for many cases but can be improved using hash sets for linear time.

🧠

Hash Set for Membership Checking (Optimal)

💡 Using a hash set to track seen elements allows checking duplicates in O(1) average time, making the solution linear and efficient.

Intuition

Iterate through the array, adding elements to a set. If an element is already in the set, a duplicate exists.

Algorithm

1. Create an empty hash set.
2. Iterate through each element in the array.
3. For each element, check if it is in the set.
4. If yes, return true immediately.
5. If no, add the element to the set.
6. If iteration completes without duplicates, return false.

💡 The hash set provides constant time membership checks, making the algorithm efficient and simple.

</>

Code

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

# Driver code
if __name__ == '__main__':
    print(containsDuplicate([1,2,3,1]))  # True
    print(containsDuplicate([1,2,3,4]))  # False

Line Notes

seen = set()Initialize empty set to track seen elements

for num in nums:Iterate over each element in array

if num in seen:Check if current element is already seen

return TrueReturn immediately if duplicate found

seen.add(num)Add new element to set

return FalseReturn false if no duplicates found

import java.util.*;
public class Solution {
    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(containsDuplicate(new int[]{1,2,3,1})); // true
        System.out.println(containsDuplicate(new int[]{1,2,3,4})); // false
    }
}

Line Notes

Set<Integer> seen = new HashSet<>();Create hash set to track seen elements

for (int num : nums)Iterate over each element in array

if (seen.contains(num))Check if element already in set

return true;Return immediately if duplicate found

seen.add(num);Add new element to set

return false;Return false if no duplicates

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.find(num) != seen.end()) {
            return true;
        }
        seen.insert(num);
    }
    return false;
}

int main() {
    vector<int> v1 = {1,2,3,1};
    vector<int> v2 = {1,2,3,4};
    cout << boolalpha << containsDuplicate(v1) << endl; // true
    cout << boolalpha << containsDuplicate(v2) << endl; // false
    return 0;
}

Line Notes

unordered_set<int> seen;Initialize hash set for tracking

for (int num : nums)Iterate over each element

if (seen.find(num) != seen.end())Check if element already in set

return true;Return immediately if duplicate found

seen.insert(num);Add element to set

return false;Return false if no duplicates

function containsDuplicate(nums) {
    const seen = new Set();
    for (const num of nums) {
        if (seen.has(num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}

// Test cases
console.log(containsDuplicate([1,2,3,1])); // true
console.log(containsDuplicate([1,2,3,4])); // false

Line Notes

const seen = new Set();Create a set to track seen elements

for (const num of nums)Iterate over each element

if (seen.has(num))Check if element already in set

return true;Return immediately if duplicate found

seen.add(num);Add element to set

return false;Return false if no duplicates

⏱

Complexity

TimeO(n)

SpaceO(n)

Each element is checked and inserted once into the hash set, leading to linear time. Space is linear due to the set storing up to n elements.

💡 For n=100000, this means about 100000 operations, which is efficient and scalable.

Interview Verdict: Accepted and optimal

This approach is the best practical solution for this problem and is expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the hash set approach is best due to its simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Sorting + Single Pass	O(n log n)	O(1) or O(n)	No	N/A	Good fallback if hash sets not allowed
3. Hash Set for Membership Checking	O(n)	O(n)	No	N/A	Code this in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then progress to optimal solutions. Practice explaining each step clearly.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach and its inefficiency.Step 3: Suggest sorting to improve time complexity.Step 4: Present the hash set approach as optimal.Step 5: Code the hash set solution and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your ability to identify duplicates efficiently, optimize naive solutions, and write clean code using appropriate data structures.

Common Follow-ups

• What if the array is sorted? → Use adjacent comparison without extra space.
• What if memory is limited? → Use sorting or bit manipulation if applicable.

💡 These follow-ups test your adaptability and understanding of trade-offs between time and space.

🔍

Pattern Recognition

When to Use

1) Need to detect duplicates or repeated elements, 2) Input is an array or list, 3) Order does not matter, 4) Efficient membership check is possible

Signature Phrases

any value appears at least twicereturn true if duplicates exist

NOT This Pattern When

Problems requiring counting frequencies or ordering constraints are different patterns.

Similar Problems

Contains Duplicate II - checks duplicates within a windowContains Duplicate III - checks duplicates within value and index constraints

Practice

1. Consider the following Python code implementing the optimal approach for finding the intersection of two arrays. What is the final returned list when calling intersect([4,9,5], [9,4,9,8,4])?

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i, j = 0, 0
    intersection = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            intersection.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return intersection

easy

A. [4, 4, 9]

B. [9, 9]

C. [4, 9]

D. [4, 9, 5]

Solution

1. Step 1: Sort both arrays

   nums1 sorted: [4,5,9], nums2 sorted: [4,4,8,9,9]

2. Step 2: Traverse with two pointers

   Compare 4 and 4 -> equal, add 4; i=1, j=1 Compare 5 and 4 -> 5>4, increment j=2 Compare 5 and 8 -> 5<8, increment i=2 Compare 9 and 8 -> 9>8, increment j=3 Compare 9 and 9 -> equal, add 9; i=3, j=4 (end)

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Intersection is [4,9] matching common elements with duplicates counted correctly [OK]

Hint: Sort arrays and advance pointers carefully [OK]

Common Mistakes:

• Off-by-one errors in pointer increments
• Including extra duplicates
• Returning unsorted results

2. What is the time complexity of the optimal prefix sum + hash map solution for finding the longest contiguous subarray with equal number of 0s and 1s, given an input array of length n?

medium

A. O(n^2) because of nested loops to check subarrays

B. O(n log n) due to sorting prefix sums

C. O(n) because each element is processed once with constant-time hash map operations

D. O(n) for prefix sums but O(n^2) for hash map lookups

Solution

1. Step 1: Identify loop structure

   The algorithm iterates over the array once, performing O(1) operations per element.

2. Step 2: Analyze hash map operations

   Hash map lookups and insertions are average O(1), so total is O(n).

3. Step 3: Why O(n) because each element is processed once with constant-time hash map operations is incorrect

   Although each element is processed once, hash map operations can degrade in worst case, but average case is O(1). However, O(n log n) due to sorting prefix sums mentions sorting prefix sums which is not done in this algorithm.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Single pass + O(1) map ops -> O(n) time [OK]

Hint: Hash map lookups are average O(1), no nested loops [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking hash map lookups cost O(n)

3. The following code attempts to find the intersection of two arrays using the two-pointer approach. Which line contains a subtle bug that can cause incorrect results when duplicates exist?

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i, j = 0, 0
    intersection = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            intersection.append(nums1[i])
            i += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return intersection

medium

A. Line that sorts nums1

B. Line that sorts nums2

C. Line that increments j in the else clause

D. Line that increments i after appending intersection

Solution

1. Step 1: Identify the bug

   When nums1[i] == nums2[j], only i is incremented but j is not, causing infinite loop or missing duplicates.

2. Step 2: Correct fix

   Both i and j must be incremented to move past matched elements and handle duplicates correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incrementing only one pointer on match breaks correctness [OK]

Hint: Both pointers must advance on match [OK]

Common Mistakes:

• Incrementing only one pointer on match
• Modifying input arrays directly
• Forgetting to sort arrays

4. What is the time complexity of the optimal bidirectional hash map approach to check if two strings of length n are isomorphic?

medium

A. O(n) because each character is processed once with constant-time hash map operations

B. O(n²) due to nested loops checking all character pairs

C. O(n log n) due to sorting characters before mapping

D. O(1) since hash maps provide constant-time lookups

Solution

1. Step 1: Identify the main loop over string length

   The algorithm iterates once over the strings of length n, processing each character pair exactly once.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are average O(1), so total time is O(n) * O(1) = O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) [OK]

Hint: Single pass with hash maps -> O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming sorting is needed
• Ignoring hash map average case

5. Consider the following buggy get method for the time-based key-value store. Which line contains the subtle bug that causes incorrect results when querying timestamps less than the smallest stored timestamp?

medium

A. Line 6: Returning empty string if i == 0

B. Line 2: Checking if key not in store

C. Line 5: Using bisect_left instead of bisect_right

D. Line 7: Returning values[i-1]

Solution

1. Step 1: Understand difference between bisect_left and bisect_right

   bisect_left returns insertion index to the left, which can cause off-by-one errors when timestamp equals stored timestamps.

2. Step 2: Identify impact on retrieval

   Using bisect_left causes incorrect index i for timestamps equal to stored ones, leading to wrong value or empty string returned.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   bisect_right is required to get correct insertion point for retrieval [OK]

Hint: bisect_right needed to get correct insertion index [OK]

Common Mistakes:

• Using bisect_left instead of bisect_right
• Incorrect boundary check for i==0
• Returning wrong index value