Mohith

Posted on Mar 19

Two Sum II - Input Array Is Sorted-java(LEETCODE:167)

#java #algorithms #tutorial #interview

Solving Two Sum II in Java Using Two Pointers (Sorted Array Approach)

Introduction

After understanding the standard Two Sum problem using hashing, I came across a variation:

Two Sum II – Input Array Is Sorted

At first glance, it looks similar, but the key difference is:

The array is already sorted.

This small detail allows us to use a more optimal and space-efficient approach.

Problem Statement

Given a 1-indexed sorted array of integers, find two numbers such that they add up to a specific target.

Constraints:

Exactly one solution exists
You may not use the same element twice
The solution must use constant extra space

Key Observation

Since the array is sorted:

Smaller numbers are on the left
Larger numbers are on the right

This allows us to avoid extra space and use a two-pointer technique.

My Thought Process

Instead of storing values like in HashMap, I asked:

“Can I use the sorted property to move intelligently?”

So I placed:

One pointer at the start
One pointer at the end

Two Pointer Logic

If sum is too small → move left pointer forward
If sum is too large → move right pointer backward
If sum equals target → return indices

Example Walkthrough

Input:

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

Step 1:

left = 0 (2), right = 3 (15)
sum = 17 → too large → move right

Step 2:

left = 0 (2), right = 1 (7)
sum = 9 → match found

Output:

[1, 2]

(Note: Indices are 1-based)

Java Implementation

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

        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {

            int sum = numbers[left] + numbers[right];

            if (sum == target) {
                return new int[] { left + 1, right + 1 };
            } 
            else if (sum < target) {
                left++;
            } 
            else {
                right--;
            }
        }

        return new int[] {};
    }
}

Line-by-Line Explanation

Initialize Pointers

int left = 0;
int right = numbers.length - 1;

left starts at the beginning
right starts at the end

Loop Until Pointers Meet

while (left < right)

Ensures we check valid pairs.

Calculate Sum

int sum = numbers[left] + numbers[right];

Adds current elements.

If Match Found

if (sum == target)

Return indices (1-based).

If Sum is Smaller

else if (sum < target)

Move left forward to increase sum.

If Sum is Larger

else

Move right backward to decrease sum.

Complexity Analysis

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

This is optimal because:

Only one pass is required
No extra data structures are used

Key Insight

The main idea is to leverage the sorted nature of the array.

Instead of storing elements (like HashMap), we adjust pointers intelligently to reach the target.

What I Learned

Not every problem needs hashing
Always check if input is sorted
Two pointers can replace extra space

Conclusion

Two Sum II demonstrates how understanding input constraints can lead to a more efficient solution. By using the two-pointer technique, we achieve optimal performance with constant space.

DEV Community