Two Sum II - Input Array Is Sorted

Updated on 02 July, 2025
Two Sum II - Input Array Is Sorted header image

Problem Statement

The task involves an array of integers numbers that is sorted in non-decreasing order. You are to find two distinct numbers in the array such that they sum up to a specific target value. We denote these two numbers as numbers[index1] and numbers[index2], where the position constraints are 1 <= index1 < index2 <= numbers.length. The requirement is to return the indices of these two numbers, incremented by one to transform from a 0-based index to a 1-based index, resulting in a two-element array [index1, index2]. It is guaranteed that there is one unique solution for the given input, and the solution must not use more than constant space.

Examples

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].

Constraints

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

Approach and Intuition

Given the constraints and the problem requirements, a two-pointer technique is ideally suited for this problem for the following reasons:

  1. The numbers array is already sorted. This sorting allows for an efficient approach where increasing and decreasing pointers can effectively find two numbers that sum to a target.

  2. By initializing two pointers, one at the beginning (left pointer) and one at the end (right pointer) of the array, we can adjust these pointers based on the sum of the numbers[left] and numbers[right].

  3. The detailed steps involved with this approach are:

  4. Initialize two pointers: left at the start (index 0) and right at the end (index numbers.length - 1).

  5. While the left pointer is less than the right pointer:

    1. Calculate the sum of the numbers at the two pointers: current_sum = numbers[left] + numbers[right].

    2. If current_sum is equal to the target, return the indices of these numbers as [left + 1, right + 1] (adjusted for 1-based indexing).

    3. If current_sum is less than the target, it implies that we need a larger sum. Thus, move the left pointer one step to the right (left++) to increase the sum.

    4. If current_sum is more than the target, it implies that we need a smaller sum. Thus, move the right pointer one step to the left (right--) to decrease the sum.

This method leverages the sorted nature of the array to efficiently find the two numbers, ensuring the use of only constant extra space and linear time complexity.

Solutions

  • C++
cpp
class Solution {
public:
    vector<int> findTwoSum(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            if (currentSum == target) {
                return {left + 1, right + 1};
            } else if (currentSum < target) {
                ++left;
            } else {
                --right;
            }
        }
        return {-1, -1}; // Return statement if no two sum solution is found.
    }
};

This function, findTwoSum, works with a sorted integer array to determine two elements that sum up to a specific target. Utilize a two-pointer technique to efficiently find these elements, where one pointer starts at the beginning (left) and the other at the end (right) of the array.

The process involves:

  • Incrementing the left pointer when the sum of the numbers at both pointers is less than the target, suggesting the need for a larger sum.
  • Decrementing the right pointer when their sum surpasses the target, indicating a smaller sum is required.
  • On finding a match where the sum equals the target, the function returns the positions of these two numbers as a vector, adjusting for 1-based indexing (hence left + 1 and right + 1).

If no such pair exists in the array that meets the target sum, the function returns {-1, -1}.

Ensure that this C++ code is understood to effectively apply the two-pointer method on sorted arrays for searching specific sums.

  • Java
java
class Solution {
    public int[] findTwoSum(int[] nums, int targetSum) {
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int currentSum = nums[start] + nums[end];
    
            if (currentSum == targetSum) {
                return new int[] { start + 1, end + 1 };
            } else if (currentSum < targetSum) {
                ++start;
            } else {
                --end;
            }
        }
        return new int[] { -1, -1 };
    }
}

This article provides a solution to the problem of finding two indices in a sorted array whose values sum up to a specific target number. The solution uses Java, featuring a straightforward two-pointer approach to efficiently solve the problem.

In the provided Java method findTwoSum, you work with a nums array of integers and a targetSum. Initialize two pointers: start points to the beginning of the array and end points to the last element. Use a loop to check combinations of numbers at these pointers:

  • Calculate currentSum by adding the values at the start and end pointers.
  • If currentSum matches targetSum, return the 1-based indices of these numbers.
  • If currentSum is less than targetSum, increment the start pointer to explore larger sums.
  • If currentSum is greater, decrement the end pointer to explore smaller sums.

If no pairs are found that meet the criteria, return {-1, -1} as an indication.

This technique ensures a time complexity of O(n) by eliminating the need for a nested loop, making it highly efficient for sorted arrays. The distinct focus on using two pointers allows exploiting the sorted nature of the array to skip unnecessary comparisons, contributing to the overall efficiency of the algorithm.

  • C
