leetcode day 16: contains duplicate

Given an array of integers, is there at least one duplicate in it?

Again we’re counting things, but since we’re really caring about existence, the condition can be wrapped into the count loop:

func containsDuplicate(nums []int) bool {
    counts := map[int]int{}
    for i:=0; i < len(nums); i++ {
        if _, ok := counts[nums[i]]; ok {
            return true
        }
        counts[nums[i]]++
    }
    return false
}

We look to see if we’ve counted this at least once, and if we have, there’s no more work to do. If we never count something twice, then the answer is false, and we’ve only done one pass at the most over the array.

Speed 65%, memory 5%.

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

Better on memory because it uses an empty struct as the sentinel value instead of an int, and much faster: 94% CPU, 37% memory. Definitely going to put this in my bag of tricks.