167. Two Sum II - Input Array Is Sorted - Detailed Explanation

Problem Statement

Description:
Given a 1-indexed array of integers numbers that is sorted in non-decreasing order and a target integer target, find two numbers such that they add up to target. Return the indices of the two numbers as an array [index1, index2] where 1 <= index1 < index2 <= numbers.length. You are guaranteed that there is exactly one solution, and you may not use the same element twice.

Examples:

Example 1:
- Input: numbers = [2,7,11,15], target = 9
- Output: [1,2]
- Explanation:
  The numbers at indices 1 and 2 (1-indexed) are 2 and 7 respectively. Their sum is 9.
Example 2:
- Input: numbers = [2,3,4], target = 6
- Output: [1,3]
- Explanation:
  The numbers at indices 1 and 3 are 2 and 4, which add up to 6.
Example 3:
- Input: numbers = [-1,0], target = -1
- Output: [1,2]
- Explanation:
  The numbers at indices 1 and 2 are -1 and 0, and their sum is -1.

Constraints:

2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
There is exactly one solution.

Hints

Hint 1: Since the array is sorted, think about using two pointers – one starting at the beginning and the other at the end of the array.
Hint 2: Use the fact that if the sum of the two pointers is too high, you can move the right pointer to the left; if the sum is too low, move the left pointer to the right.

Approaches

Brute Force Approach

Idea:

Check every pair of numbers (using nested loops) to see if they add up to the target.
Return the pair of indices when found.

Drawbacks:

Time Complexity: O(n²) – inefficient for large arrays.
Not ideal since the array is already sorted, which hints at a better approach.

Optimal Approach – Two Pointers

Idea:

Use two pointers:
- Left Pointer: Starts at the beginning of the array.
- Right Pointer: Starts at the end of the array.
Compute the sum of the elements at these pointers.
- If the sum equals the target: Return the 1-indexed positions.
- If the sum is less than the target: Increase the left pointer to increase the sum.
- If the sum is greater than the target: Decrease the right pointer to decrease the sum.

Step-by-Step Walkthrough:

Consider the array [2,7,11,15] with target = 9:

Initialization:
- left = 0 (points to 2)
- right = 3 (points to 15)
First Iteration:
- Sum = 2 + 15 = 17 which is greater than 9.
- Move right pointer left to index 2.
Second Iteration:
- left = 0 (still 2), right = 2 (points to 11).
- Sum = 2 + 11 = 13 still greater than 9.
- Move right pointer left to index 1.
Third Iteration:
- left = 0 (points to 2), right = 1 (points to 7).
- Sum = 2 + 7 = 9 equals the target.
- Return indices [0 + 1, 1 + 1] = [1,2].

Complexity Analysis:

Time Complexity: O(n) – each element is visited at most once.
Space Complexity: O(1) – constant extra space is used.

Code Implementations

Python Code (Two Pointers Approach)

Python3

. . . .

Java Code (Two Pointers Approach)

Java

. . . .

Step-by-Step Walkthrough and Visual Example

Let's walk through the example numbers = [2,7,11,15] and target = 9:

Initialize:
- left = 0 (points to 2)
- right = 3 (points to 15)
Iteration 1:
- Calculate current_sum = 2 + 15 = 17
- Since 17 > 9, move the right pointer leftwards:
  - Now, right = 2 (points to 11)
Iteration 2:
- With left = 0 (points to 2) and right = 2 (points to 11):
- Calculate current_sum = 2 + 11 = 13
- Since 13 > 9, move the right pointer leftwards:
  - Now, right = 1 (points to 7)
Iteration 3:
- With left = 0 (points to 2) and right = 1 (points to 7):
- Calculate current_sum = 2 + 7 = 9
- current_sum equals target. Return the answer as [left + 1, right + 1] = [1, 2].

Common Mistakes

Not Returning 1-Indexed Positions:
Since the array is 1-indexed according to the problem, remember to add 1 to each index before returning.
Using Nested Loops Unnecessarily:
The two pointers approach takes advantage of the sorted property of the array and is far more efficient than a brute force nested loops solution.
Incorrect Pointer Updates:
Be sure to adjust the pointers correctly based on whether the current sum is less than or greater than the target.

Edge Cases

Array with Two Elements:
With only two elements, the solution is trivial but ensure your code handles this without error.
Negative Numbers:
Even though the array is sorted, it can contain negative numbers. The two pointers approach still applies.
Guaranteed One Solution:
The problem guarantees exactly one solution, so you don’t need to handle cases where no solution exists.

Variations:

Two Sum (Unsorted Array):
In the unsorted version, a hash map is typically used to achieve O(n) time.
3Sum and 4Sum:
These problems require finding triplets or quadruplets that add up to a target value.
Closest Two Sum:
Find the pair of numbers whose sum is closest to the target value.