Skip to main content

167. Two Sum II - Input Array Is Sorted

medium

The classic Two Sum, but the input is sorted and you must return 1-indexed positions using O(1) extra space. Two pointers is the textbook answer, but the hash-map version is still useful when the interviewer asks 'what if the array weren't sorted?' — knowing both unlocks follow-up questions on 3Sum and 4Sum.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] 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.

Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • -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.

Examples

Example 1

Input
numbers = [2,7,11,15], target = 9
Output
[1,2]

Explanation: 2 + 7 = 9, returned as 1-indexed positions.

Example 2

Input
numbers = [2,3,4], target = 6
Output
[1,3]

Example 3

Input
numbers = [-1,0], target = -1
Output
[1,2]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash-map version: same as Two Sum — walk the array, store value -> 1-indexed position, look up the complement. Works regardless of order but spends O(n) space.

Hint 2

Sorted-array version: place left = 0 and right = n - 1. If numbers[left] + numbers[right] equals target, return [left+1, right+1]. If the sum is too small, increment left. If too large, decrement right.

Hint 3

Two pointers is strictly better here — O(1) space, no allocator pressure — but the hash-map answer is what the interviewer will ask you to derive first if they're warming up to a 3Sum follow-up.

Solution approach

Reveal approach

Two viable paths. Hash map (complement lookup): single pass storing value -> 1-indexed position, look up target - x at each step, return when hit. O(n) time, O(n) space. Two pointers (the constraint-satisfying answer): left = 0, right = len(numbers) - 1, repeatedly compare numbers[left] + numbers[right] against target — move left forward when too small, right backward when too large, return when equal. The sorted invariant guarantees correctness: skipping numbers[left] is safe because every remaining candidate paired with it would be even smaller. O(n) time, O(1) space. Lead with two pointers given the constant-space constraint.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • hash-map
  • two-pointers
  • complement-lookup

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Two Sum II - Input Array Is Sorted and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →