Contains Duplicate

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• given an array filled with numbers
• can you determine if a duplicate is present in the array

What is Being Asked?

(One sentence on the actual task.)

• find whether there is a duplicate integer or not

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Nested loop is too wasteful
• Given its just regular numbers, we can use the unique property of Sets and solve this problem in two passes

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Iterate through the numbers
• Check whether the number already exists within our set
• If it does, you have found a duplicate
• If not, add it to the set and proceed to the next iteration

Why This Works

(Explain the core reason the solution is correct.)

• We can find whether a number exists in a set in O(1)
• If number already exists in the set then we have found our duplicate and can return True

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Sets
• Array

Time & Space Complexity

• Time: O(N) → Reason: Only going through the Array once
• Space: O(N) → Reason: Storing the full array if all items are unique once

Code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # brute force
        # Time: O(n^2)
        # Space: O(n)
        # for each item, check whether that item doesnt exist in the array
        # for i in range(len(nums)): 
        #     for j in range(i + 1, len(nums)):
        #         if nums[i] == nums[j]:
        #             return True

        # optimized solution - two pass
        # one pass to store all the values O(n)
        # another pass to iterate on each O(n)

        mySet = set() # 1,
        for num in nums:
            if num in mySet:
                return True
            mySet.add(num)
        
        return False