Two Sum on a Sorted Array: Left and Right Pointers, O(1) Space

• Two-pointer technique – a left pointer starts at the smallest value and a right pointer at the largest in a sorted array.
• Decision rule – if a[left] + a[right] < target, increment left; if greater, decrement right; if equal, return the pair.
• O(n) time, O(1) space – each pointer moves at most n steps total, and no extra data structure is needed.
• Sorted precondition – the array must be sorted for the pointer movement reasoning to be correct.
• Alternative – on unsorted data, use a HashMap approach at the cost of O(n) extra space.

What is the Two Sum on Sorted Array problem?

Given a sorted array of integers and a target sum, find two elements that add up to the target. Return their indices or the values themselves. The array is guaranteed to be sorted in non-decreasing order.

At the National Bank of India, the reconciliation team checks whether a disputed charge equals the sum of two legitimate debits.

How do the two pointers work?

Keep left at index 0 and right at the last index. The loop runs while left < right.

1. Compute sum = a[left] + a[right].
2. If sum == target, return the pair.
3. If sum < target, the only way to increase the sum is to move left up to a larger value.
4. If sum > target, the only way to decrease the sum is to move right down to a smaller value.

package com.bank.reconciliation;

import java.math.BigDecimal;

public class TwoSumSorted {

    public static int[] twoSum(BigDecimal[] amounts, BigDecimal target) {
        int left = 0, right = amounts.length - 1;

        while (left < right) {
            BigDecimal sum = amounts[left].add(amounts[right]);
            int cmp = sum.compareTo(target);

            if (cmp == 0) {
                return new int[]{left, right};
            } else if (cmp < 0) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};  // no pair found
    }

    public static void main(String[] args) {
        BigDecimal[] deposits = {
            new BigDecimal("100"), new BigDecimal("200"),
            new BigDecimal("350"), new BigDecimal("500"),
            new BigDecimal("700")
        };
        BigDecimal target = new BigDecimal("550");
        int[] result = twoSum(deposits, target);
        System.out.println("Pair at indices: " + result[0] + ", " + result[1]);
        System.out.println("Values: " + deposits[result[0]] + " + " + deposits[result[1]]);
    }
}

Pair at indices: 1, 2
Values: 200 + 350

Why does moving a single pointer never miss a valid pair?

Because the array is sorted, when sum < target, the value at left is too small even when paired with the largest remaining value at right. So left can never be part of the answer and is safely discarded. The symmetric argument holds when sum > target. This correctness reasoning is the key insight interviewers probe.

How is this different from the HashMap Two Sum?

| Aspect | Sorted Two Pointers | HashMap Two Sum |
|---|---|---|
| Precondition | Array must be sorted | Works on unsorted data |
| Time | O(n) | O(n) |
| Space | O(1) | O(n) for the map |
| Multiple pairs | Easily extended to find all pairs | Needs extra bookkeeping |
| Index preservation | Indices are in the sorted array | Original indices preserved |

// HashMap approach for unsorted data
Map<BigDecimal, Integer> seen = new HashMap<>();
for (int i = 0; i < amounts.length; i++) {
    BigDecimal complement = target.subtract(amounts[i]);
    if (seen.containsKey(complement)) {
        return new int[]{seen.get(complement), i};
    }
    seen.put(amounts[i], i);
}

What about integer overflow?

For very large amounts, a[left] + a[right] can overflow int or long. In real financial code at the National Bank of India, Pankaj mandates BigDecimal for all money operations so sums are exact and overflow is not a concern.

What are the edge cases?

• No valid pair – pointers cross without finding a match; return a sentinel like {-1, -1}.
• Multiple valid pairs – the algorithm finds one; to find all, continue after recording the pair.
• Duplicate elements – works correctly because the pointers are distinct indices.
• Array of length less than 2 – no pair possible; return sentinel.
• Target equals double of a single element – two pointers can land on distinct indices with the same value.

What are common mistakes?

// Wrong: using the same index for both elements
if (amounts[left].add(amounts[left]).compareTo(target) == 0) { ... }
// This checks one element against itself, not two distinct elements

// Correct: always ensure left < right
while (left < right) {
    BigDecimal sum = amounts[left].add(amounts[right]);
    // ...
}

What should a senior engineer know?

The two-pointer technique generalizes to Three Sum (fix one element, two-pointer on the rest) and K Sum problems. The O(1) space advantage matters in memory-constrained environments like processing large batch files. When the data arrives unsorted and sorting would destroy original indices, the HashMap approach is the correct choice.

What are common interview follow-up questions?

• What if the array is unsorted? – Use a HashMap.
• Can you extend to Three Sum? – Yes, fix one element and two-pointer on the rest.
• What about returning all pairs? – After finding a pair, skip duplicates and continue.
• What if no pair exists? – Return a sentinel value.