Two Sum II - Input Array Is Sorted

▶

Steps

setup

Initialize main loop with i = 0

Select the first element at index 0 (value 2) to find its complement.

💡 We start by fixing one number and searching for its complement to reach the target sum.

Line:

for i in range(n):
    complement = target - numbers[i]

💡 The algorithm iterates over each element to find a matching complement using binary search.

setup

Calculate complement for i=0

Calculate complement = target - numbers[i] = 9 - 2 = 7 to find in the subarray after index 0.

💡 Finding the complement is essential to know what value to search for in the remaining array.

Line:

complement = target - numbers[i]

💡 The complement is the exact value needed to pair with the current element to reach the target.

setup

Initialize binary search with left=1, right=3

Set binary search boundaries to the subarray after i: left=1, right=3 to search for complement 7.

💡 Binary search requires defining the search range within the array after the current element.

Line:

j = binary_search(numbers, i + 1, n - 1, complement)

💡 Setting left and right pointers defines the current search space for the complement.

compare

Calculate mid = 2 for binary search

Calculate mid index as 2 (middle of left=1 and right=3) to check the value at mid.

💡 Midpoint calculation is key to divide the search space in binary search.

Line:

mid = left + (right - left) // 2

💡 Mid index splits the search range to efficiently narrow down the search.

compare

Compare numbers[mid]=11 with complement=7

Since 11 > 7, move right pointer to mid - 1 = 1 to search left half.

💡 Comparison decides which half of the array to discard next.

Line:

if arr[mid] == target:
    return mid
elif arr[mid] < target:
    left = mid + 1
else:
    right = mid - 1

💡 Because 11 is greater than the complement, the complement must be in the left half.

compare

Recalculate mid = 1 with updated right=1

Calculate new mid index as 1 (between left=1 and right=1) to check the value at mid.

💡 Recalculating mid after pointer update narrows the search further.

Line:

mid = left + (right - left) // 2

💡 Mid now points to the only element left in the search range.

compare

Compare numbers[mid]=7 with complement=7

Value at mid equals complement, so binary search returns mid index 1.

💡 Finding the complement confirms the pair that sums to the target.

Line:

if arr[mid] == target:
    return mid

💡 Binary search successfully located the complement in the array.

reconstruct

Return result indices [1, 2]

Return the 1-based indices of the current element (i=0) and complement (j=1) as [1, 2].

💡 Indices are converted to 1-based as per problem requirement before returning.

Line:

return [i + 1, j + 1]

💡 The solution pair indices are returned as the final answer.

reconstruct

Algorithm terminates with answer

The algorithm ends after returning the indices of the two numbers that sum to the target.

💡 The search stops as soon as the pair is found, demonstrating efficiency.

Line:

return [i + 1, j + 1]

💡 Early termination upon finding the solution avoids unnecessary computations.

finalize

Binary search loop ends after finding complement

Binary search loop terminates as complement is found, confirming no further search is needed.

💡 Understanding loop termination helps grasp binary search efficiency.

Line:

return mid

💡 Binary search stops immediately upon finding the target, avoiding extra iterations.

def binary_search(arr, left, right, target):
    while left <= right:  # STEP 3,4,5,6,7 loop
        mid = left + (right - left) // 2  # STEP 4,6
        if arr[mid] == target:  # STEP 7
            return mid
        elif arr[mid] < target:  # STEP 5
            left = mid + 1
        else:
            right = mid - 1
    return -1

def two_sum_binary_search(numbers, target):
    n = len(numbers)
    for i in range(n):  # STEP 1
        complement = target - numbers[i]  # STEP 2
        j = binary_search(numbers, i + 1, n - 1, complement)  # STEP 3
        if j != -1:  # STEP 7
            return [i + 1, j + 1]  # STEP 8
    return []

if __name__ == '__main__':
    print(two_sum_binary_search([2,7,11,15], 9))  # Output: [1, 2]

📊

Two Sum II - Input Array Is Sorted - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how binary search efficiently finds the complement, avoiding brute force checks.

traverse

i

2

0

7

1

11

2

15

3

traverse

i

2

0

7

1

11

2

15

3

compare

i

2

0

left

7

1

11

2

right

15

3

compare

i

2

0

left

7

1

mid

11

2

right

15

3

move_right

i

2

0

right

7

1

mid

11

2

15

3

compare

i

2

0

mid

7

1

11

2

15

3

record

i

2

0

mid

7

1

11

2

15

3

record

i

2

0

j

7

1

11

2

15

3

Result: [1,2]

record

i

2

0

j

7

1

11

2

15

3

Result: [1,2]

record

i

2

0

mid

7

1

11

2

15

3

Result: [1,2]

Key Takeaways

✓ Binary search efficiently finds the complement by halving the search space each step.

This efficiency is hard to see from code alone but clear when watching pointer movements and comparisons.

✓ The complement calculation guides the binary search target, linking the two-pointer and binary search concepts.

Understanding this link helps grasp why the algorithm avoids brute force.

