LeetCode: The “Contains Duplicate” Problem

Source: Dev.to

Problem Statement

“Does this list have the same number appearing more than once?”

Examples everyone understands:

• [3, 7, 1, 9] → false
• [3, 7, 3, 9] → true
• [5] → false
• [8, 8] → true
• [] → false

We need a reliable way to detect if any number appears more than once.

Naïve Human Approach

Imagine the list [4, 1, 7, 2, 9, 4, 8].

1. Take 4 → remember it
2. Take 1 → new → remember
3. Take 7 → new → remember
4. Take 2 → new → remember
5. Take 9 → new → remember
6. Take 4 → duplicate!

The algorithm: keep a memory of numbers seen; if you encounter a number already in memory, stop.

Naïve Python Implementation

def has_duplicate(nums):
    seen = []                # empty list = our memory

    for num in nums:         # look at each number one by one
        if num in seen:      # is it already in memory?
            return True      # yes → duplicate found
        seen.append(num)     # no → remember it

    return False             # no duplicates

Mental Run

Input: [4, 1, 7, 4] → returns True.

Complexity Issue

Checking num in seen on a list scans each element → O(n) per check.
Inside a loop over n elements, the total time becomes O(n²), which is unacceptable for large inputs (e.g., 100,000 elements).

Optimized Solution with a Set

A Python set provides near‑constant‑time membership tests (hash table lookup).

def has_duplicate(nums):
    seen = set()             # fast lookup structure

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

    return False

Now the algorithm runs in O(n) time and O(n) extra space.

Full LeetCode‑style Class

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

# Simple test
s = Solution()
nums = [1, 0, 2, 5, 8, 9, 1]
result = s.containsDuplicate(nums)
print(result)   # True

Running the code confirms the expected output.

Takeaways

• Choosing the right data structure (list vs. set) dramatically affects performance.
• Understanding time complexity helps you write scalable solutions.
• Translating human logic into efficient machine logic is a core skill for algorithmic problem solving.

These lessons apply beyond LeetCode:

• Designing APIs
• Optimizing backend systems
• Handling large datasets
• Preventing performance bottlenecks

---

This week I’m focused on hash maps and strings. Cheers to learning!