mediumTwo Pointers

Two Sum II - Input Array Is Sorted

Find two values in a sorted array whose sum equals the target. Exactly one pair exists. Use constant extra space. Report their positions starting from 1, smaller first.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated integers on line 1. Values are nondecreasing. Line 2 contains the target.

Expected result

Two one-based positions separated by a space.

Case 1

Input

1 4 6 10
10

Expected output

2 3

Case 2

Input

2 2
4

Expected output

1 2

Case 3

Input

-4 -1 0 3
-1

Expected output

1 4

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Two sum on a sorted array, 1-based indices, exactly one pair. A hash map uses O(n) space. For each numbers[i] binary-search target-numbers[i] on the right. n ≤ 3 × 10^4, so O(nlog n) time and O(1) space.

Note that the array is sorted in non-decreasing order, so for each numbers[i], we can find the position of target - numbers[i] by binary search, and return [i + 1, j + 1] if it exists.

The time complexity is O(n × log n), where n is the length of the array numbers. The space complexity is O(1).

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0, n = numbers.length;; ++i) {
            int x = target - numbers[i];
            int l = i + 1, r = n - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (numbers[mid] >= x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (numbers[l] == x) {
                return new int[] {i + 1, l + 1};
            }
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.