Lecture Notes: Contains Duplicate Problem

Overview

• Problem: Given an array of numbers, return true if any value appears at least twice; otherwise, return false if all values are distinct.
• Example: [1, 2, 3, 1] -> Output: true because 1 appears twice.

Brute Force Approach

• Idea: Compare each element with every other element.
• Steps:
  1. For each number, compare it to all other numbers in the array.
• Time Complexity:
  • Each element comparison takes O(n) time.
  • Total time complexity is O(n^2).
• Space Complexity: O(1) (no extra memory needed).

Sorting Approach

• Idea: Sort the array first and then check for adjacent duplicates.
• Steps:
  1. Sort the array.
  2. Iterate through the sorted array and check adjacent elements for duplicates.
• Time Complexity:
  • Sorting takes O(n log n).
  • One pass through the array takes O(n).
  • Overall time complexity is O(n log n).
• Space Complexity: O(1) (ignoring the sorting algorithm's space).

Hash Set Approach

• Idea: Use a hash set to track seen elements and detect duplicates in O(1) time.
• Steps:
  1. Initialize a hash set.
  2. Iterate through the array:
  • Check if the element is already in the hash set.
  • If so, return true (duplicate found).
  • Otherwise, add the element to the hash set.
  3. If no duplicates are found, return false.
• Time Complexity: O(n) (single pass and O(1) hash set operations).
• Space Complexity: O(n) (space for hash set can grow up to the size of the input array).

Code Implementation (Hash Set Approach)

# Initialize hash set
seen = set()

# Iterate through the array
for num in nums:
    if num in seen:
        return True
    seen.add(num)

# If no duplicates found, return False
return False

Summary

• Three approaches to solve the Contains Duplicate problem: Brute Force, Sorting, and Hash Set.
• Hash Set approach is the most efficient with O(n) time complexity and O(n) space complexity.

Conclusion

• Efficient algorithms use additional space to improve time complexity.
• Hash Set is a useful data structure for checking membership in O(1) time.

Additional Notes

• Consider joining the presenter's Patreon for further support and more content.