167. Two Sum II - Input Array is Sorted

📝 Problem Details

• Title: 167. Two Sum II - Input Array is Sorted
• Link: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
• Difficulty: Medium
• Tags/Categories: Two-Pointers

input 1-indexed, sorted array numbers input integer target return the indices of two numbers that add up to target the solution must be O(1) extra space and must run in O(n) time

💭What Were My Initial Thoughts?

- the original solution for Two Sum involving a hashmap is not viable given the complexity constraints
- a brute force is also not viable 

- the input array is sorted which allows for efficient two pointer usage
  - Start with **two pointers**: one at the beginning (`i = 0`) and one at the end (`j = n-1`).
  - If `numbers[i] + numbers[j]` equals `target`, return `[i+1, j+1]` (1-based indexing).
  - If the sum is **too small**, move the left pointer `i++`.
  - If the sum is **too large**, move the right pointer `j--`.

💡 Explanation of Solution

Two Pointer Approach:

- init two pointers
	- i = 0
	- j = n-1

- while i < j
	- compute sum = numbers[i] + numbers[j]
	- if sum == target return {i+1, j+1} due to the array being 1-indexed
	- if sum < target, move i++ to increase the sum
	- if sum > target, move j-- to decrease the sum

- return empty array if no valid pairs are located

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i=0;
        int j=numbers.size()-1;
 
        while(i < j) {
            int sum = numbers[i] + numbers[j];
            if(sum == target) return {i+1,j+1};
            if(sum < target) i++;
            if(sum > target) j--;
        }
 
        return {};
    }
};