Contains Duplicate - Leetcode Solution

Problem Link

Step-by-Step Thought Process

Brute Force

Understand the Problem:
- We need to check if there are any duplicates in the array nums.
- If any number appears twice, we return true, otherwise we return false.
Loop Through Each Pair of Elements:
- We iterate through each element in the array nums.
- For each element, we compare it with every other element that comes after it.
Check for Duplicates:
- If we find two identical elements at different indices, we return true immediately.
- If no duplicates are found after checking all pairs, return false.

Code Solution (Brute Force)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        n = len(nums)

        for i in range(n):
            for j in range(i+1, n):
                if nums[i] == nums[j]:
                    return True
        return False
        # Time Complexity: O(n^2)
        # Space Complexity: O(1)

#include <vector>
using namespace std;

class Solution {
public:
    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;
    }
};

public class Solution {
    public 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;
    }
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(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;
};

Why the Brute Force Solution is Inefficient

The brute force approach is inefficient because it requires comparing every pair of elements in the array, leading to a time complexity of O(n^2), where n is the length of the array. This becomes slow for larger arrays because the number of comparisons grows quadratically as the size of the array increases.

Optimal Solution: The Fix

Instead of using nested loops, we use a set to track the elements we've already seen.
As we iterate through the array, we check if the current element is already in the set. If it is, that means we've found a duplicate, so we return true immediately.
If the current element is not in the set, we add it to the set and continue to the next element.
By using a set, we can check for duplicates in constant time, O(1), making the time complexity of the solution O(n) where n is the length of the array.
Since we're using a set to store seen elements, the space complexity is O(n) as we might need to store up to n elements in the worst case.

Code Solution (Optimal)

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        s = set()
        for num in nums:
            if num in s:
                return True
            else:
                s.add(num)
        return False

# Time Complexity: O(n)
# Space Complexity: O(n)

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

class Solution {
public:
    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;
    }
};

import java.util.HashSet;
import java.util.Set;

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const seen = new Set();
    for (const num of nums) {
        if (seen.has(num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
};

Detailed Explanation

Understanding the Problem: Contains Duplicate

The “Contains Duplicate” problem is a foundational algorithmic task that asks whether any value appears more than once in a given integer array nums. If any element appears at least twice, the function should return true; if every element is distinct, it should return false.

Example:

Input: [1, 2, 3, 1] → Output: true (1 appears twice)
Input: [1, 2, 3, 4] → Output: false (no duplicates)

Why This Problem Matters

This problem is commonly asked in interviews and introduces you to basic data structures like hash sets. It sharpens your ability to trade time for space and shows the benefit of using efficient data lookups to avoid nested iteration. It's also highly relevant in real-world scenarios like checking for duplicate entries in data, logs, or transactions.

Naive Approach: Brute Force

The brute-force solution involves comparing each element with every other element that comes after it. If a match is found, we return true. If no matches are found after all comparisons, we return false.

While this approach is simple and works correctly, it requires O(n²) time due to the nested loop, which becomes impractical for large arrays.

Optimal Solution: Using a Set

The optimal solution leverages a hash set to track the elements we've already seen. Sets in most programming languages allow O(1) average time complexity for insertions and membership checks.

Here's the process:

Create an empty set called seen.
Iterate through each number num in the input array.
If num is already in seen, return true immediately (duplicate found).
If not, add num to seen.
If the loop completes without finding a duplicate, return false.

Example Walkthrough

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

Initialize seen = {}
Check 3 → not in seen → add → {3}
Check 1 → not in seen → add → {1, 3}
Check 4 → add → {1, 3, 4}
Check 2 → add → {1, 2, 3, 4}
Check 1 → already in seen → return true

Time and Space Complexity

Time Complexity: O(n), where n is the number of elements in the array. Each lookup and insertion into the set is done in constant time.
Space Complexity: O(n) in the worst case, to store up to n distinct elements in the set.

Edge Cases to Consider

Empty array → return false, since there are no duplicates.
Array with one element → return false, as there's nothing to compare.
Array with all identical values → return true
Array with all unique values → return false

Conclusion

The “Contains Duplicate” problem is an elegant example of how a simple data structure like a set can drastically improve performance over brute-force approaches. It reinforces key principles in algorithm design: using hash-based lookups to avoid redundant work and identifying opportunities to optimize nested iterations.

Get Personalized Support at AlgoMap Bootcamp 💡