NEETCODE - Two Pointers: Two Integer Sum II

From O(n²) brute force to O(n) two-pointer technique

Technology: Python, Algorithms
Skill: Two Pointers, O(n)

Problem Statement

Given an array of integers numbers that is sorted in non-decreasing order, find two numbers that add up to a specific target number.

Return the indices of the two numbers (1-indexed) as [index1, index2] where index1 < index2.

Key Constraints:

• The array is already sorted
• Exactly one solution exists
• Must use O(1) additional space
• Cannot use the same element twice
• Return 1-indexed positions (not 0-indexed)

Example:

Input: numbers = [1,2,3,4], target = 3
Output: [1,2]

Explanation:
1 + 2 = 3
index1 = 1, index2 = 2 (1-indexed)

Constraints:

2 <= numbers.length <= 1000
-1000 <= numbers[i] <= 1000
-1000 <= target <= 1000

Solutions Progression

Approach 1: Brute Force (Nested Loops)

def twoSum(numbers: List[int], target: int) -> List[int]:
    n = len(numbers)

for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]  # 1-indexed

return []

Time Complexity: O(n²)

• Outer loop runs n times
• Inner loop runs (n-1), (n-2), ..., 1 times
• Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²)

Space Complexity: O(1)

• Only using two loop variables, no additional data structures

Why this approach works:

• Checks every possible pair exhaustively
• Guaranteed to find the solution if it exists

Trade-offs:

• ✅ Simple to understand and implement
• ✅ O(1) space meets constraint
• ❌ Ignores the sorted property completely
• ❌ Wastes time checking impossible pairs

Approach 2: Hash Map (Complement Lookup)

def twoSum(numbers: List[int], target: int) -> List[int]:
    seen = {}  # value -> index

for i, num in enumerate(numbers):
        complement = target - num

if complement in seen:
            return [seen[complement] + 1, i + 1]  # 1-indexed

seen[num] = i
    return []

Time Complexity: O(n)

• Single pass through array: O(n)
• Hash lookups are O(1) average case
• Total: O(n)

Space Complexity: O(n)

• Worst case: store all n elements in hash map

Why this approach works:

• For each number, check if its complement exists
• Store numbers we've seen for instant lookup

Trade-offs:

• ✅ Optimal time complexity
• ✅ Works on unsorted arrays too
• ❌ Violates the O(1) space constraint
• ❌ Doesn't leverage the sorted property

Approach 3: Two Pointers (Optimal) ⭐

def twoSum(numbers: List[int], target: int) -> List[int]:
    left = 0
    right = len(numbers) - 1

while left < right:
        current_sum = numbers[left] + numbers[right]

if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1   # Need larger sum
        else:
            right -= 1  # Need smaller sum

return []

Time Complexity: O(n) Detailed breakdown:

• Each iteration moves one pointer
• Left pointer moves from 0 → n-1 (worst case)
• Right pointer moves from n-1 → 0 (worst case)
• Total pointer movements: At most n steps
• Each step does O(1) work (addition, comparison)
• Result: O(n)

Mathematical justification:

• At each step, we eliminate at least one index from consideration
• Start with n possible positions, end with 0
• Maximum iterations = n

Space Complexity: O(1)

• Only two pointer variables (left, right)
• No additional data structures

Why this approach works:

• The key insight is the sorted property:
  1. If sum is too small: numbers[left] must be too small
     • All pairs with numbers[left] will be too small
     • Move left pointer right to get larger values
  2. If sum is too large: numbers[right] must be too large
     • All pairs with numbers[right] will be too large
     • Move right pointer left to get smaller values
  3. Convergence guarantee:
     • Pointers move toward each other
     • Eventually meet at the solution or exhaust all pairs

Trade-offs:

• ✅ Optimal time: O(n)
• ✅ Optimal space: O(1)
• ✅ Leverages sorted property perfectly
• ✅ Elegant and intuitive
• ❌ Only works on sorted arrays

Pattern Recognition

Core Algorithmic Pattern: Two Pointers (Opposite Ends)

This is a fundamental pattern where:

1. Start with pointers at opposite ends of a sorted array
2. Move pointers based on comparison logic
3. Converge toward the solution

Key Insight That Unlocks the Problem

The sorted property + two pointers = O(n) without extra space Most people's first instinct is hash map (from regular Two Sum). The breakthrough is recognizing:

• "Sorted" means we can make directional decisions
• If sum is wrong, we know exactly which pointer to move
• No need to remember anything → O(1) space

Bridge to Real Systems

Where This Algorithm Lives in Production

1. Database Query Optimization
   • PostgreSQL's merge join uses this exact pattern:

   -- When joining two sorted tables
   SELECT * FROM table1
   JOIN table2 ON table1.id = table2.id
   ORDER BY table1.id;
   

2. Network Protocol - TCP Congestion Control
   • TCP's Fast Retransmit uses two pointers tracking:
3. Git Merge Algorithm
   • Git's three-way merge uses pointers to traverse sorted commit histories:
4. Redis Sorted Sets (ZRANGEBYLEX)
   • Redis uses two-pointer logic for range queries on sorted sets:
5. Google's MapReduce - Merge Phase
   • When combining sorted outputs from reducers:

Complexity Summary Table

Winner: Two Pointers - O(n) time, O(1) space, leverages sorted property perfectly.