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.
1. 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.