Contains Duplicate

▶

Steps

setup

Initialize empty hash set

Create an empty hash set 'seen' to track numbers encountered.

💡 This set will store unique numbers for quick membership checks.

Line:

seen = set()

💡 The set starts empty, ready to track numbers.

compare

Check if 1 is in set

Look up number 1 in the empty set to check for duplicates.

💡 Checking membership tells if the number is new or duplicate.

Line:

if num in seen:

💡 1 is not found, so no duplicate yet.

insert

Insert 1 into set

Add 1 to the set since it was not found.

💡 Adding the number allows future duplicate detection.

Line:

seen.add(num)

💡 Set now contains 1.

compare

Check if 2 is in set

Check if 2 is already in the set {1}.

💡 Each number is checked to detect duplicates early.

Line:

if num in seen:

💡 2 is new, no duplicate yet.

insert

Insert 2 into set

Add 2 to the set since it was not found.

💡 Adding 2 updates the set for future checks.

Line:

seen.add(num)

💡 Set now contains {1, 2}.

compare

Check if 3 is in set

Check if 3 is already in the set {1, 2}.

💡 Membership check is repeated for each number.

Line:

if num in seen:

💡 3 is new, no duplicate yet.

insert

Insert 3 into set

Add 3 to the set since it was not found.

💡 Adding 3 updates the set for future checks.

Line:

seen.add(num)

💡 Set now contains {1, 2, 3}.

compare

Check if 1 is in set again

Check if the last number, 1, is already in the set {1, 2, 3}.

💡 This check detects if a duplicate exists.

Line:

if num in seen:

💡 1 is found, so a duplicate exists and algorithm will return true.

reconstruct

Prepare to return true due to duplicate

The algorithm has detected a duplicate and is about to return true.

💡 Early return saves time by avoiding unnecessary checks.

Line:

return True

💡 Duplicate confirmed, algorithm terminates.

reconstruct

Return true and terminate

Return true immediately because a duplicate was found, ending the algorithm.

💡 This final step confirms the algorithm's output and stops further processing.

Line:

return True

💡 The algorithm terminates early upon detecting a duplicate, demonstrating efficiency.

def containsDuplicate(nums):
    seen = set()  # STEP 1: Initialize empty set
    for num in nums:
        if num in seen:  # STEP 2,4,6,8: Check membership
            return True  # STEP 9,10: Return on duplicate
        seen.add(num)  # STEP 3,5,7: Insert new number

if __name__ == '__main__':
    print(containsDuplicate([1,2,3,1]))  # True

📊

Contains Duplicate - Watch the Algorithm Execute, Step by Step

Watching each membership check and insertion helps you understand how hash sets efficiently detect duplicates without scanning the entire array repeatedly.

insert

empty map

check

Lookup: 1→ false

empty map

insert

1→true

check

Lookup: 2→ false

1→true

insert

1→true

2→true

check

Lookup: 3→ false

1→true

2→true

insert

1→true

2→true

3→true

check

Lookup: 1→ true

1→truelookup

2→true

3→true

Result: true

check

Lookup: 1→ true

1→truelookup

2→true

3→true

Result: true

check

Lookup: 1→ true

1→truelookup

2→true

3→true

Result: true

Key Takeaways

✓ Using a hash set allows constant-time membership checks to detect duplicates efficiently.

This is hard to see from code alone because the speed and early termination are implicit, but the visualization shows each check and insert explicitly.

✓ The algorithm returns immediately upon finding the first duplicate, saving unnecessary work.

Seeing the early return in action clarifies why this approach is optimal compared to scanning all pairs.

✓ Each insertion grows the set, building a record of seen numbers that prevents repeated scanning.

Visualizing the set growing step-by-step helps understand how the algorithm accumulates knowledge about the input.

Practice

1. You are given a binary array and need to find the length of the longest contiguous subarray with an equal number of 0s and 1s. Which algorithmic approach guarantees an optimal O(n) time solution?

easy

A. Brute force nested loops checking all subarrays for equal 0s and 1s

B. Prefix sum combined with a hash map to track first occurrences of prefix sums

