Contains Duplicate — Day 56(Python)

Photo by Sigmund on Unsplash

Today’s problem is an easy tagged question on leetcode. Let us look into the question.

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

One of the easiest ways to solve this problem is by sorting. Using the sorting function, we can sort our array. After sorting, we can check if any of the adjacent elements are equal. In case any of the adjacent numbers are equal, we will return True, else we will return False.

Let us look into the code snippet.

class CheckDuplicate:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                return True
        return False

Complexity analysis.

Time Complexity

We are using python’s inbuilt sorting function. The time complexity for the sorting function is O(NlogN), where N is the number of elements in the list.

Space Complexity.

We are not using any extra data structure hence the space complexity is O(1).

Can we try to improve the Time complexity? What if we use an extra data structure?

We will be traversing through the list. We can use a dictionary to check if the number is already visited before. Let us look into the code snippet.

class CheckDuplicate:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dict_num = dict()
        for num in nums:
            if num in dict_num:
                return True
            else:
                dict_num[num] = 1
        return False

Complexity analysis.

Time Complexity

We are traversing through the list once, therefore the time complexity is O(N), where N is the number of elements.

Space Complexity.

We are using a dictionary to store the elements in the list, therefore the space complexity is O(N), where N is the count of numbers in the list.