How do you approach Two Sum II - Sorted Input?

The array is sorted - a hash map works but ignores that structure (and uses O(n) space).

What is the time complexity of Two Sum II - Sorted Input?

Time complexity: O(n) - each pointer moves at most n steps. Space complexity: O(1) - just two indices.

What are common mistakes on Two Sum II - Sorted Input?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

gitGood.dev

← Back to problems

Two Sum II - Sorted Input

EasyAlgorithms

Description

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.

Return the indices of the two numbers as an array [index1, index2] of length 2, where 1 <= index1 < index2 <= numbers.length.

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 (1-indexed).

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.

Example 3

Input: numbers = [-1,0], target = -1

Output: [1,2]

Constraints

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

Two Sum II - Sorted Input: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

The array is sorted - a hash map works but ignores that structure (and uses O(n) space).
Start one pointer at the beginning and one at the end. What does the current sum tell you?
If the sum is too small, only moving the left pointer right can increase it; if too big, move the right pointer left.

The optimal approach

Show the approach: Converging Two Pointers

Because the array is sorted, start with the smallest and largest elements. If their sum is less than the target, the left pointer must move right (the only way to grow the sum). If greater, the right pointer must move left. Since exactly one solution exists, the pointers always converge on it.

Time: O(n) - each pointer moves at most n steps
Space: O(1) - just two indices

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.

← Back to problems

Two Sum II - Sorted Input

EasyAlgorithms

Description

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.

Return the indices of the two numbers as an array [index1, index2] of length 2, where 1 <= index1 < index2 <= numbers.length.

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 (1-indexed).

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.

Example 3

Input: numbers = [-1,0], target = -1

Output: [1,2]

Constraints

Two Sum II - Sorted Input: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

The array is sorted - a hash map works but ignores that structure (and uses O(n) space).
Start one pointer at the beginning and one at the end. What does the current sum tell you?
If the sum is too small, only moving the left pointer right can increase it; if too big, move the right pointer left.

The optimal approach

Show the approach: Converging Two Pointers

Time: O(n) - each pointer moves at most n steps
Space: O(1) - just two indices

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.