Two Sum II - Input Array Is Sorted - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Find two numbers in a sorted array that sum to a target and return their 1-based indices.
Get the length n of the input array numbers.
Initialize two pointers: l to 0 (start) and r to n-1 (end).
While l is less than r:
Compute the sum of numbers[l] and numbers[r].
If the sum equals the target, return a list with l+1 and r+1 (1-based indices).
If the sum is less than the target, increment l to try a larger number.
If the sum is greater than the target, decrement r to try a smaller number.

Code Solution

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

        while l < r:
            summ = numbers[l] + numbers[r]
            if summ == target:
                return [l + 1, r + 1]
            elif summ < target:
                l += 1
            else:
                r -= 1

# Time Complexity: O(n)
# Space Complexity: O(1)

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0;
        int r = numbers.size() - 1;

        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) {
                return {l + 1, r + 1};
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }

        throw invalid_argument("No two sum solution");
    }
};

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0;
        int r = numbers.length - 1;

        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) {
                return new int[] {l + 1, r + 1};
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }

        throw new IllegalArgumentException("No two sum solution");
    }
}

var twoSum = function(numbers, target) {
    let l = 0;
    let r = numbers.length - 1;

    while (l < r) {
        let sum = numbers[l] + numbers[r];
        if (sum === target) {
            return [l + 1, r + 1];
        } else if (sum < target) {
            l++;
        } else {
            r--;
        }
    }

    throw new Error("No two sum solution");
};

Detailed Explanation

Understanding the Problem: Two Sum II - Input Array Is Sorted

The “Two Sum II – Input Array Is Sorted” problem asks you to find two numbers in a sorted array that add up to a specific target and return their 1-based indices. The key insight is that the array is already sorted, which enables a much more efficient solution than brute-force searching.

Example:

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2] (because 2 + 7 = 9)

Why This Problem Matters

This problem is a classic use case for the two-pointer technique, optimized for sorted arrays. It emphasizes the importance of leveraging input constraints (sortedness) to improve performance, a key strategy in competitive programming and software engineering.

Brute Force vs. Optimized Approach

A brute-force method would check every pair of elements to find a match — which works but is inefficient at O(n²) time complexity. Thankfully, since the input array is sorted, we can solve it in linear time using a two-pointer approach.

Optimal Solution: Two Pointers

The two-pointer technique involves scanning the array from both ends toward the center. At each step, you check the sum of the elements pointed to by the left and right pointers.

Steps:

Initialize two pointers:
- left = 0 (start of array)
- right = numbers.length - 1 (end of array)
While left < right:
- Calculate sum = numbers[left] + numbers[right]
- If sum == target, return [left + 1, right + 1] (1-based indexing)
- If sum < target, increment left to increase the sum
- If sum > target, decrement right to decrease the sum

Example Walkthrough

Input: numbers = [2, 3, 4], target = 6

left = 0, right = 2 → 2 + 4 = 6
Match found → return [1, 3]

Time and Space Complexity

Time Complexity: O(n), where n is the number of elements. Each element is visited at most once.
Space Complexity: O(1), since the solution uses only two pointers and no extra data structures.

Edge Cases to Consider

Exactly two elements in array → only one pair to check
No valid pair (not possible per problem guarantees)
Multiple valid pairs (only the first one encountered is returned)
Negative numbers and zero handled correctly with same logic

Conclusion

The “Two Sum II” problem is an elegant demonstration of the power of two-pointer strategies. By leveraging the sorted nature of the input, we eliminate the need for nested loops and achieve linear performance with constant space usage. It's a textbook case for writing clean, efficient, and optimal code using minimal memory.

Get Personalized Support at AlgoMap Bootcamp 💡