Last updated on January 29th, 2025 at 02:16 am

Here, we see a Two Sum II – Input Array Is Sorted LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Binary Search, Two-Pointers

Companies

Amazon

Level of Question

Medium

Two Sum II – Input Array Is Sorted LeetCode Solution

1. Problem Statement

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[index₁] and numbers[index₂] where 1 <= index₁ < index₂ <= numbers.length.

Return the indices of the two numbers, index₁ and index₂, added by one as an integer array [index₁, index₂] 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].

2. Coding Pattern Used in Solution

The coding pattern used in this code is Two Pointers. This pattern is commonly used when dealing with sorted arrays or linked lists to find pairs or subarrays that satisfy a specific condition. In this case, the two pointers (l and r) are used to traverse the array from both ends to find two numbers that sum up to the target.

3. Code Implementation in Different Languages

3.1 Two Sum II – Input Array Is Sorted C++

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

    while (numbers[l] + numbers[r] != target)
      if (numbers[l] + numbers[r] < target)
        ++l;
      else
        --r;

    return {l + 1, r + 1};
  }        
};

3.2 Two Sum II – Input Array Is Sorted Java

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

    while (numbers[l] + numbers[r] != target)
      if (numbers[l] + numbers[r] < target)
        ++l;
      else
        --r;

    return new int[] {l + 1, r + 1};        
    }
}

3.3 Two Sum II – Input Array Is Sorted JavaScript

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

3.4 Two Sum II – Input Array Is Sorted Python

class Solution(object):
    def twoSum(self, numbers, target):
        l = 0
        r = len(numbers) - 1

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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)

The algorithm assumes the input array is sorted. If the array is not sorted, it would need to be sorted first, which would add an O(n log n) time complexity for the sorting step.
The use of 1-based indexing in the return value is specific to the problem requirements (e.g., LeetCode’s “Two Sum II – Input Array Is Sorted”).
The algorithm is efficient and optimal for this problem due to the sorted nature of the input and the use of the Two Pointers pattern.