Skip to main content

#121. Contains Duplicate | LeetCode Python Solution

Problem​

LeetCode Problem

  1. Contains Duplicate

Contains Duplicate - Brute Force Approach​

Algorithm​

The algorithm for the naive solution is to use nested loops:

  • The outer loop iterates over the entire list
  • The inner loop iterates the remaining of the list to check if there is a duplicate

Implementation​

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for idx1 in range(len(nums)):
            for idx2 in range(idx1+1, len(nums)):
                num1 = nums[idx1]
                num2 = nums[idx2]
                if num1 == num2:
                    return True

        return False

Complexity Analysis​

Time complexity: O(n^2).

We're using nested loops. For each element, we try to find its duplicate by looping through the rest of the array which takes O(n) time. Therefore, the time complexity is O(n^2).

Space complexity: O(1).

We are not using any extra space with this solution. The space required does not depend on the size of the input array, so only constant space is used.

Contains Duplicate - Sorting Approach​

Algorithm​

Another approach is to sort the input list as a pre-preprocessing step. The idea is that if there are any duplicate integers, they will be consecutive after sorting. We can then use two pointers technique to loop through the list to check if there is a pair of consecutive numbers having the same value.

This approach employs sorting algorithm. Since comparison sorting algorithm like heapsort is known to provide O(nlogn) worst-case performance, sorting is often a good preprocessing step. After sorting, we can sweep the sorted array to find if there are any two consecutive duplicate elements.

Implementation​

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # Sort the list first
        nums.sort()

        i = 0
        while i < len(nums) - 1:
            currNum = nums[i]
            nextNum = nums[i+1]
            if currNum == nextNum:
                return True

            i += 1

        return False

Complexity Analysis​

Time complexity: O(nlogn). Sorting is O(nlogn) in the worst case scenario and iterating through the list with 2 pointers is O(n). Therefore, the entire algorithm is dominated by the sorting step, which is O(nlogn).

Space complexity: O(1). Space depends on the sorting implementation which usually costs O(1) extra space if Heap Sort is used. Heap Sort is an in-place designed sorting algorithm, the space requirement is constant and therefore, O(1).

Contains Duplicate - Set Approach​

Algorithm​

We can also utilize a dynamic data structure, Set, that supports fast search and insert operations. Both operations are constant time O(1) on average. Therefore, by using Python Set data structure, we can achieve linear time complexity for finding the duplicate in an unsorted array.

Implementation​

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # Keep track of numbers visited so far
        visited = set()

        for currNum in nums:
            if currNum in visited:
                return True
            else:
                visited.add(currNum)

        return False

Complexity Analysis​

Time complexity: O(n). We iterate the list with n elements only once. Each set lookup or insert only takes O(1) constant time. Therefore, the time complexity is O(n).

Space complexity: O(n). The space required depends on the number of items stored in the set, which stores at most n elements in the worst case.