DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Contains Duplicate

easyArrays and hashing Must-doGoogle SRE

Problem statement

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

Think of it as a quick sanity check on a list of IDs, such as instance IDs or port numbers pulled from several config files, before you treat them as unique.

Examples

Example 1

Input: nums = [4, 9, 2, 9]

Output: true

Explanation: 9 appears at index 1 and again at index 3.

Example 2

Input: nums = [8, 3, 5]

Output: false

Explanation: All three values are different.

Hints

Approach

Keep a set of every value seen so far. A set answers "have I seen this?" in constant time on average, so one pass is enough.

  1. Start with an empty set.
  2. For each value, if it is already in the set, return true.
  3. Otherwise add it and continue.
  4. If the loop finishes, return false.

In Java, Set.add returns false when the value was already present, which folds the check and the insert into one call.

ComplexityTime O(n)Space O(n)
Python
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

Follow-up questions

  • Return true only if two equal values are at most k positions apart.
  • The list is too large for memory and arrives as a stream. What would you do?

Frequently asked questions

That one-liner is correct and also O(n). The loop version is better when duplicates are common, because it stops at the first repeat instead of building the whole set.

When memory is tight and you are allowed to reorder the input. An in-place sort needs almost no extra space, while the set can grow to hold every value.

Checking that a list of hostnames, IPs or ports has no repeats is a real pre-deploy check. The same "have I seen this before" set is the first step in deduplicating alerts or log lines.