LeetCode 217 - Contains Duplicate

This is an Easy array problem. Given an integer array, return true if any value appears at least twice, and false if every value is unique. I used it to compare three approaches: brute force, sorting, and a hash set.

Problem link and explanation

Problem link: 217. Contains Duplicate
Summary: Given an integer array nums, return true if the array contains any duplicate value. Otherwise, return false.

For example:

nums = [1, 2, 3, 1]

The value 1 appears twice, so the answer is true. If the input is [1, 2, 3, 4], every value is unique, so the answer is false.

The problem is simple, but it is useful for comparing where each approach spends time and memory. Checking every pair uses almost no extra memory but costs more time. Using a set reduces the time cost but stores values proportional to the input size.

Approach

I am going to write more coding-test solutions in Python from here, partly to get more comfortable with the ML ecosystem.

1. Brute force pair comparison

The most direct approach is to compare every pair of values. Compare the first value with all later values, then the second value with all values after it, and so on.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True

        return False

This uses no extra data structure, so the extra space is O(1). The comparison count grows quickly, though. With n elements, the number of pairs is close to n², so the time complexity is O(n²).

2. Sort and compare adjacent values

A better time complexity than brute force can be achieved by sorting first. Once the array is sorted, equal values sit next to each other, so I only need to compare adjacent elements.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()

        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True

        return False

The sorting step makes the time complexity O(n log n). The duplicate check after sorting is just one linear scan.

The space complexity is the part worth checking. Python’s list.sort() sorts the list in place, so it can look like there is no extra array. But Python uses Timsort, and Timsort can use auxiliary space proportional to the input size in the worst case. I would describe this approach as O(n) extra space conservatively.

That is different from how I usually think about C++ std::sort, which is often described with around O(log n) stack space. The same high-level idea, sorting first, can have different space-complexity details depending on the language and runtime implementation.

3. Track seen values with a hash set

The first approach that came to mind was to keep a set of values I had already seen. While scanning the array from left to right, if the current value is already in the set, I can return true immediately. Otherwise, I add it to the set and continue.

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

        for num in nums:
            if num in seen:
                return True
            seen.add(num)

        return False

This fits the requirement directly because the question only asks whether a duplicate exists. If a duplicate appears early, the function returns early. In the worst case, it still scans the array once.

The trade-off is memory. If every value is unique, the set eventually holds n values.

Complexity analysis

1. Brute force

Time complexity: O(n²)
- Every pair can be compared, so the number of comparisons grows quadratically.
Space complexity: O(1)
- It only uses index variables and no additional data structure.

2. Sorting

Time complexity: O(n log n)
- Sorting dominates the cost, and the adjacent comparison pass is O(n).
Space complexity: O(n)
- Python’s Timsort may use auxiliary space proportional to the input size in the worst case.

3. Hash set

Time complexity: O(n)
- Each value is visited once. Set membership checks and insertions are average-case O(1).
Space complexity: O(n)
- If all values are unique, the set stores n values.

Optimized code

For this problem, the hash set approach is the most natural final version. Since I only need to know whether a value has appeared before, remembering the values seen so far is enough.

from typing import List

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

        for num in nums:
            if num in seen:
                return True
            seen.add(num)

        return False

Summary and reflection

This problem was useful because the same requirement can be solved with three different trade-offs. Brute force uses almost no extra memory but costs too much time. Sorting improves the time complexity, but the sorting cost and the language’s sorting implementation matter. A hash set uses extra memory but answers the actual question, have I seen this value before, directly.

The part I had to correct was Python sorting space complexity. I initially thought about it like C++ std::sort, but Python’s Timsort can use O(n) extra space in the worst case. When I choose sorting in an algorithm problem, I should check not only the O(n log n) time cost but also the sorting algorithm used by the language.