Two Sum

▶

Steps

setup

Create list of (index, value) pairs

We pair each number with its original index to keep track after sorting.

💡 This step preserves original indices so we can return correct positions after sorting.

Line:

nums_with_index = list(enumerate(nums))

💡 We now have a list of tuples linking each number to its original index.

setup

Sort the list by value

We sort the list of (index, value) pairs by the value to prepare for two-pointer search.

💡 Sorting allows us to use two pointers efficiently to find the target sum.

Line:

nums_with_index.sort(key=lambda x: x[1])

💡 The list is now ordered by values but still keeps original indices.

setup

Initialize left and right pointers

Set left pointer at start (0) and right pointer at end (3) of the sorted list.

💡 Two pointers will move inward to find the pair summing to target.

Line:

left, right = 0, len(nums) - 1

💡 Pointers mark the current candidates for sum comparison.

compare

Calculate sum of values at left and right

Sum values at left (2) and right (15) pointers: 2 + 15 = 17.

💡 We check if this sum matches the target to decide pointer movement.

Line:

current_sum = nums_with_index[left][1] + nums_with_index[right][1]

💡 Sum is greater than target, so we need to reduce it by moving right pointer.

shrink

Compare sum to target and move right pointer

Since 17 > 9, move right pointer left from 3 to 2 to try smaller sum.

💡 Moving right pointer inward reduces the sum because array is sorted ascending.

Line:

right -= 1

💡 Pointer movement is guided by sum comparison to target.

compare

Calculate sum at new pointers

Sum values at left (2) and right (11): 2 + 11 = 13.

💡 Check if this sum matches target or requires pointer movement.

Line:

current_sum = nums_with_index[left][1] + nums_with_index[right][1]

💡 Sum still greater than target, so right pointer will move again.

shrink

Move right pointer left again

Since 13 > 9, move right pointer from 2 to 1 to try smaller sum.

💡 Continuing to reduce sum by moving right pointer inward.

Line:

right -= 1

💡 Pointer moves systematically narrow down candidates.

compare

Calculate sum at new pointers

Sum values at left (2) and right (7): 2 + 7 = 9.

💡 Check if sum equals target to find solution.

Line:

current_sum = nums_with_index[left][1] + nums_with_index[right][1]

💡 Sum equals target, so we found the correct pair.

reconstruct

Return original indices of the pair

Return the original indices [0, 1] of the numbers 2 and 7 that sum to target.

💡 Returning original indices is the goal, showing the solution found.

Line:

return [nums_with_index[left][0], nums_with_index[right][0]]

💡 The algorithm successfully maps sorted positions back to original indices.

reconstruct

Final state with answer

The algorithm ends with the answer [0, 1], the indices of the two numbers summing to target.

💡 This final state confirms the solution and shows the entries involved.

💡 The final output matches the expected result, validating the approach.

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    nums_with_index = list(enumerate(nums))  # STEP 1
    nums_with_index.sort(key=lambda x: x[1])  # STEP 2
    left, right = 0, len(nums) - 1  # STEP 3
    while left < right:
        current_sum = nums_with_index[left][1] + nums_with_index[right][1]  # STEP 4,6,8
        if current_sum == target:  # STEP 8
            return [nums_with_index[left][0], nums_with_index[right][0]]  # STEP 9
        elif current_sum < target:  # Not used in this example
            left += 1
        else:
            right -= 1  # STEP 5,7

📊

Two Sum - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how sorting and two pointers work together to efficiently find the solution without checking every pair.

insert

0→2

1→7

2→11

3→15

update

0→2

1→7

2→11

3→15

check

0→2

1→7

2→11

3→15

check

0→2

3→15

1→7

2→11

check

0→2

1→7

2→11

3→15

check

0→2

2→11

1→7

3→15

check

0→2

1→7

2→11

3→15

check

0→2

1→7

2→11

3→15

check

0→2

1→7

2→11

3→15

Result: [0,1]

check

0→2

1→7

2→11

3→15

Result: [0,1]

Key Takeaways

✓ Sorting the array with original indices preserved enables efficient two-pointer search.

This insight is hard to see from code alone because the index preservation is subtle but crucial.

✓ Two pointers move inward based on sum comparison, narrowing search space without checking all pairs.

Visualizing pointer moves clarifies how the algorithm avoids brute force.

