217. Contains Duplicate — LeetCode(Python)
I got you!
Problem:
Given an integer array nums
, return true
if any value appears at least twice in the array, and return false
if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
Solution:
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
dic = {}
for n in nums:
if n in dic:
return True
else:
dic[n] = 1
return False
Explanation:
We create a dictionary that stores all numbers in the array nums as keys and the values of these keys correspond to the number of times the key is present in the array.
If the key is not already present in the dictionary, we add it using:
else:
dic[n] = 1
If, however, the key is already present in the dictionary, this means that the number is repeated in the array. And thus, we return True:
if n in dic:
return True
Time and Space Complexity:
Since we need to iterate over the array nums once, the time complexity would depend on the length of nums, and would do so, linearly.
Since we store every(almost) element of the array nums in a dictionary, the space required is also a linear function of the length of the array nums.
Thus, if n is the length of the array nums,
Time Complexity: O(n)
Space Complexity: O(n)
Optimized Solution:
return not len(set(nums)) == len(nums)
This would see if the length of the array passed to the function is the same as the length of the set of all unique elements in the array. If it is, this means there are no repetitions, and opposite otherwise.
The time and space complexity is the same as above. This solution was just optimized in terms of lines of code.