217. Contains Duplicate
Problem Statement and Starter Code
Given an array called NUMS, if an element has a duplicate in the array, return True. Otherwise, return False.
Initial, Naive Solution
Ok so the above is my first, naive solution. Since we're looking for a duplicate, we can look for the mode of the array.
To do this, we use the built-in Python function max.
Max takes set(nums) as input, which is effectively a hash set that has no duplicates, and sorts through it using the key to compare elements, in this case, the key counts how many times the element appears in the array.
Then we see what the count of the mode is via nums.count(mode) and if it's greater than 1 we've found a duplicate and return True.
The issue with this is that nums.count in the key is O(n) because we search each element to see if it's included, and then we do this for all the n elements in the array, so we have overall O(n^2).
This is why this solution fails Leetcode's tests because it exceeds the timelimit (implying there is a better solution).
Revised Solution
The above is a fairly good solution. We return whether it is not equal via the !=. So we return a boolean as desired.
We also think about what we're comparing. We're comparing the hash set (which contains no duplicates) to the length of the original array.
It makes sense that if the length of the set and the length of the array aren't the same, then a duplicate must have been dropped to make the set.