167. Two Sum II - Input Array Is Sorted

Intuition

Given a sorted array, the problem requires finding two numbers that add up to a specific target. The key insight is to leverage the sorted property of the array, which allows us to use a two-pointer approach efficiently. By starting with one pointer at the beginning and the other at the end of the array, we can adjust the pointers based on the sum of the values they point to, effectively narrowing down the search space.

Approach

1. Initialize Pointers: Start with two pointers, left at the beginning (index 0) and right at the end (index length - 1) of the array.
2. Iterate with Two Pointers: - Calculate the sum of the elements at the left and right pointers. - If the sum equals the target, return the 1-based indices [left + 1, right + 1]. - If the sum is greater than the target, decrement the right pointer to reduce the sum. - If the sum is less than the target, increment the left pointer to increase the sum.
3. Return Result: Since the problem guarantees exactly one solution, the loop will find and return the correct indices.

Complexity

Time Complexity:

O(n), where n is the length of the array. Each element is processed at most once by the two pointers.

Space Complexity:

O(1), as the solution only uses a constant amount of extra space for the two pointers and variables.

Code

C++

#include 
using namespace std;
class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        int left = 0;
        int right = numbers.size() - 1;
        while (left < right) {
            int total = numbers[left] + numbers[right];
            if (total == target) {
                return {left + 1, right + 1};
            } else if (total > target) {
                right--;
            } else {
                left++;
            }}
        return {};
    }
};

Python

from typing import List
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total > target:
                right -= 1
            else:
                left += 1
        return []  # This line is never reached if there is a valid solution as per problem constraints.

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int total = numbers[left] + numbers[right];
            if (total == target) {
                return new int[]{left + 1, right + 1};
            } else if (total > target) {
                right--;
            } else {
                left++;
            }
        }
        return new int[]{};
    }
}

JavaScript

var twoSum = function (numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    while (left < right) {
        let total = numbers[left] + numbers[right];
        if (total === target) {
            return [left + 1, right + 1];
        } else if (total > target) {
            right--;
        } else {
            left++;
        }
    }
};