DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Contains Duplicate - Solution
Solutions and explanations
Link to Problem StatementView on GitHubWatch Video

Video Explanation

This approach begins by sorting the input list, which brings any duplicates next to each other.
We then iterate through the list, comparing each element to its neighbor.

  • If two adjacent elements are equal, we’ve found a duplicate and return true.
  • If we reach the end without finding any duplicates, we return false.
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for idx in range(1, len(nums)):
            if nums[idx] == nums[idx - 1]:
                return True
        return False

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(n log n) — time taken by sorting dominates the overall complexity.

  • Space Complexity: O(1) or O(n)

    • O(1) if the sorting algorithm is in-place
    • Otherwise, O(n) if it requires additional space.

    This is depends on the internal implementation of the sorting algorithm.

This two-pass approach uses a frequency map (counter), which is typically implemented as a hash map or dictionary, to store the count of each element.

  • The first pass builds the frequency map.
  • And the second pass checks whether any element appears more than once.
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        freq = collections.Counter(nums)
        for cnt in freq.values():
            if cnt > 1:
                return True
        return False

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(n)
  • Space Complexity: O(n)

This is a one-pass approach that uses a hash set to track already seen elements.

  • If we encounter a value that already exists in the set, we’ve found a duplicate and return true.
  • Otherwise, we add it to the set and continue checking the remaining elements.
  • Finally, if no duplicate is found, we return false.
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        values_seen = set()
        for num in nums:
            if num in values_seen:
                return True
            values_seen.add(num)
        return False

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(n)
  • Space Complexity: O(n)

This approach detects duplicates in a single step by comparing the original length with the number of distinct elements.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) > len(set(nums))

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(n)
  • Space Complexity: O(n)