Two Sum II - Input Array Is Sorted

• Difficulty: Medium
• Topics: Array, Two Pointers, Binary Search
• Link: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Problem Description

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Solution

1. Problem Deconstruction

Technical Restatement
Given a sorted 1-indexed integer array numbers and target integer target, find the unique pair of distinct indices (i,j) where numbers[i] + numbers[j] = target and 1 ≤ i < j ≤ n. Return [i,j] as a 1-indexed array. The solution must maintain O(1) auxiliary space complexity.

Beginner-Friendly Version
You have a list of numbers that’s already sorted from smallest to largest. Each position in the list is numbered starting from 1 (not 0). Find exactly two different positions where the numbers at those positions add up to your target number. Return the position numbers as a list. There’s always exactly one correct answer, and you can’t use the same position twice.

Mathematical Formulation
Let numbers be a sorted sequence a₁ ≤ a₂ ≤ ... ≤ aₙ with n ≥ 2. Find the unique ordered pair (i,j) such that:

• 1 ≤ i < j ≤ n
• aᵢ + aⱼ = target
• Solution exists and is unique by problem guarantee

Constraint Analysis

• 2 ≤ numbers.length ≤ 3×10⁴: Eliminates O(n²) brute force (would require ~900M operations)
• -1000 ≤ numbers[i] ≤ 1000: Enables safe integer arithmetic without overflow concerns
• Sorted non-decreasing order: Enables binary search and two-pointer techniques
• -1000 ≤ target ≤ 1000: Constrains sum ranges, enables early termination optimizations
• Exactly one solution: No need to handle multiple solution cases
• Constant extra space: Eliminates hash table approaches (O(n) space)

Edge Cases Implied by Constraints

• Minimal input size (n=2): Only one possible pair
• Negative numbers and zero: Valid inputs requiring proper signed arithmetic
• Target smaller than smallest element sum: Impossible by solution guarantee
• Duplicate values: Possible but handled by sorted property

---

2. Intuition Scaffolding

Real-World Analogy: Library Book Search
Imagine a library with books arranged by page count (sorted). You need two books whose page counts sum to a specific total. Instead of checking every combination (O(n²)), start with the thinnest and thickest books. If their sum is too large, replace the thickest with a slightly thinner one. If too small, replace the thinnest with a slightly thicker one. This converges to the solution in O(n) time.

Gaming Analogy: RPG Potion Crafting
You have sorted potion strengths and need exactly two that combine to a specific power level. Starting with weakest and strongest potions, adjust your selection based on whether the combination is overpowered or underpowered, moving inward until the perfect combination is found.

Mathematical Analogy: Bisection Method
Similar to root-finding for a monotonic function f(i,j) = numbers[i] + numbers[j] - target, we perform a coordinated search from both ends of the domain, leveraging the sorted property to guarantee convergence.

Common Pitfalls

1. Global Min/Max Fallacy: The smallest and largest elements don’t necessarily form the solution
2. Binary Search Misapplication: Searching for target - numbers[i] for each i is O(n log n) instead of optimal O(n)
3. Hash Table Temptation: Violates constant space requirement despite O(n) time
4. Over-Engineering: Adding unnecessary complexity for a problem with elegant two-pointer solution
5. Index Conversion Errors: Forgetting to convert between 0-indexed and 1-indexed representations

---

3. Approach Encyclopedia

Approach 1: Brute Force Enumeration

Pseudocode:
for i from 0 to n-2:
    for j from i+1 to n-1:
        if numbers[i] + numbers[j] == target:
            return [i+1, j+1]  # Convert to 1-indexing

Complexity Proof

• Time: ∑_{i=0}^{n-2} (n - i - 1) = (n-1) + (n-2) + … + 1 = n(n-1)/2 ∈ O(n²)
• Space: O(1) auxiliary space Visualization

numbers: [2, 7, 11, 15], target: 9
i=0: 2+7=9 ✓ found
    2+11=13 ✗
    2+15=17 ✗
i=1: 7+11=18 ✗
    7+15=22 ✗
i=2: 11+15=26 ✗

Approach 2: Binary Search Complement

Pseudocode:
for i from 0 to n-2:
    complement = target - numbers[i]
    j = binary_search(numbers, complement, i+1, n-1)
    if j != -1:
        return [i+1, j+1]

Complexity Proof

• Time: (n-1) binary searches each O(log n) → O(n log n)
• Space: O(1) for iterative binary search implementation Visualization

numbers: [2, 7, 11, 15], target: 9
i=0: complement=7, search in [7,11,15] → found at index 1

Approach 3: Two-Pointer Technique (Optimal)

Pseudocode:
left = 0, right = n-1
while left < right:
    current_sum = numbers[left] + numbers[right]
    if current_sum == target:
        return [left+1, right+1]
    elif current_sum < target:
        left += 1  # Need larger sum
    else:
        right -= 1  # Need smaller sum

