Introduction

The Contains Duplicate problem involves checking whether any element appears more than once in the array.

Given an array arr[] of size n, the task is to determine whether the array contains duplicate elements.

Return:

  • true  if any value appears at least twice
  • false if all elements are distinct

This is one of the most important beginner-level Hashing problems and helps in understanding HashSet, efficient lookup operations, and duplicate detection techniques.

Example

Input: arr[] = [1, 2, 3, 4, 2]Output: true
Explanation:
Element 2 appears more than once.
Therefore, the array contains duplicates.

Input: arr[] = [5, 8, 1, 9]
Output: false
Explanation:
All elements are unique.
No duplicate element exists.

Constraints

 1 <= n <= 10^5 -10^9 <= arr[i] <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Compare every element with all remaining elements
  2. If any two elements are equal:
    • duplicate exists

This approach is easy to understand but repeated comparisons increase time complexity.

Steps

  1. Traverse the array using index i.
  2. Compare arr[i] with every element after it.
  3. If duplicate is found:
    • return true
  4. If traversal completes:
    • return false

Dry Run

Input Array: [1, 2, 3, 4, 2]Compare 1 with remaining elements:
No duplicate found
Compare 2 with remaining elements:
2 == 2
Duplicate found
Return true

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)
Explanation:
Every element is compared with remaining elements.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (HashSet)

Explanation

Instead of repeatedly comparing elements, we can use a HashSet.

The idea is:

  1. Traverse the array
  2. Store visited elements in HashSet
  3. If current element already exists:
    • duplicate found immediately

HashSet provides fast lookup operations.

Steps

  1. Create an empty HashSet.
  2. Traverse the array.
  3. For every element:
    • check if element already exists
  4. If exists:
    • return true
  5. Otherwise:
    • insert element into HashSet
  6. If traversal finishes:
    • return false

Dry Run

Input Array: [1, 2, 3, 4, 2]Initially:
HashSet = {}
Traverse 1:
Not present
Insert 1
HashSet = {1}
Traverse 2:
Not present
Insert 2
HashSet = {1, 2}
Traverse 3:
Insert 3
HashSet = {1, 2, 3}
Traverse 4:
Insert 4
HashSet = {1, 2, 3, 4}
Traverse 2:
2 already exists
Duplicate found
Return true

Optimized Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is checked once using HashSet lookup.

Space Complexity: O(n)
Explanation:
HashSet stores array elements.

Edge Cases

  1. Array contains all unique elements
  2. Array contains all duplicates
  3. Array contains one element
  4. Array contains negative numbers
  5. Duplicate appears multiple times

Why This Problem is Important

This problem helps in understanding:

  1. Hashing techniques
  2. HashSet usage
  3. Fast lookup operations
  4. Duplicate detection
  5. Efficient traversal

It is one of the most important beginner-level hashing interview problems.

Real-World Applications

Duplicate detection is used in:

  1. Database systems
  2. User authentication systems
  3. Fraud detection
  4. Data cleaning pipelines
  5. Inventory management systems

Common Mistakes

  1. Forgetting to insert elements into HashSet
  2. Incorrect duplicate checks
  3. Using list instead of HashSet
  4. Breaking loops incorrectly

Interview Tips

Interviewers often expect:

  1. HashSet optimization
  2. O(n) solution
  3. Efficient lookup explanation

Always explain why HashSet provides faster duplicate detection compared to nested loops.

Related Questions

  1. Frequency Count
  2. Majority Element
  3. Two Sum
  4. First Missing Positive
  5. Longest Consecutive Sequence

Final Takeaway

The Contains Duplicate problem is a fundamental hashing problem that teaches efficient lookup operations and duplicate detection techniques using HashSet. Understanding this problem builds a strong foundation for advanced hashing and array interview problems.