Log inSign up
mediumLeetCodeNot Started

Two Sum II - Input Array Is Sorted

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array Indexing & Iteration
  • Two-Pointer Technique Basics
  • Binary Search on Sorted Arrays

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how sorted order enables bidirectional two-pointer convergence.
  • Formally justify candidate elimination: why discarding left or right never misses the optimal pair.
  • Master 1-indexed coordinate conversions in competitive programming.
  • Compare space-time trade-offs between Hash Map (O(N) time, O(N) space) and Two Pointers (O(N) time, O(1) space).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array is already sorted in non-decreasing order.
  • Target sum of two elements is required.
  • Constraint strictly specifies O(1) auxiliary space (ruling out Hash Maps).

Algorithmic Decision Tree:

  • Initialize left = 0, right = numbers.length - 1.
  • Compute sum = numbers[left] + numbers[right].
  • If sum === target, return [left + 1, right + 1].
  • If sum < target, left++; else right--.

Connected Patterns:

3Sum (Sorting + Fixed Outer Loop + Two-Pointer Inner Scan)3Sum Closest (Two Pointers tracking minimum absolute difference)Container With Most Water (Two Pointers inward shrinkage on bounding height)

1. Nested Loops Pair Check (Brute Force)

Intuition

Iterate across all pairs i from 0 to n-1 and j from i+1 to n-1. If numbers[i] + numbers[j] == target, return [i + 1, j + 1].

When to apply: Use to verify 1-based index requirements.

Nested Loops (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
First pair evaluated satisfies the target condition
Visual state
Values and pointers at this exact step
pointers
S
2
7
11
15
0
↑ i
1
↑ j
2
3
Variables at this step
i
0
j
1
sum
9
target
9
found
true
Check / comparison
Check pair (0, 1): numbers[0] + numbers[1] = 2 + 7 = 9
Decision / next transition
Sum == target (9). Match found immediately!
Why this step matters

First pair evaluated satisfies the target condition.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int[] twoSum(int[] numbers, int target) {
4 for (int i = 0; i < numbers.length; i++) {
5 for (int j = i + 1; j < numbers.length; j++) {
6 if (numbers[i] + numbers[j] == target) {
7 return new int[]{i + 1, j + 1};
8 }
9 }
10 }
11 return new int[]{-1, -1};
12 }
13 }
14
15 public static void main(String[] args) {
16 Solution sol = new Solution();
17 int[] numbers = {2, 7, 11, 15};
18 int target = 9;
19 int[] ans = sol.twoSum(numbers, target);
20 System.out.println("Indices: [" + ans[0] + ", " + ans[1] + "]");
21 }
22}

Time & Space Complexity

  • Time complexity: O(n^2) — Nested loops examine all n*(n-1)/2 pairs.
  • Space complexity: O(1) — O(1) auxiliary space.

Why Brute Force Doesn't Scale:

For N = 30,000, N2 / 2 = 4.5 * 108 operations, exceeding typical 1-second CPU time limits.

The Two Pointer method checks at most N elements total, finishing in under 2ms with zero dynamic memory allocation.

2. Binary Search for Complement

Intuition

Since the array is sorted in non-decreasing order, for each index i, we search for complement = target - numbers[i] in numbers[i+1..n-1] in O(log n) time.

When to apply: Use to exploit sorted order using binary search.

Binary Search Complement (O(N log N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Complement 7 must lie to the right of index 0 in the sorted array
Visual state
Values and pointers at this exact step
pointers
S
2
7
11
15
0
↑ i
1
2
3
Variables at this step
i
0
currentVal
2
targetComplement
7
searchLow
1
searchHigh
3
Check / comparison
Fix numbers[0] = 2. Complement needed = 9 - 2 = 7
Decision / next transition
Binary search for 7 in subarray range [1..3].
Why this step matters

Complement 7 must lie to the right of index 0 in the sorted array.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int[] twoSum(int[] numbers, int target) {
4 int n = numbers.length;
5 for (int i = 0; i < n; i++) {
6 int comp = target - numbers[i];
7 int low = i + 1, high = n - 1;
8 while (low <= high) {
9 int mid = low + (high - low) / 2;
10 if (numbers[mid] == comp) return new int[]{i + 1, mid + 1};
11 if (numbers[mid] < comp) low = mid + 1;
12 else high = mid - 1;
13 }
14 }
15 return new int[]{-1, -1};
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] numbers = {2, 7, 11, 15};
22 int target = 9;
23 int[] ans = sol.twoSum(numbers, target);
24 System.out.println("Indices: [" + ans[0] + ", " + ans[1] + "]");
25 }
26}

