Skip to main content
DSA patterns

Contains Duplicate

easyArrays and hashing Must-doAccentureWiproTCSAmazon

Problem statement

You are given a list of integers nums. Return true if any value shows up two or more times in the list, and false if every value is different.

Think of nums as a list of ports handed out to different services. Before deploying, you want a quick check: was the same port accidentally given to two services?

Examples

Example 1

Input: nums = [1, 2, 3, 1]

Output: true

Explanation: The value 1 shows up at index 0 and again at index 3, so the list has a duplicate.

Example 2

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

Output: false

Explanation: Every value in the list is different, so there is no duplicate.

Example 3

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

Output: true

Explanation: Several values repeat here (1, 3, 4 and 2 each show up more than once), so a duplicate exists — the list can have more than one repeated value, but only one true/false answer is needed.

Hints

Hint 1: Comparing every pair of values works, but think about how many pairs there are for a list of n numbers — can you avoid checking most of them?

Approach

Optimal: Hash set

Intuition

Sorting works, but it spends effort putting the whole list in order when all you actually need is a fast way to ask "have I seen this value before?". A hash set answers that question in roughly constant time, so a single pass through the list — checking and then remembering each value — is enough.

For each value, check whether it is already in the set. If it is, you've found a duplicate immediately, without needing to look at the rest of the list. If not, add it to the set and move on.

Steps

  1. Create an empty set called seen.
  2. Walk through nums, looking at one value x at a time.
  3. If x is already in seen, a duplicate is found — return true.
  4. Otherwise, add x to seen and continue.
  5. If the loop finishes with no match, return false.

Edge case: a list with zero or one value can never contain a duplicate — the set never has a chance to already hold the single value being checked, so the loop correctly falls through to false.

Complexity

Time O(n) - a single pass over the list, and each set lookup or insert takes constant time on average

Space O(n) - in the worst case (no duplicate at all) the set ends up holding every value in the list

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


if __name__ == "__main__":
    print(str(Solution().containsDuplicate([1, 2, 3, 1])).lower())  # true
    print(str(Solution().containsDuplicate([1, 2, 3, 4])).lower())  # false
    print(str(Solution().containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2])).lower())  # true
RecapThe whole problem in a few lines, for the night before
  • Spot it: "does any value repeat?" in an unsorted list
  • Idea: keep a set of values seen so far; the first value already in the set is a duplicate
  • Cost: O(n) time, O(n) space (sorting first: O(n log n) time, O(n) space for a copy, or O(1) extra if sorted in place)
  • Trap: comparing every pair works but is O(n²) — too slow once the list gets into the tens of thousands
  • Remember: len(set(nums)) != len(nums) is a correct one-liner, but it always scans the whole list; the loop version can stop at the first duplicate

Interview follow-ups

  • What if you need to return the duplicate value itself, not just whether one exists?

    Use the same hash set, but instead of returning true the moment you find a match, save that value and either return it right away (if you only need the first duplicate) or keep scanning and collect every repeated value into a list. The time stays O(n); you just do something with the match instead of stopping immediately.

  • The list is too large to fit in memory and arrives as a stream. What would you do?

    An exact answer still needs to remember every value seen so far, so you either shard the stream by hash (equal values always land in the same shard, so you can check each shard on its own, smaller machine) or accept a small chance of error using a fixed-memory structure like a Bloom filter, which can say "no duplicate" with certainty but only "probably a duplicate" when it flags one.

Frequently asked questions

That one-liner is correct and also O(n) — a set can only hold each distinct value once, so if the set ends up smaller than the original list, something repeated. The loop version does the same amount of work in the worst case, but it can return true the moment it spots the first duplicate, instead of always building the entire set first.

When memory is limited and you're allowed to reorder the input. Sorting in place needs almost no extra memory (O(1) beyond the sort itself), while the hash set approach can grow to hold every value in the list. The trade-off is that sorting changes the order of the caller's data, which may not be acceptable.

Both cases correctly return false in every approach here — there's no second value to compare against, so no duplicate can exist.

Starting the inner loop at the same index as the outer one instead of one past it. If both loops start at 0, the code ends up comparing every value with itself (nums[i] == nums[i] is always true), which reports a duplicate even when the list has none. Starting the inner loop at i + 1 guarantees the two indices are always different.

Checking a list of hostnames, IPs, ports or config keys for repeats is a real pre-deploy sanity check. The same "have I seen this before" set is also the first building block for deduplicating alerts or collapsing repeated log lines.