DSA Series Day 7: Two Sum II (Sorted Array) in Java, Python and Rust

Two Sum II is the same question as Day 1, with one small twist: the array is already sorted. Welcome to Day 7 of the Tekraze DSA series. Remember how we solved the original with a hash map? That one sorted detail lets us throw the hash map away and solve Two Sum II with two pointers in constant extra space. It is one of the best problems for seeing why sorted input changes everything.

Also Read: Two Sum (Day 1): Hash Map Solution in Java, Python and Rust

What is the Two Sum II problem?

You get an array numbers sorted in non-decreasing order and a target. Find two different positions whose values add up to the target and return them as 1-based indexes, with the smaller index first.

In Two Sum II there is exactly one answer, you cannot use the same element twice, and you must use only constant extra space. This is LeetCode 167, if you want to practice it after reading.

Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]   (2 + 7 = 9)
Input:  numbers = [2, 3, 4], target = 6
Output: [1, 3]   (2 + 4 = 6)
Input:  numbers = [-1, 0], target = -1
Output: [1, 2]

How should you think about Two Sum II in plain words?

Put one finger on the smallest number and another on the largest. Add them. If the sum is too small, the only way to make it bigger is to move the left finger to a larger number. If the sum is too big, move the right finger to a smaller number.

Because the array is sorted, every move tells you something for sure, so you never need to look back. Keep squeezing until the sum hits the target.

What does the brute force solution look like?

Check every pair with two nested loops and return the first pair that adds up to the target.

def two_sum_brute(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]

Time is O(n²) because we try every pair. Space is O(1). The Day 1 hash map trick gets the time down to O(n), but it costs O(n) memory and ignores the sorted input, which is exactly what an interviewer wants you to use on this problem.

If you want a refresher on why O(n) beats O(n²) so badly on big inputs, our Big O helper post on time and space complexity walks through it with charts.

How do we get the optimal Two Sum II solution?

Start left at index 0 and right at the last index. While left is less than right, compute the sum. If it equals the target, return both indexes plus one. If it is smaller, move left one step right. If it is larger, move right one step left.

Why is it safe to drop a number in Two Sum II?

If the sum is too small, then the left value plus the biggest remaining value still falls short, so that left value can never be part of the answer. The same logic works in reverse for the right side. Each step removes one candidate for good.

Time is O(n), because each pointer only moves inward and together they make at most n steps. Space is O(1), just two indexes.

Two Sum II in Java

import java.util.Arrays;

public class Solution {
    // numbers is sorted in non-decreasing order, answer uses 1-based indexes
    public static int[] twoSum(int[] numbers, int target) {
        int left = 0, 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[]{-1, -1};
    }

    public static void main(String[] args) {
        int[][] nums = {{2, 7, 11, 15}, {2, 3, 4}, {-1, 0}, {1, 2, 3, 4, 4, 9, 56, 90}, {5, 25, 75}};
        int[] targets = {9, 6, -1, 8, 100};
        int[][] expected = {{1, 2}, {1, 3}, {1, 2}, {4, 5}, {2, 3}};
        for (int i = 0; i < nums.length; i++) {
            int[] got = twoSum(nums[i], targets[i]);
            String ok = Arrays.equals(got, expected[i]) ? "PASS" : "FAIL";
            System.out.println(ok + " " + Arrays.toString(got));
        }
    }
}

The test loop uses Arrays.equals from the Java standard library to compare the arrays.

Two Sum II in Python

def two_sum(numbers, target):
    # numbers is sorted, answer uses 1-based indexes
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]


if __name__ == "__main__":
    tests = [
        ([2, 7, 11, 15], 9, [1, 2]),
        ([2, 3, 4], 6, [1, 3]),
        ([-1, 0], -1, [1, 2]),
        ([1, 2, 3, 4, 4, 9, 56, 90], 8, [4, 5]),
        ([5, 25, 75], 100, [2, 3]),
    ]
    for nums, target, expected in tests:
        got = two_sum(nums, target)
        print("PASS" if got == expected else "FAIL", got)

Two Sum II in Rust

