Two Sum II - Input Array Is Sorted

LeetCode 167 | Difficulty: Medium

Medium

Problem 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. Let these two numbers be numbers[index~1~] and numbers[index~2~] where 1 <= index~1~ < index~2~ <= numbers.length.

Return* the indices of the two numbers, index~1~ and index~2~, added by one as an integer array [index~1~, index~2~] 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, index~1~ = 1, index~2~ = 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 index~1~ = 1, index~2~ = 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 index~1~ = 1, index~2~ = 2. We return [1, 2].

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.

Topics: Array, Two Pointers, Binary Search

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 272 ms)

Metric	Value
Runtime	272 ms
Memory	N/A
Date	2018-04-30

Solution

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.Length-1; i++)
	{
		int remainingTarget = target-numbers[i];
		int index2 = BinSearch(numbers, i+1, numbers.Length-1,remainingTarget);
		if(index2!=-1)
		{
			 return new int[] {i+1, index2+1};
		}
	}
	return null;
}

public int BinSearch(int[] nums, int start, int end, int target)
{
	while(start<=end)
	{
		int mid = (start+end)/2;
		if(nums[mid]==target)
		{
			return mid;
		}
		else if(nums[mid]>target)
		{
			end = mid-1;
		}
		else 
		{
			start = mid+1;
		}		
	}
	return -1;
}
}

📜 1 more C# submission(s)

Submission (2018-04-30) — 288 ms, N/A

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int start = 0, end = numbers.Length-1;
	while(start<=end)
	{
		int sum = numbers[start]+numbers[end];
		if(sum==target)
		{
			return new int[] {start+1,end+1};
		}
		else if(sum<target)
		{
			start++;
		}
		else
		{
			end--;
		}
	}
	return null;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Precisely define what the left and right boundaries represent, and the loop invariant.