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

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.

// Brute force, aka "please reject me":
for (int i = 0; i < numbers.length; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[i] + numbers[j] == target) {
            return new int[]{i + 1, j + 1};
        }
    }
}
// Prefer caffeinated pointer magic below.

🧠 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 < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[] { left + 1, right + 1 };
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    throw new IllegalArgumentException("Somehow, there's no solution.");
}

⚠️ 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.

🧠 Interviewer Brain-Tattoo

“If you ever brute-force a sorted array, somewhere a mutex locks itself out of shame.”