C. Dynamic programming storing counts of 0s and 1s separately for all subarrays

D. Greedy approach expanding subarrays while counts of 0s and 1s remain equal

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest contiguous subarray with equal 0s and 1s efficiently.

2. Step 2: Identify algorithmic pattern

   Using prefix sums transformed by treating 0 as -1, and a hash map to store earliest prefix sum indices, allows O(n) time detection of subarrays with zero sum difference.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Prefix sum + hash map is classic for equal 0/1 subarray [OK]

Hint: Prefix sums + hash map track equal 0s and 1s efficiently [OK]

Common Mistakes:

• Thinking greedy can find longest equal 0/1 subarray
• Using DP that tracks counts separately is inefficient
• Brute force is correct but not optimal

2. Consider the following Python function to find the longest contiguous subarray with equal number of 0s and 1s. What is the returned value when the input is [0, 1, 0, 1]?

def findMaxLength(nums):
    prefix_sum = 0
    seen = {0: -1}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

easy

A. 4

B. 2

C. 3

D. 0

Solution

1. Step 1: Trace prefix sums and seen map

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}, max_length=0 Index 1: num=1 -> prefix_sum=0, seen has 0 at -1, max_length=max(0,1-(-1))=2 Index 2: num=0 -> prefix_sum=-1, seen has -1 at 0, max_length=max(2,2-0)=2 Index 3: num=1 -> prefix_sum=0, seen has 0 at -1, max_length=max(2,3-(-1))=4

2. Step 2: Return max_length

   max_length is 4, the length of the entire array.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Full array balanced, max_length=4 [OK]

Hint: Prefix sums track balance; max length updates on repeated sums [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Ignoring initial seen entry for sum 0
• Confusing prefix sum updates

3. Consider the following Python code implementing the Two Sum problem using sorting and two pointers. What is the output when calling two_sum([3, 2, 4], 6)?

easy

A. [1, 0]

B. [0, 2]

C. [2, 1]

D. [1, 2]

Solution

1. Step 1: Sort nums with indices

   nums_with_index = [(0,3), (1,2), (2,4)] sorted by value -> [(1,2), (0,3), (2,4)]

2. Step 2: Two pointers check sums

   left=0 (value=2), right=2 (value=4), sum=6 equals target -> return indices [1, 2]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sum found at indices 1 and 2 matching target 6 [OK]

Hint: Sort with indices, then two pointers find correct pair [OK]

Common Mistakes:

• Returning values instead of indices
• Mixing up left and right indices
• Off-by-one errors in pointer movement

4. What is the time complexity of the optimal prefix sum + hash map solution for checking if a continuous subarray sum is a multiple of k, given an input array of length n and integer k?

medium

A. O(n * k)

B. O(n^2)

C. O(n)

D. O(k)

Solution

1. Step 1: Analyze the main loop over n elements

   The algorithm iterates once over the array, performing O(1) operations per element.

2. Step 2: Consider hash map operations and modulo computations

   Hash map lookups and insertions are average O(1), modulo operations are O(1), so total is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming modulo k affects complexity multiplicatively
• Thinking hash map size depends on k linearly

5. Consider the following buggy get method for the time-based key-value store. Which line contains the subtle bug that causes incorrect results when querying timestamps less than the smallest stored timestamp?

medium

A. Line 6: Returning empty string if i == 0

B. Line 2: Checking if key not in store

C. Line 5: Using bisect_left instead of bisect_right

D. Line 7: Returning values[i-1]

Solution

1. Step 1: Understand difference between bisect_left and bisect_right

   bisect_left returns insertion index to the left, which can cause off-by-one errors when timestamp equals stored timestamps.

2. Step 2: Identify impact on retrieval

   Using bisect_left causes incorrect index i for timestamps equal to stored ones, leading to wrong value or empty string returned.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   bisect_right is required to get correct insertion point for retrieval [OK]

Hint: bisect_right needed to get correct insertion index [OK]

Common Mistakes:

• Using bisect_left instead of bisect_right
• Incorrect boundary check for i==0
• Returning wrong index value