217. Contains Duplicate

Problem Link

Brute Force: You can iterate twice over the Array to check if element from outer iteration is present using inner iteration. This would yield following runtime complexity: Time -> \(O(n^2)\), Space -> \(O(1)\)

We can optimize the operation of checking if an element is present from \(O(n)\) to \(O(1)\) using a data structure like HashSet which gives us constant time querying operation. The tradeoff being increase in space complexity to \(O(n)\), which majority of time is acceptable as memory isn't as scare as old days.

Pseudocode

• Iterate over the \(nums\) array. For each \(num\),
• check if the \(num\) is present in our hashset.
  • If yes, we can return immediately
  • Else, store current \(num\) in our hashset and continue.

Runtime Complexity

Time: \(O(n)\), since we're only iterating the nums array once and querying hashset, an \(O(1)\) operation.

Space: \(O(n)\), due to the hashset used for storing num.

PythonGo

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

func containsDuplicate(nums []int) bool {
    set := make(map[int]struct{})
    for _, num := range nums {
        if _, ok := set[num]; ok {
            return true
        }
        set[num] = struct{}{}
    }
    return false
}

Go HashSet Implementation

Go doesn't have any built-in HashSet type, but the idiomatic way to build one is using map[T]struct{}. This give has \(O(1)\) lookup over keys and has zero memory overhead from struct{}.

• To add any element: set["apple"] = struct{}{}
• To check presence of element: if _, ok := set["apple"]; ok

---