↓Skip to main content

LeetCode 217: Contains Duplicate

2022-08-21·1 min· ·

LeetCode Easy Array Hash-Table Sorting

Author

Wei Yi Chung

Working at the contributing of open source, distributed systems, and data engineering.

Table of Contents

Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2022-08-21

Submissions: Wrong Answer → Accepted → Wrong Answer → Accepted ×4

Approach
#

set(nums) drops duplicates, so a shorter length means a repeat (Hash Table). To stop early, add elements to a set while scanning and return True on the first one already present.

My Attempts
#

In both 2022-08 and 2022-10 I wrote len(set(nums)) == len(nums), the exact opposite, returning True when there is no duplicate. != passed.

Solution
#

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

Complexity
#

Time O(n), space O(n).

Mistakes to Avoid
#

A repeat exists when the lengths differ; do not invert it.

Interview Explanation
#

I add numbers to a set while scanning and report a duplicate as soon as one is already present, in O(n) time and space; comparing the set’s length with the array’s also works.

Related

LeetCode 169: Majority Element

2022-08-20·2 mins

LeetCode Easy Array Hash-Table Divide-and-Conquer Sorting

LeetCode 169 note: Boyer-Moore voting, where different values cancel in pairs and the survivor is the one appearing more than half the time

LeetCode 219: Contains Duplicate II

2022-08-21·2 mins

LeetCode Easy Array Hash-Table Sliding-Window

LeetCode 219 note: a hash map stores each value’s last index; only the most recent occurrence needs a distance check

LeetCode 1: Two Sum

2019-09-14·2 mins

LeetCode Easy Array Hash-Table

LeetCode 1 note: store seen numbers in a hash map while scanning and look up target - x; checking before storing prevents using one element twice

LeetCode 202: Happy Number

2022-08-21·1 min

LeetCode Easy Hash-Table Math Two-Pointers Floyds-Cycle-Finding-Algorithm

LeetCode 202 note: repeatedly take the sum of squared digits, which reaches 1 or enters a cycle; detect it with a set of seen numbers or fast and slow pointers

LeetCode 205: Isomorphic Strings

2022-08-21·2 mins

LeetCode Easy Hash-Table String

LeetCode 205 note: characters must map one to one; it holds when the distinct characters and distinct pairs all have the same count

LeetCode 228: Summary Ranges

2022-08-21·2 mins

LeetCode Easy Array

LeetCode 228 note: scan once, extending the current range when a number continues the previous one and opening a new range otherwise, then format