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.

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