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:

1. Initialization:
   • left = 0 (points to 2)
   • right = 3 (points to 15)
2. First Iteration:
   • Sum = 2 + 15 = 17 which is greater than 9.
   • Move right pointer left to index 2.
3. 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.
4. 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)