Two Sum II — Input Array Is Sorted

Medium

two-pointersarraybinary-search

Given a 1-indexed array of integers nums sorted in non-decreasing order and an integer target, find two numbers that add up to target and return their 1-based indices i < j. Exactly one solution exists; use only O(1) extra space.

Input

Line 1: space-separated integers nums (sorted)
Line 2: integer target

Output

The two 1-based indices, space-separated.

Example 1

Input:

2 7 11 15
9

Output:

1 2

2 + 7 = 9 → indices 1 and 2.

Example 2

Input:

-1 0
-1

Output:

1 2

Constraints

2 ≤ nums.length ≤ 3·10^4
nums is sorted in non-decreasing order
Exactly one valid pair exists.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Two Sum II — Input Array Is Sorted

Medium

two-pointersarraybinary-search

Input

Line 1: space-separated integers nums (sorted)
Line 2: integer target

Output

The two 1-based indices, space-separated.

Example 1

Input:

2 7 11 15
9

Output:

1 2

2 + 7 = 9 → indices 1 and 2.

Example 2

Input:

-1 0
-1

Output:

1 2

Constraints

2 ≤ nums.length ≤ 3·10^4
nums is sorted in non-decreasing order
Exactly one valid pair exists.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.