TWO SUM II

 

Two Sum II – Input Array Is Sorted (Two Pointer Approach)

Introduction

The Two Sum II problem is an optimized version of the classic Two Sum problem. Here, the input array is already sorted in non-decreasing order. This allows us to use a more efficient approach instead of checking all possible pairs.

The goal is to find two numbers such that their sum equals a given target and return their indices (1-based indexing).

Problem Statement

Given a sorted array numbers and a target value:

• Find two numbers such that numbers[index1] + numbers[index2] = target

• Return indices as [index1, index2] (1-based)

• Only one solution exists

• Do not use the same element twice

• Use constant extra space

Solution Code

class Solution {
    public int[] twoSum(int[] numbers, int target) {

        int start = 0;
        int 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 new int[]{-1, -1};
    }
}

Approach Used: Two Pointer Technique

Idea

Since the array is already sorted, we can use two pointers:

• One pointer (start) at the beginning

• Another pointer (end) at the end

Instead of checking all pairs, we intelligently move pointers based on the sum.

How It Works

1. Initialize:

   • start = 0

   • end = n - 1

2. Calculate sum:

   • sum = numbers[start] + numbers[end]

3. Compare with target:

   • If sum == target = return indices

   • If sum < target = move start forward (increase sum)

   • If sum > target = move end backward (decrease sum)

4. Repeat until solution is found

Why This Approach Was Chosen

• The array is already sorted, which allows efficient searching

• Instead of checking all pairs (O(n²)), we reduce complexity

• Uses constant extra space, satisfying the problem constraint

• Cleaner and faster compared to brute-force

Comparison with Brute Force

Approach	Time Complexity	Space	Notes
Brute Force	O(n²)	O(1)	Checks all pairs
Two Pointer	O(n)	O(1)	Efficient for sorted arrays

EXAMPLE:

Input:

numbers = [2, 7, 11, 15]
target = 9

Steps:

• start = 0 (2), end = 3 (15) => sum = 17 =>too large => move end

• start = 0 (2), end = 1 (7) => sum = 9 => match found

Output:

[1, 2]

Important Observation

We return start + 1 and end + 1 because:

• The problem uses 1-based indexing

• Arrays in Java use 0-based indexing

Time and Space Complexity

• Time Complexity: O(n)

• Space Complexity: O(1)

Conclusion

The Two Pointer approach is an efficient solution for the Two Sum II problem when the array is sorted. By leveraging the sorted property, we reduce time complexity significantly while keeping space usage minimal. This makes it a preferred approach over brute-force methods.