LeetCode Two Sum II Explained: Two Pointer Approach in Python

Problem Overview

In the Two Sum II – Input Array Is Sorted problem, we are given a sorted array of integers and a target value. The task is to find two numbers such that their sum equals the target and return their 1-based indices.

Why Sorting Matters

The key constraint of this problem is that the input array is already sorted in non-decreasing order. This allows us to make informed decisions about how to move through the array without checking every possible pair.

Optimal Strategy: Two Pointer Technique

Instead of using a brute-force nested loop or a hash map, we can use two pointers to solve the problem in linear time. One pointer starts at the beginning of the array, and the other starts at the end.

How the Algorithm Works

1. Initialize a left pointer at the start of the array.
2. Initialize a right pointer at the end of the array.
3. Calculate the sum of the values at both pointers.
4. If the sum equals the target, return the 1-based indices of both pointers.
5. If the sum is greater than the target, move the right pointer left to reduce the sum.
6. If the sum is less than the target, move the left pointer right to increase the sum.

Python Implementation

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l = 0
        r = len(numbers) - 1

        while l < r:
            current_sum = numbers[l] + numbers[r]

            if current_sum == target:
                return [l + 1, r + 1]
            elif current_sum > target:
                r -= 1
            else:
                l += 1
  

Why This Approach Works

Because the array is sorted, moving the left pointer always increases the sum, and moving the right pointer always decreases the sum. This guarantees that no valid pair is skipped and that the solution is found efficiently.

Complexity Analysis

• Time Complexity: O(n), where n is the length of the array.
• Space Complexity: O(1), as no extra data structures are used.

Pattern Summary

This problem is a classic example of the two-pointer pattern applied to a sorted array. Instead of storing values or checking all pairs, pointer movement is guided by how the current sum compares to the target.

Mastering this pattern is essential for efficiently solving a wide range of array problems involving pairs, sums, or comparisons under sorted constraints.

```