// numbers is sorted, answer uses 1-based indexes
fn two_sum(numbers: &[i32], target: i32) -> Option<(usize, usize)> {
    if numbers.len() < 2 {
        return None;
    }
    let (mut left, mut right) = (0usize, numbers.len() - 1);
    while left < right {
        let sum = numbers[left] + numbers[right];
        if sum == target {
            return Some((left + 1, right + 1));
        } else if sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }
    None
}

fn main() {
    let tests: [(&[i32], i32, (usize, usize)); 5] = [
        (&[2, 7, 11, 15], 9, (1, 2)),
        (&[2, 3, 4], 6, (1, 3)),
        (&[-1, 0], -1, (1, 2)),
        (&[1, 2, 3, 4, 4, 9, 56, 90], 8, (4, 5)),
        (&[5, 25, 75], 100, (2, 3)),
    ];
    for (nums, target, expected) in tests.iter() {
        let got = two_sum(nums, *target);
        let ok = if got == Some(*expected) { "PASS" } else { "FAIL" };
        println!("{} {:?}", ok, got);
    }
}

The Rust version returns an Option, so a missing pair is handled cleanly instead of with magic numbers like -1.

All three programs use the same five tests: the classic [2, 7, 11, 15] case, a gap in the middle with [2, 3, 4], negative numbers, duplicate values that form the answer, and a pair sitting at the end of the array. Every test passes.

What are the 6 tips and tricks for an easy Two Sum II solution?

1. Spot the pattern. A sorted array plus a pair or target sum almost always means two pointers starting at both ends.
2. Say the reason for each move. Interviewers love hearing why moving a pointer cannot skip the answer. One sentence about sorted order is enough.
3. Watch the 1-based indexes. Add one to both indexes before returning. It is the most common silly bug in this problem.
4. Use left < right, not left <= right. The two indexes must point to different elements.
5. Think about overflow. In Java or Rust with very large values, the sum of two ints can overflow. Using a long, or comparing numbers[left] with target - numbers[right], avoids it.
6. Know the next step. 3Sum fixes one number and runs this exact loop on the rest, so mastering Two Sum II makes 3Sum much easier.

What are the common mistakes people make?

• Returning 0-based indexes when the problem asks for 1-based ones.
• Reaching for a hash map and missing the constant space requirement.
• Moving both pointers at once after a comparison, which can skip the answer.
• Using binary search for each element, which works in O(n log n) but is slower than needed.
• Forgetting that duplicates like [4, 4] can be a valid pair.

Where is the Two Sum II pattern used in the real world?

Any time data is already sorted, two pointers lets you find matches without building extra structures. Finance tools use it to pair buy and sell orders around a price. Databases use a close cousin in sort-merge joins. Analytics jobs use it to find two events whose timestamps fall within a window.

When memory is tight, like on embedded devices or huge log files, skipping the hash map really matters.

Which earlier posts in the series should you read before Two Sum II?

This post is a sequel to Day 1, so read Two Sum first to compare the hash map and two pointer versions side by side. Day 2, Best Time to Buy and Sell Stock, shows another single pass idea, and Day 3 and Day 4 cover the hashing basics with Contains Duplicate and Valid Anagram.

Day 6, Valid Palindrome, is the best warm-up because it introduces the two pointer pattern on a string. Next, 3Sum builds directly on today’s loop.

Frequently asked questions about Two Sum II

What is the difference between Two Sum and Two Sum II?

Two Sum works on any array and is solved with a hash map in O(n) time and O(n) space. Two Sum II gives you a sorted array, so two pointers solve it in O(n) time and O(1) space.

Why do two pointers work on a sorted array?

Sorted order means moving the left pointer always increases the sum, and moving the right pointer always decreases it. Each step safely rules out one number.

What is the time complexity of Two Sum II?

The two pointer solution runs in O(n) time and O(1) extra space. Brute force takes O(n²), and binary search per element takes O(n log n).

Can I use a hash map for Two Sum II?

It gives the right answer, but it uses O(n) extra space and the problem asks for constant space, so interviewers expect two pointers.

Why does the answer use 1-based indexes?

That is just how the problem is defined. Add one to each 0-based index before returning it.

Conclusion

Two Sum II shows what a single detail can do: sorted input turns a hash map problem into a two pointer squeeze with no extra memory. Practice the loop until you can explain every pointer move in one sentence. Tomorrow we use it as a building block for 3Sum.