Contains Duplicate

This is problem #1 in NeetCode's Arrays & Hashing section of problems.

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1:

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

Output: true

Example 2:

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

Output: false

The code is stubbed out as follows:

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

I've solved this one a couple of times now, so here's my solution:

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hash_table = {}
        
        for num in nums:
            if num in hash_table:
                return True
            hash_table[num] = True

        return False

My original solution was probably something with a run time complexity of O(n²). I did end up looking up a better solution, which is what you see above. However, I've solved it enough times from memory that it's the only version I can think of whenever I see this problem.

So let's talk about how it works. We use a hash table, which has a lookup speed of O(1). If nums=[1,2,3,3], then as we iterate through nums, hash_table changes as follows:

num = 1
hash_table = { 1: True }

num = 2
hash_table = { 1: True, 2: True }

num = 3
hash_table = { 1: True, 2: True, 3: True }

num = 3

When num = 3 for the second time (due to the for-loop), when we do a hash table lookup via if num in hash_table, we do in fact find that there is already an instance of 3, so we immediately return True. It's worth noting that the actual value we store in the key-value pairs in the dictionary is irrelevant. In other words, we can update the code as follows:

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hash_table = {}
        
        for num in nums:
            if num in hash_table:
                return True
            hash_table[num] = "some random value that is never used"

        return False

And the code will still work and pass the test cases. The only reason we care about the hash table is because it gives us O(1) lookups.