Complexity Proof

• Time: Each iteration eliminates one element → maximum n-1 iterations → O(n)
• Space: Only two pointers → O(1) Visualization

Step 0: [2, 7, 11, 15], L=0, R=3, sum=17 > target → R--
Step 1: [2, 7, 11, 15], L=0, R=2, sum=13 > target → R--  
Step 2: [2, 7, 11, 15], L=0, R=1, sum=9 = target ✓

---

4. Code Deep Dive

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1  # Initialize two pointers
    
    while left < right:  # Continue until pointers meet
        current_sum = numbers[left] + numbers[right]  # Calculate current pair sum
        
        if current_sum == target:
            # Found solution, convert to 1-indexing
            return [left + 1, right + 1]
        elif current_sum < target:
            # Sum too small, move left pointer rightward
            left += 1
        else:
            # Sum too large, move right pointer leftward
            right -= 1
    
    # Solution guaranteed by problem constraints
    return [-1, -1]  # Fallback (never reached)

Line-by-Line Analysis

• Line 2: Pointer initialization covers entire array range
• Line 4: Loop invariant: left < right ensures distinct elements
• Line 5: Sum calculation uses current pointer positions
• Lines 7-8: Early return upon finding solution with 1-index conversion
• Lines 9-12: Pointer movement leverages sorted property:
  • Smaller sum → need larger left element
  • Larger sum → need smaller right element

Edge Case Handling

• Example 1 ([2,7,11,15], 9): Converges in 3 iterations as shown in visualization
• Example 2 ([2,3,4], 6): Direct hit at first check (2+4=6)
• Example 3 ([-1,0], -1): Single iteration with negative numbers handled correctly
• Minimal case ([1,2], 3): Only one possible pair, found immediately
• Duplicate values ([1,1,2,2], 3): Still finds valid pair (1+2) despite duplicates

---

5. Complexity War Room

Hardware-Aware Analysis

• Array size up to 30,000 elements → ~240KB memory (assuming 8-byte integers)
• Fits comfortably in L2/L3 cache (typically 256KB-8MB)
• O(n) algorithm processes ~30K elements in microseconds on modern CPUs
• Memory access pattern is sequential/contiguous → cache-friendly

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Brute Force	O(n²)	O(1)	10/10	❌ Fails large N
Binary Search	O(n log n)	O(1)	8/10	✅ Acceptable
Two-Pointer	O(n)	O(1)	9/10	✅ Optimal

Performance Characteristics

• Best Case: O(1) when solution is at array extremes
• Worst Case: O(n) when solution is in middle
• Average Case: O(n) with constant factor ~n/2

---

6. Pro Mode Extras

Algorithm Variants

1. Three Sum Problem

   # Extension: Find all triplets summing to zero
   def threeSum(numbers):
       numbers.sort()
       result = []
       for i in range(len(numbers)-2):
           if i > 0 and numbers[i] == numbers[i-1]:
               continue
           left, right = i+1, len(numbers)-1
           while left < right:
               total = numbers[i] + numbers[left] + numbers[right]
               if total == 0:
                   result.append([numbers[i], numbers[left], numbers[right]])
                   # Skip duplicates
                   while left < right and numbers[left] == numbers[left+1]:
                       left += 1
                   while left < right and numbers[right] == numbers[right-1]:
                       right -= 1
                   left += 1
                   right -= 1
               elif total < 0:
                   left += 1
               else:
                   right -= 1
       return result
   

2. Two Sum with Multiple Solutions

   # Modified for multiple valid pairs
   def twoSumAllPairs(numbers, target):
       left, right = 0, len(numbers)-1
       result = []
       while left < right:
           current_sum = numbers[left] + numbers[right]
           if current_sum == target:
               result.append([left+1, right+1])
               # Find all pairs with current left
               temp = right
               while left < temp and numbers[left] + numbers[temp-1] == target:
                   result.append([left+1, temp])
                   temp -= 1
               left += 1
           elif current_sum < target:
               left += 1
           else:
               right -= 1
       return result
   

Interview Cheat Sheet

• First Mention: Always state time/space complexity upfront
• Sorted Array Insight: Immediately recognize two-pointer opportunity
• Edge Cases: Mention negative numbers, duplicates, minimal input
• Verification: Walk through examples to confirm logic
• Optimization Path: Brute Force → Binary Search → Two-Pointer

Mathematical Proof of Correctness
Given sorted array a₁ ≤ a₂ ≤ ... ≤ aₙ and target T, the two-pointer algorithm maintains the invariant that for any left and right, if a solution exists, it must satisfy i ∈ [left, n] and j ∈ [0, right]. Each iteration either finds the solution or reduces the search space by one element, guaranteeing termination in at most n-1 steps.