✓ When the sum equals the target, the algorithm immediately returns the original indices, completing the search.

Seeing the exact moment of equality and return helps understand the stopping condition.

Practice

1. Consider the following code snippet implementing the optimal approach for longest consecutive sequence. What is the value of max_len returned when the input is [1, 9, 3, 10, 2]?

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Identify sequence starts

   Numbers are {1,2,3,9,10}. Sequence starts are numbers where num-1 not in set: 1 and 9.

2. Step 2: Count consecutive lengths

   From 1: sequence is 1,2,3 -> length 3. From 9: sequence is 9,10 -> length 2. Max length is 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest consecutive sequence is [1,2,3] length 3 [OK]

Hint: Only count sequences starting at numbers without predecessor [OK]

Common Mistakes:

• Counting sequences from every number causing duplicates
• Off-by-one errors in length counting
• Confusing max length with total unique numbers

2. You are given an integer array and need to find the k elements that appear most frequently. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a frequency map and bucket sort to group elements by their frequency, then collect top k from highest frequency buckets.

B. Sort the entire array and pick the top k elements by frequency.

C. Use a greedy approach that picks elements as they appear until k elements are chosen.

D. Use dynamic programming to build frequency counts and select top k elements.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding top k frequent elements efficiently, ideally in linear time.

2. Step 2: Identify approach with linear time complexity

   Bucket sort groups elements by frequency, allowing O(n) time retrieval of top k elements by scanning buckets from high to low frequency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort approach is known to run in O(n) time for this problem [OK]

Hint: Bucket sort groups by frequency for O(n) retrieval [OK]

Common Mistakes:

• Sorting entire array is O(n log n), not optimal
• Greedy approach ignores frequency counts
• DP is unrelated to frequency counting here

3. Identify the bug in the following Python code for detecting duplicates:

medium

A. Line 2: initializing the set should be a list

B. Line 6: returning False outside the loop is incorrect

C. Line 4: adding the number before checking membership causes always True

D. Line 5: the membership check should use 'not in' instead of 'in'

Solution

1. Step 1: Analyze the order of operations

   The code adds the number to the set before checking if it is already present, so the membership check always returns True on the first iteration.

2. Step 2: Identify the bug

   Membership check must occur before adding the number to avoid false positives.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding before checking membership causes immediate True return [OK]

Hint: Check membership before adding to avoid false positives [OK]

Common Mistakes:

• Adding before checking membership
• Misplacing return statements
• Confusing set initialization

4. What is the time complexity of the optimal hash set approach for finding the longest consecutive sequence in an array of size n?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n) because each number is processed at most twice

C. O(n²) because of nested loops checking consecutive numbers

D. O(n) average but O(n²) worst case due to hash collisions

Solution

1. Step 1: Analyze outer loop

   The outer loop iterates over each unique number once.

2. Step 2: Analyze inner while loop

   Each number is visited at most once in the inner loop when counting consecutive sequences, so total work is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set lookups are O(1), total linear time [OK]

Hint: Each element visited once in sequence counting [OK]

Common Mistakes:

• Assuming sorting is involved causing O(n log n)
• Confusing nested loops as O(n²)
• Overestimating hash collision impact

5. Suppose the problem changes: now elements can be reused multiple times, and you want the top k elements by total frequency including duplicates. Which modification to the optimal bucket sort approach correctly handles this?

hard

A. Use the same bucket sort approach since frequencies already count duplicates.

B. Modify frequency counting to count unique elements only, then apply bucket sort.

C. Use a min-heap to track top k elements dynamically as frequencies update with reuse.

D. Sort the entire nums array and pick the top k elements by frequency.

Solution

1. Step 1: Understand reuse changes frequency dynamics

   Elements can appear multiple times dynamically, so frequencies update continuously.

2. Step 2: Bucket sort is static and cannot handle dynamic frequency updates

   Min-heap allows maintaining top k elements efficiently as frequencies change.

3. Step 3: Choose min-heap approach for dynamic top k tracking

   Min-heap keeps size k and updates with new frequencies, suitable for reuse scenario.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Bucket sort is static; min-heap adapts to frequency changes [OK]

Hint: Dynamic frequency updates require min-heap, not bucket sort [OK]

Common Mistakes:

• Assuming bucket sort works with dynamic reuse
• Counting unique elements only loses frequency info
• Sorting entire array is inefficient