✓ Pointer updates (left, right, mid) directly reflect decisions to discard half the search space.

Seeing these pointer moves visually clarifies how binary search narrows down the search quickly.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. You are given an array representing heights of vertical lines on the x-axis. You want to find two lines that together with the x-axis form a container, such that the container holds the maximum amount of water. Which algorithmic approach guarantees finding the optimal solution in O(n) time?

easy

A. Two pointers starting at opposite ends, moving the pointer at the shorter line inward.

B. Brute force by checking all pairs of lines and calculating their container area.

C. Dynamic programming to store maximum areas for subproblems of line pairs.

D. Greedy approach moving the pointer at the taller line inward to maximize area.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding two lines that maximize the container area, which depends on the minimum height and the distance between lines.

2. Step 2: Analyze algorithmic approaches

   Brute force (checking all pairs) is O(n²), dynamic programming is unnecessary and inefficient here, and moving the pointer at the taller line can miss optimal solutions. The two-pointer approach moving the pointer at the shorter line inward guarantees checking all promising pairs efficiently in O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach with shorter line pointer movement -> O(n) optimal [OK]

Hint: Two pointers move inward from ends, shorter line pointer moves [OK]

Common Mistakes:

• Moving pointer at taller line instead of shorter line
• Using DP unnecessarily
• Assuming greedy on taller line pointer works

3. What is the time complexity of the optimal 3Sum solution that sorts the array and uses a hash set for the two-sum complement search for each fixed element?

medium

A. O(n^3) because of nested loops and hash set operations

B. O(n^2) because for each element, we scan the rest with a hash set lookup in O(1)

C. O(n log n) due to sorting and linear two-pointer scans

D. O(n^2 log n) because sorting and hash set insertions dominate

Solution

1. Step 1: Identify sorting cost

   Sorting takes O(n log n), which is dominated by later steps.

2. Step 2: Analyze nested loops and hash set usage

   Outer loop runs n times; inner loop runs up to n times; hash set operations inside inner loop are O(1) each, but overall complexity is O(n^2).

3. Step 3: Clarify complexity of hash set approach

   The hash set approach inside the inner loop leads to O(n^2) complexity, not O(n^3).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Hash set lookups are O(1), so total is O(n^2) [OK]

Hint: Sorting O(n log n) < O(n²) nested loops dominate [OK]

Common Mistakes:

• Confusing hash set insertions as O(n)
• Thinking sorting dominates
• Assuming triple nested loops remain

4. What is the time complexity of the optimal two-pointer solution for the Container With Most Water problem, and why?

medium

A. O(n^2) because each pointer moves multiple times and all pairs are checked.

B. O(n) because each pointer moves inward at most n times, scanning the array once.

C. O(n log n) due to sorting or binary search steps involved.

D. O(1) because only constant space and operations are used.

Solution

1. Step 1: Analyze pointer movements

   Each pointer starts at opposite ends and moves inward only when the shorter line pointer moves, so total moves per pointer ≤ n.

2. Step 2: Count total operations

   Since pointers move inward without revisiting positions, total iterations ≤ n, making time complexity O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer linear scan -> O(n) time [OK]

Hint: Two pointers each move at most n times -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing space complexity with time
• Thinking sorting is required

5. Examine the following code snippet intended to check if a string is a valid palindrome ignoring case and non-alphanumeric characters. Which line contains a subtle bug that can cause incorrect results on inputs like "A man, a plan, a canal: Panama"?

def isPalindrome(s: str) -> bool:
    cleaned = [ch for ch in s if ch.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left].lower() != cleaned[right].lower():
            return False
        left += 1
        right -= 1
    return True

medium

A. Line 5: if cleaned[left].lower() != cleaned[right].lower(): (case normalization done here)

B. Line 2: cleaned = [ch for ch in s if ch.isalnum()] (missing lowercasing during cleaning)

C. Line 4: while left < right: (correct loop condition)

D. Line 7: right -= 1 (correct pointer decrement)

Solution

1. Step 1: Identify where case normalization occurs

   Case normalization is done inside the loop condition, not during cleaning.

2. Step 2: Understand impact of missing lowercasing in cleaning

   Since cleaned list stores original case, repeated .lower() calls in loop are inefficient but correct; however, this is not a bug causing incorrect results.

3. Step 3: Re-examine line 2

   Line 2 does not lowercase characters, but line 5 does, so no bug here.

4. Step 4: Check for subtle bug

   Actually, no bug in case normalization, but if line 2 did not skip non-alphanumeric characters, that would cause errors. Here, line 2 correctly filters non-alnum.

5. Step 5: Reconsider options

   None of the lines have a bug causing incorrect results on the example input.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Missing lowercasing in cleaning is not a bug since it's done later [OK]

Hint: Case normalization can be done either during cleaning or comparison [OK]

Common Mistakes:

• Not skipping non-alphanumeric characters
• Not normalizing case consistently
• Off-by-one errors in pointer movement