The O(n) Club: Two Sum II – Sorted Input, Sorted Output, Less Screaming

⚡ TL;DR

You have a sorted array, a target, and either a Java IDE or a willingness to brute force your career into oblivion. Don’t check every pair: let two pointers meet in O(n) time.

🧠 How Devs Usually Mess This Up

With sorted input, many still reach for the soul-crushing double loop. Others miss the classic 1-based index gotcha—because programming is 99% zero-based, but this question likes chaos. Bonus: since there’s exactly one solution, you don’t have to lose sleep over dupes or accidental twin-pairings. (But people still do…)

🔍 What’s Actually Going On

Picture two tired robots: one at the start of the array, the other at the end. They scan towards each other. If their sum is too small, left-bot moves right. If too large, right-bot shuffles left. When they fist-bump at the perfect sum, you win. Thank sorted input for this party trick—unsorted arrays can only dream of such elegance.

🛠️ PseudoCode

Set left = 0 (start), right = N-1 (end).
While left < right:
- Calculate sum = numbers[left] + numbers[right].
- If sum == target: return left+1, right+1 (because 1-based indices = job security for interviewers).
- If sum < target: left++ (make it bigger).
- If sum > target: right-- (make it smaller).
Assume a solution exists, because the problem says so. Otherwise, exception time.

💻 The Code

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left &lt; right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[] { left + 1, right + 1 };
        } else if (sum &lt; target) {
            left++;
        } else {
            right--;
        }
    }
    throw new IllegalArgumentException(&quot;Somehow, there&#039;s no solution.&quot;);
}

⚠️ Pitfalls, Traps & Runtime Smacks

Don’t forget: output needs to be 1-based indices. (Leave 0-based at home.)
No need for hashmaps, binary search, or existential dread. There’s exactly one answer.
Don’t pair a number with itself—pointers naturally “slide” around this.
Complexity: O(n) time, O(1) extra space. Your server bill thanks you.