Skip to main content
Talentd

Two Sum II - Input Array Is Sorted - Solution & Explanation

MediumArrayTwo PointersBinary Search25 min readAsked at: Amazon, Microsoft, Apple +13
Practice this problem

Problem Statement

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.

 

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 Overview

Problem Overview: You get a 1-indexed sorted array of integers and a target value. Return the indices of the two numbers whose sum equals the target. Exactly one valid pair exists, and you cannot reuse the same element.

Approach 1: Two-Pointer Technique (O(n) time, O(1) space)

The sorted property of the array allows a classic two pointers strategy. Start one pointer at the leftmost index and another at the rightmost index. Compute the sum of both values. If the sum equals the target, return the indices. If the sum is smaller than the target, move the left pointer right to increase the sum. If the sum is larger, move the right pointer left to decrease it.

This works because the array is already sorted, so moving pointers predictably increases or decreases the sum. Every iteration eliminates one candidate pair, which guarantees linear traversal. You scan the array at most once, giving O(n) time complexity and constant O(1) extra space. This is the optimal and most common interview solution for problems involving a sorted array.

Approach 2: Binary Search Optimization (O(n log n) time, O(1) space)

Another option leverages binary search. Iterate through the array with index i. For each element numbers[i], compute the complement target - numbers[i]. Because the array is sorted, run binary search on the remaining subarray [i+1, n-1] to check whether that complement exists.

Each binary search takes O(log n) time, and you perform it for up to n elements. That leads to O(n log n) total time with constant O(1) extra space. This approach is conceptually straightforward if you're already comfortable with binary search patterns, but it performs more comparisons than the two-pointer strategy.

The key insight is recognizing that the sorted order enables efficient searching for the complementary value. However, because you restart a binary search for every element, the runtime grows faster than the linear two-pointer solution.

Recommended for interviews: The two-pointer approach is the expected answer. Interviewers want you to notice that the input array is sorted and exploit that property to reduce the problem from O(n log n) or O(n^2) to O(n). Mentioning the binary search alternative shows good algorithmic awareness, but implementing the linear two-pointer scan demonstrates stronger problem-solving instincts.

Approach 1: Two-Pointer Technique

This approach utilizes a two-pointer technique taking advantage of the sorted nature of the input array. The first pointer starts at the beginning of the array while the second starts at the end. By evaluating the sum at these two pointers, you can determine how to move the pointers:

  • If the sum is greater than the target, move the right pointer left to decrease the sum.
  • If the sum is less than the target, move the left pointer right to increase the sum.
  • If the sum equals the target, you've found the solution.

This method operates in O(n) time and uses O(1) additional space.

The C solution uses a while loop to implement the two-pointer technique. The left and right pointers are adjusted based on the sum compared to the target, ensuring the correct indices are returned in ascending order due to the sorted nature of the input array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Binary Search Optimization

This approach also takes advantage of the sorted array, integrating binary search for a more theoretically robust approach. For every element in the array, a binary search is employed to find the complement such that the sum is equal to the target:

  • Iterate over the array with an index i.
  • Compute the complement as target - numbers[i].
  • Attempt to find this complement within remaining elements using binary search.
  • The solution involves returning these two indices once found.
  • Note: While this method theoretically can be less efficient, it remains simple to implement and understand.

The C solution incorporates a binary search helper function to look for the complement of each element from the remaining array indices. Once found, it returns the indices incremented by one, adhering to the input constraints.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) (due to binary search)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Binary Search

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 times log n), where n is the length of the array numbers. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Two Pointers

We define two pointers i and j, which point to the first element and the last element of the array respectively. Each time we calculate numbers[i] + numbers[j]. If the sum is equal to the target value, return [i + 1, j + 1] directly. If the sum is less than the target value, move i to the right by one position, and if the sum is greater than the target value, move j to the left by one position.

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

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Technique

Time Complexity: O(n)
Space Complexity: O(1)

Binary Search Optimization

Time Complexity: O(n log n) (due to binary search)
Space Complexity: O(1)

Binary Search—
Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer TechniqueO(n)O(1)Best choice when the array is already sorted and only one pair is guaranteed
Binary Search OptimizationO(n log n)O(1)Useful when practicing binary search patterns on sorted arrays

Video Solution

TWO SUM II - Amazon Coding Interview Question - Leetcode 167 - Python • NeetCode • 544,630 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Two Sum II - Input Array Is Sorted easy or hard?
The problem is rated Medium on LeetCode but becomes straightforward once you recognize the sorted array property. Identifying the two-pointer pattern reduces the complexity and makes the implementation short and efficient.
Two Sum II - Input Array Is Sorted Python/Java solution
Python and Java implementations typically follow the same two-pointer logic: initialize left and right pointers, compare their sum to the target, and move the pointers accordingly. The algorithm runs in O(n) time and uses constant O(1) space in both languages.
How to solve Two Sum II - Input Array Is Sorted in O(n)?
Use two pointers on the sorted array. Start with one pointer at the left end and one at the right end. If their sum equals the target, return the indices. If the sum is smaller than the target, move the left pointer right; if larger, move the right pointer left. This guarantees a single linear pass.
What is the best approach for Two Sum II - Input Array Is Sorted?
The two-pointer technique is the best approach. Place one pointer at the start and another at the end of the sorted array, then adjust them based on the current sum compared to the target. This method runs in O(n) time and uses O(1) extra space, making it optimal for this problem.
Is Two Sum II - Input Array Is Sorted asked at Google/Amazon/Meta?
Two Sum variants appear frequently in interviews at companies like Amazon, Google, Meta, and Microsoft. The sorted-array version specifically tests whether you recognize when the two-pointer technique can replace hash maps or brute force solutions.
What data structure is used in Two Sum II - Input Array Is Sorted?
The problem primarily uses arrays and the two-pointer technique. Because the input array is sorted, you do not need additional data structures like hash maps. The algorithm works directly with array indices while adjusting two pointers.
What is the time complexity of Two Sum II - Input Array Is Sorted?
The optimal solution runs in O(n) time using the two-pointer technique because each pointer moves at most once across the array. An alternative binary search approach takes O(n log n) time since it performs a binary search for each element.

Ready to solve this problem?

Practice Two Sum II - Input Array Is Sorted with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Two Sum IV - Input is a BST