Time & Space Complexity

  • Time complexity: O(n log n) — n elements, each performing O(log n) binary search.
  • Space complexity: O(1) — O(1) auxiliary pointer variables.

3. Two Pointers (Optimal & Standard)

Intuition

1. Initialize left = 0, right = n - 1. 2. Calculate sum = numbers[left] + numbers[right]. 3. If sum == target, return [left + 1, right + 1]. 4. If sum < target, left++ to increase sum. 5. If sum > target, right-- to decrease sum.

When to apply: Use as the canonical optimal technique for sorted array pair sum.

Two Pointers on Inward Ends (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Since the array is sorted, 15 is too large to pair with any number
Visual state
Values and pointers at this exact step
pointers
S
2
7
11
15
0
↑ L
1
2
3
↑ R
Variables at this step
L
0
R
3
sum
17
target
9
Check / comparison
L = 0, R = 3: numbers[0] + numbers[3] = 2 + 15 = 17 > 9
Decision / next transition
Sum 17 > target 9. Decrement R to 2.
Why this step matters

Since the array is sorted, 15 is too large to pair with any number. Moving R left is guaranteed safe.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int[] twoSum(int[] numbers, int target) {
4 int left = 0, right = numbers.length - 1;
5 while (left < right) {
6 int sum = numbers[left] + numbers[right];
7 if (sum == target) {
8 return new int[]{left + 1, right + 1};
9 } else if (sum < target) {
10 left++;
11 } else {
12 right--;
13 }
14 }
15 return new int[]{-1, -1};
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] numbers = {2, 7, 11, 15};
22 int target = 9;
23 int[] ans = sol.twoSum(numbers, target);
24 System.out.println("Indices: [" + ans[0] + ", " + ans[1] + "]");
25 }
26}

Time & Space Complexity

  • Time complexity: O(n) — Each step decrements right or increments left; at most n steps.
  • Space complexity: O(1) — Only two index pointers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Nested Loops)O(N^2)O(1)Check all pairs (i, j) with i < j and see if their sum matches target.Checks N*(N-1)/2 pairs without taking advantage of sorted order.
2.Binary Search ComplementO(N log N)O(1)For each index i, binary search for target - numbers[i] in the subarray numbers[i+1..n-1].Performs independent log N searches instead of converging pointers.
3.Two Pointers (Inward Convergence)OptimalO(N)O(1)Start with pointers at both ends and move inward based on comparison with target.None. Maximum N pointer movements.

Common Pitfalls & Crucial Edge Cases

0-indexed vs 1-indexed Return

Returning [left, right] instead of [left + 1, right + 1].

Using Hash Map

While a Hash Map achieves O(N) time, it uses O(N) space and fails the problem requirement of O(1) extra space.

Allowing Same Index Reuse

Using left <= right instead of left < right, which could mistakenly pair an element with itself if 2 * numbers[i] == target.

Integer Overflow on Sum

In languages like C++, if elements were up to 109, numbers[left] + numbers[right] could overflow a 32-bit signed integer. For the given constraints (-1000 to 1000), standard integer suffices.

Crucial Edge Cases to Validate:

  • Minimum Length Array (N = 2) — e.g., numbers = [-1, 0], target = -1 -> immediately checks left = 0, right = 1 and returns [1, 2].
  • Negative Numbers — e.g., numbers = [-5, -3, -1, 0, 2, 4], target = -4 -> properly handles signed addition.
  • Duplicate Elements — e.g., numbers = [0, 0, 3, 4], target = 0 -> handles numbers[0] + numbers[1] == 0 returning [1, 2].
  • Solution at Extreme Ends — e.g., numbers = [1, 2, 3, 4, 10], target = 11 -> 1 + 10 = 11, resolved in step 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Confirm 1-indexing: Always acknowledge the 1-indexed return constraint upfront to avoid off-by-one errors.
  2. Mention the space complexity trade-off: Highlight why Two Pointers (O(1) space) is strictly superior to Hash Map (O(N) space) when sorted input is provided.
  3. Explain the elimination logic: State clearly why left++ or right-- safely discards suboptimal search space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does incrementing left when sum < target guarantee we do not miss any valid solution?

2.What is the primary advantage of the Two Pointer approach over the Hash Map approach for this specific problem?

3.If numbers = [2, 3, 4] and target = 6, what is the 1-indexed output?

Back to DSA Sheet