Two Sum II: Input Array Is Sorted (Two Pointers)

1. Problem Statement

Mental Model

Imposing order to reduce the search space complexity.

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

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

2. The Mental Model: The "Squeeze" Intuition

Why do we use two pointers here? Because the array is Sorted.

Imagine you are standing in a hallway. The smallest values are behind you (index 0) and the largest are in front of you (index N-1).

If your current "Sum" is too small, you need to increase it. The only way to increase it without checking every pair is to move your "Small" pointer forward.
If your current "Sum" is too large, you need to decrease it. You move your "Large" pointer backward.

This property of Monotonicity (moving a pointer always changes the sum in a predictable direction) is what allows us to solve this in $O(N)$ instead of $O(N^2)$.

3. Visual Execution

flowchart LR
    Start[2, 7, 11, 15] --> P1[L=2, R=15 | Sum=17]
    P1 -- Sum > Target --> P2[L=2, R=11 | Sum=13]
    P2 -- Sum > Target --> P3[L=2, R=7 | Sum=9]
    P3 -- Sum == Target --> Found[Return 1, 2]

4. Java Implementation

public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int 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++; // Need a larger sum
        } else {
            right--; // Need a smaller sum
        }
    }
    return new int[]{-1, -1};
}

5. Verbal Interview Script (The Staff Way)

Interviewer: "How would you solve Two Sum if the array is already sorted?"

You: "Since the array is sorted, I can leverage the monotonic property of the input. Instead of a HashMap which takes $O(N)$ space, I'll use a Two-Pointer 'Squeeze' approach. I'll place one pointer at the start and one at the end. By calculating the sum and comparing it to the target, I can greedily decide which pointer to move. If the sum is less than the target, I increment the left pointer to bring in a larger value. If it's greater, I decrement the right pointer. This gives us a time complexity of $O(N)$ and a space complexity of $O(1)$, which is optimal."

6. Common Pitfalls & Edge Cases

Integer Overflow: In some languages, numbers[left] + numbers[right] might overflow. In Java, if the target and numbers are large, consider using long for the sum check.
1-Indexed vs 0-Indexed: Always clarify if the interviewer wants the array indices (0-based) or the human-readable positions (1-based). This problem specifically asks for 1-based.
No Solution: Even if the problem says a solution exists, a senior engineer always adds a default return [-1, -1] to make the code robust.

7. Comparative Analysis

Approach	Time	Space	Note
Brute Force	$O(N^2)$	$O(1)$	Check every pair.
HashMap	$O(N)$	$O(N)$	Good if array is NOT sorted.
Two Pointers	$O(N)$	$O(1)$	Best for sorted arrays.

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'Two Sum II: Input Array Is Sorted (Two Pointers)', I focused on reducing the time complexity by leveraging a HashMap-based lookup. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by using in-place modifications. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

If your current "Sum" is too small, you need to increase it. The only way to increase it without checking every pair is to move your "Small" pointer forward.
If your current "Sum" is too large, you need to decrease it. You move your "Large" pointer backward.
Problem: 3Sum - Unique Triplets