leetcode-textbook

0167 - Two Sum II - Input Array Is Sorted

Difficulty: Medium Pattern: Two Pointers LeetCode: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Concepts used

Problem

Given a 1-indexed integer array numbers already sorted in non-decreasing order, find two numbers that add up to a specific target. Return the indices of the two numbers, [index1, index2], as an integer array of length 2 where index1 < index2 and both are 1-based. The problem guarantees exactly one solution and you may not use the same element twice.

Signature:

int[] twoSum(int[] numbers, int target)

Examples (verbatim from LeetCode):

Input:  numbers = [2,7,11,15], target = 9
Output: [1,2]

Input:  numbers = [2,3,4], target = 6
Output: [1,3]

Input:  numbers = [-1,0], target = -1
Output: [1,2]

Intuition

Imagine a row of price tags sorted from cheapest to most expensive, and you have exactly $9 to spend on two items. Put one finger on the cheapest tag and one on the most expensive. If the two prices add to more than $9, the expensive item is clearly too pricey – slide the right finger to a cheaper one. If they add to less than $9, the cheap item is too cheap – slide the left finger to a pricier one. Close in until the pair hits $9. This finger dance is two pointers: one index (left) at the start, one (right) at the end, moving inward.

Let’s watch it on the smallest example, numbers = [2,7,11,15], target = 9:

Why is moving the correct finger guaranteed safe? Because the array is sorted: any index to the right holds a value at least as large. So moving left forward can only increase the sum, and moving right backward can only decrease it. That one-way promise means exactly one finger can ever bring us closer to target – there is never a tie where we would have to guess. This is why sorting is the key clue: without it, moving a finger would tell us nothing about whether the sum goes up or down.

The older problem Two Sum (LC 1) had an unsorted array, so it needed a hash map (a key-to-value lookup table) to remember values already seen. Here the sort is a free gift – we trade that hash map’s O(n) memory for two plain index variables, dropping to O(1) space.

Checkpoint A – Which finger moves?

Pause and pick before expanding. A wrong first guess teaches more than a fast right one.

Q1 (recall). When the current sum is LESS than the target, which pointer moves?

Show answer **(a)** -- the array is sorted, so advancing `left` can only increase the sum, which is what "sum too small" calls for.

Q2 (comprehend). Why can we be sure that moving one finger never skips over the correct pair?

Show answer **(a)** -- the sorted order gives a one-way promise: each finger moves the sum in a known direction, so exactly one finger can ever bring us closer. That is why the sort is the key clue -- without it, moving a finger tells us nothing.

Pseudocode

function twoSumSorted(numbers, target):
    set left to first index
    set right to last index
    while left < right:
        set current to numbers[left] + numbers[right]
        if current equals target:
            return [left + 1, right + 1]   # 1-indexed
        if current is less than target:
            advance left                   # need a bigger sum
        else:  # current is greater than target
            move right back one            # need a smaller sum
    # problem guarantees a solution, so we never reach here
    return an empty pair

Java Solution

class Solution {
    public 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};
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

The loop invariant is left < right: the two indices must point at distinct elements (the problem forbids reusing one). The +1 on the return converts from Java’s 0-based indices to the 1-based indices LeetCode wants — this is the most common silly mistake on the problem, so it is the one line worth remembering. The final return new int[]{-1,-1} is unreachable because the problem promises exactly one solution; we include it only so the compiler is satisfied that every path returns.

Complexity

Time:  O(n)  -- each iteration moves exactly one pointer, so at most n iterations.
Space: O(1)  -- two index variables plus the 2-element result; no extra structure.

Dry-Run

Step-by-step on numbers = [2,7,11,15], target = 9:

Step left right numbers[left] numbers[right] sum action
1 0 3 2 15 17 17 > 9 -> right–
2 0 2 2 11 13 13 > 9 -> right–
3 0 1 2 7 9 9 == 9 -> return [0+1, 1+1] = [1,2]

Three iterations; the answer is [1, 2]. Notice left never moved — the sorted property let us shrink only from the right until the pair was tight enough.

Checkpoint B – Trace and stress it

Q1 (apply). Trace numbers = [1,2,3,4,6], target = 5. What is returned?

Show answer **(a)** -- step 1: `left=0` (1), `right=4` (6), sum 7 > 5 -> `right--`. step 2: `left=0` (1), `right=3` (4), sum 5 == 5 -> return `[0+1, 3+1] = [1,4]`. Option (b) is the 0-based trap; (c) sums to 7.

Q2 (analyze). What goes wrong if the loop condition is while (left <= right) instead of while (left < right)?

Show answer **(a)** -- the problem says you may not use the same element twice. `<` keeps the pointers on distinct elements; `<=` would let them collide and "find" a single element pairing with itself.

Q3 (transfer). How would you solve this if the input array were NOT sorted?

Show answer You lose the guarantee that moving a finger changes the sum in a known direction, so the two-pointer move rule no longer works. Fall back to the hash-map approach from Pattern 1's Two Sum: store each value's index in a map as you scan, and for each element check whether `target - value` is already stored. Alternatively sort a copy first -- but then you must track the original indices to return them.

Common mistakes