c
int* findTwoSum(int* nums, int numsLength, int targetSum, int* outputSize) {
    int start = 0;
    int end = numsLength - 1;
    *outputSize = 2;
    while (start < end) {
        int currentSum = nums[start] + nums[end];
    
        if (currentSum == targetSum) {
            int* solution = malloc((*outputSize) * sizeof(int));
            solution[0] = start + 1;
            solution[1] = end + 1;
            return solution;
        } else if (currentSum < targetSum) {
            start++;
        } else {
            end--;
        }
    }
    int* solution = malloc((*outputSize) * sizeof(int));
    solution[0] = -1;
    solution[1] = -1;
    return solution;
}

The given solution in C aims to find two numbers from a sorted array such that their sum equals a specified target number. Here is a concise summary of how the function operates:

  • Initialize two pointers, start to the beginning of the array and end to the last element.
  • Use a while loop to continue processing as long as start is less than end.
  • Calculate the sum of the elements at the start and end indexes.
  • Compare the calculated sum with the target:
    • If they match, allocate memory for a result array, store the 1-based positions of the elements, and return the array.
    • If the calculated sum is less than the target, increment the start pointer to move right, thus increasing the sum.
    • If the calculated sum is greater than the target, decrement the end pointer to move left, thus decreasing the sum.
  • If no matching elements are found by the time the loop exits, allocate memory for the result array, set both elements to -1 indicating no solution, and return the array.

This approach efficiently utilizes the properties of a sorted array to find the solution in linear time, making it optimal for larger data sets.

  • JavaScript
js
var findTwoSum = function (nums, goal) {
    let start = 0;
    let end = nums.length - 1;
    while (start < end) {
        let currentSum = nums[start] + nums[end];
    
        if (currentSum == goal) {
            return [start + 1, end + 1];
        } else if (currentSum < goal) {
            start++;
        } else {
            end--;
        }
    }
    return [-1, -1];
};

The provided JavaScript function, findTwoSum, effectively solves the problem of finding two numbers in a sorted array that add up to a specific target, known as goal. The implementation utilizes a two-pointer technique to efficiently search for the required pair. Here’s a closer look at how the solution works:

  1. Initialize two pointers, start at the beginning (0-index) of the array and end at the last index.

  2. Use a while loop to iterate through the array as long as start is less than end.

  3. Calculate the sum of the numbers pointed by the start and end pointers.

  4. If the sum equals the goal, return the indices of the two numbers adjusted by 1 (to change from 0-based to 1-based index).

  5. If the sum is less than the goal, increment the start pointer to increase the sum.

  6. If the sum is greater than the goal, decrement the end pointer to decrease the sum.

  7. If no pair is found by the end of the loop, return [-1, -1] indicating no solution.

This method is optimal for sorted arrays and runs with a time complexity of O(n), where n is the number of elements in the input array. Adjusting the pointers based on the comparison of the current sum and the goal allows the method to skip unnecessary elements, which results in the linear time complexity.

  • Python
python
class Solution:
    def findTwoSum(self, nums: List[int], goal: int) -> List[int]:
        left = 0
        right = len(nums) - 1
        while left < right:
            current_sum = nums[left] + nums[right]
    
            if current_sum == goal:
                return [left + 1, right + 1]
            elif current_sum < goal:
                left += 1
            else:
                right -= 1
        return [-1, -1]

This guide walks through a solution for finding two numbers in a sorted array that sum up to a specific target. This Python solution uses a two-pointer technique to identify the indices of the two numbers.

  • Initialize two pointers, left starting at the beginning of the array and right at the end.
  • Iterate through the array using a while loop until left is less than right.
    • Calculate current_sum of the elements at the left and right pointers.
    • If current_sum matches the goal, return the 1-based indices of these elements as a list [left + 1, right + 1].
    • If current_sum is less than the goal, increment the left pointer to explore higher sums.
    • If current_sum is greater than the goal, decrement the right pointer to explore lower sums.
  • If no suitable pair is found by the time the while loop exits, return [-1, -1] to indicate failure.

This method efficiently leverages the sorted nature of the array, achieving a time complexity of O(n) by eliminating the need for a nested loop.

Comments

No comments yet.