Two Sum II - Input Array Is Sorted solution and explanation
TCS
Google
Infosys
8 more videos on this problem
TWO SUM II - Amazon Coding Interview Question - Leetcode 167 - PythonNeetCode · 8:18 · 544K views
Two Sum II - Leetcode 167 - 2 Pointers (Python)Greg Hogg · 5:44 · 19K views
Efficiently Solving Leetcode Problem 167: Two Sum II - Input array is sortedEngineering Digest · 6:09 · 10K views
Two Sum II | LeetCode 167 (Medium)Destination FAANG · 12:43 · 3K views
[LeetCode]167. Two Sum II - Input array is sorted 中文 & K Sum模板山景城一姐 · 4:16 · 1K views
LeetCode 167. Two Sum II - Input Array Is Sorted | Medium | Algorithm Explained | C++Cherry Coding [IIT-G] · 7:56 · 767 views
Two Sum II - Input Array Is Sorted | Leetcode 167 | Python | CodingTechError · 6:49 · 710 views
Two Sum II Problem | Input Array is Sorted | Two Pointers | Leetcode 167Binod Suman Academy · 10:57 · 616 views
167. Two Sum II - Input Array Is Sorted, Leetcode Javascript SolutionJSDev · 8:12 · 464 views
The 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.
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] <= 1000numbersis 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.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
sum_ = numbers[left] + numbers[right]
if sum_ == target:
return [left + 1, right + 1]
elif sum_ < target:
left += 1
else:
right -= 1
return [] # Due to constraints, this should not occur.public class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[] { left + 1, right + 1 };
} else if (sum < target) {
left++;
} else {
right--;
}
}
throw new IllegalArgumentException("No solution exists"); // Safe due to problem constraints.
}
}#include <vector>
using namespace std;
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {}; // Should never reach due to problem constraints.
}var twoSum = function(numbers, target) {
let left = 0, right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return []; // Unneeded by constraints
};#include <stdlib.h>
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
*returnSize = 2;
int* result = (int*)malloc(sizeof(int) * 2);
int left = 0, right = numbersSize - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
result[0] = left + 1;
result[1] = right + 1;
return result;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return NULL; // This point should never be reached due to problem constraints.
}public class Solution {
public int[] TwoSum(int[] numbers, int target) {
int left = 0, right = numbers.Length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[] { left + 1, right + 1 };
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0]; // Guarantee issue due to constraints
}
}In Python, the solution employs a straightforward two-pointer technique with a while loop. The pointers move inward based on the current sum relative to the target. The solution is returned as a list of indices.
Time Complexity: O(n)
Space Complexity: O(1)
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.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
def binary_search(left: int, right: int, target: int) -> int:
while left <= right:
mid = left + (right - left) // 2
if numbers[mid] == target:
return mid
elif numbers[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
for i in range(len(numbers)):
complement = target - numbers[i]
idx = binary_search(i + 1, len(numbers) - 1, complement)
if idx != -1:
return [i + 1, idx + 1]
return [] # By constraints, never reachedpublic class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
int complement = target - numbers[i];
int index = binarySearch(numbers, i + 1, numbers.length - 1, complement);
if (index != -1) {
return new int[] {i + 1, index + 1};
}
}
throw new IllegalArgumentException("No solution exists");
}
private int binarySearch(int[] numbers, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] == target) return mid;
else if (numbers[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}#include <vector>
#include <algorithm>
using namespace std;
int binarySearch(vector<int>& numbers, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] == target) return mid;
else if (numbers[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
vector<int> twoSum(vector<int>& numbers, int target) {
for (int i = 0; i < numbers.size(); ++i) {
int complement = target - numbers[i];
int idx = binarySearch(numbers, i + 1, numbers.size() - 1, complement);
if (idx != -1) return {i + 1, idx + 1};
}
return {}; // Ensured solution should be found per constraints.
}var twoSum = function(numbers, target) {
const binarySearch = (left, right, target) => {
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (numbers[mid] === target) return mid;
else if (numbers[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
};
for (let i = 0; i < numbers.length; i++) {
const complement = target - numbers[i];
const index = binarySearch(i + 1, numbers.length - 1, complement);
if (index !== -1) {
return [i + 1, index + 1];
}
}
return []; // Guaranteed by constraints not to reach this line
};#include <stdlib.h>
int binarySearch(int* numbers, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] == target) {
return mid;
} else if (numbers[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
*returnSize = 2;
for (int i = 0; i < numbersSize - 1; ++i) {
int complement = target - numbers[i];
int idx = binarySearch(numbers, i + 1, numbersSize - 1, complement);
if (idx != -1) {
int* result = (int*)malloc(2 * sizeof(int));
result[0] = i + 1;
result[1] = idx + 1;
return result;
}
}
return NULL; // Should never reach here.
}public class Solution {
public int[] TwoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.Length; i++) {
int complement = target - numbers[i];
int index = BinarySearch(numbers, i + 1, numbers.Length - 1, complement);
if (index != -1) {
return new int[] {i + 1, index + 1};
}
}
return Array.Empty<int>();
}
private int BinarySearch(int[] numbers, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] == target) return mid;
else if (numbers[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}In Python, this solution applies a binary search to find the complement for every given element index. As it loops through each element, binary search allows efficient checks within the remaining sub-array for matches.
Time Complexity: O(n log n)
Space Complexity: O(1)
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).
function twoSum(numbers: number[], target: number): number[] {
const n = numbers.length;
for (let i = 0; ; ++i) {
const x = target - numbers[i];
let l = i + 1;
let r = n - 1;
while (l < r) {
const mid = (l + r) >> 1;
if (numbers[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
if (numbers[l] === x) {
return [i + 1, l + 1];
}
}
}func twoSum(numbers []int, target int) []int {
for i, n := 0, len(numbers); ; i++ {
x := target - numbers[i]
j := sort.SearchInts(numbers[i+1:], x) + i + 1
if j < n && numbers[j] == x {
return []int{i + 1, j + 1}
}
}
}use std::cmp::Ordering;
impl Solution {
pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
let n = numbers.len();
let mut l = 0;
let mut r = n - 1;
loop {
match (numbers[l] + numbers[r]).cmp(&target) {
Ordering::Less => {
l += 1;
}
Ordering::Greater => {
r -= 1;
}
Ordering::Equal => {
break;
}
}
}
vec![(l as i32) + 1, (r as i32) + 1]
}
}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).
function twoSum(numbers: number[], target: number): number[] {
for (let i = 0, j = numbers.length - 1; ; ) {
const x = numbers[i] + numbers[j];
if (x === target) {
return [i + 1, j + 1];
}
if (x < target) {
++i;
} else {
--j;
}
}
}func twoSum(numbers []int, target int) []int {
for i, j := 0, len(numbers)-1; ; {
x := numbers[i] + numbers[j]
if x == target {
return []int{i + 1, j + 1}
}
if x < target {
i++
} else {
j--
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n) |
| Binary Search Optimization | Time Complexity: O(n log n) |
| Binary Search | – |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best choice when the array is already sorted and only one pair is guaranteed |
| Binary Search Optimization | O(n log n) | O(1) | Useful when practicing binary search patterns on sorted arrays |
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.