30. Two Sum II - Input Array Is Sorted

🔗 LeetCode Problem: 167. Two Sum II - Input Array Is Sorted
📊 Difficulty: Medium
🏷️ Topics: Array, Two Pointers, Binary Search

Problem Statement

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. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

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

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints: - 2 <= numbers.length <= 3 * 10^4 - -1000 <= numbers[i] <= 1000 - numbers is sorted in non-decreasing order. - -1000 <= target <= 1000 - The tests are generated such that there is exactly one solution.

---

🎨 Visual Understanding

The Problem Visualized

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

Find two numbers that sum to 9:
2 + 7 = 9 ✓

Return their 1-indexed positions: [1, 2]

Why 1-indexed?
Array indices: 0  1  2   3
Values:       [2, 7, 11, 15]
1-indexed:     1  2  3   4

Answer: [1, 2] (not [0, 1])

Difference from Two Sum (LC 1)

Two Sum (LC 1):
- Array NOT sorted
- Need HashMap: O(n) time, O(n) space
- Return 0-indexed positions

Two Sum II (LC 167):
- Array IS sorted
- Can use Two Pointers: O(n) time, O(1) space
- Return 1-indexed positions
- Guaranteed exactly one solution

Why Sorted Array Helps

numbers = [2, 7, 11, 15], target = 9

Without sorting (Two Sum approach):
Need HashMap to track seen numbers
Space: O(n)

With sorting (Two Pointers approach):
If sum < target → need larger number → move left pointer right
If sum > target → need smaller number → move right pointer left
If sum == target → found answer!
Space: O(1)

---

🎯 Approach 1: HashMap (Like Two Sum)

The Most Natural Thinking 💭

Core Logic:

Use HashMap approach from Two Sum:
1. Iterate through array
2. Check if (target - current) exists in map
3. If yes, return indices
4. If no, add current to map

Why This Works: - Works for any array (sorted or not) - Easy to understand - O(n) time complexity

Why This Fails Requirements: - Uses O(n) extra space - Problem requires O(1) space - Doesn't utilize sorted property - Not optimal for interviews

Implementation

public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        int complement = target - numbers[i];

        if (map.containsKey(complement)) {
            // Return 1-indexed positions
            return new int[] {map.get(complement) + 1, i + 1};
        }

        map.put(numbers[i], i);
    }

    return new int[] {-1, -1};  // Should never reach here
}

⏰ Time: O(n) - single pass through array
💾 Space: O(n) - HashMap storage (violates requirement)

---

✅ Approach 2: Two Pointers (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use two pointers to exploit sorted property:

1. Left pointer at start (smallest number)
2. Right pointer at end (largest number)
3. Calculate sum = numbers[left] + numbers[right]
4. If sum == target: Found answer!
5. If sum < target: Need larger sum → left++
6. If sum > target: Need smaller sum → right--

Key insight: Sorted array allows us to make greedy decisions
- Too small? Move left pointer right (get larger number)
- Too large? Move right pointer left (get smaller number)

Visual Explanation:

numbers = [2, 7, 11, 15], target = 9
           L           R

Step 1: sum = 2 + 15 = 17
        17 > 9 → Too large → R--

numbers = [2, 7, 11, 15]
           L      R

Step 2: sum = 2 + 11 = 13
        13 > 9 → Too large → R--

numbers = [2, 7, 11, 15]
           L   R

Step 3: sum = 2 + 7 = 9
        9 == 9 → Found!

Return: [1, 2] (1-indexed)

Why This Works:

Sorted array property guarantees:
- numbers[left] ≤ numbers[left+1] ≤ ... ≤ numbers[right]

If sum < target:
  - Current left is too small
  - Moving right makes right smaller (worse)
  - Only option: move left right (get larger number)

If sum > target:
  - Current right is too large
  - Moving left makes left larger (worse)
  - Only option: move right left (get smaller number)

This greedy approach always finds the answer!

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) {
            // Found the answer! Return 1-indexed positions
            return new int[] {left + 1, right + 1};
        } else if (sum < target) {
            // Sum too small, need larger number
            left++;
        } else {
            // Sum too large, need smaller number
            right--;
        }
    }

    // Should never reach here (guaranteed solution exists)
    return new int[] {-1, -1};
}

⏰ Time: O(n) - single pass, pointers meet in middle
💾 Space: O(1) - only two pointers

---

🔍 Step-by-Step Execution

Example: numbers = [2, 7, 11, 15], target = 9

Initial State:
═══════════════════════════════════════════════════════════════════
numbers = [2, 7, 11, 15]
           L           R
target = 9


Step 1: Check current sum
═══════════════════════════════════════════════════════════════════
left = 0, right = 3
sum = numbers[0] + numbers[3] = 2 + 15 = 17

Compare: 17 vs 9
17 > 9 → Sum too large, need smaller number

Action: Move right pointer left
right = 2


Step 2: Check current sum
═══════════════════════════════════════════════════════════════════
numbers = [2, 7, 11, 15]
           L      R

left = 0, right = 2
sum = numbers[0] + numbers[2] = 2 + 11 = 13

Compare: 13 vs 9
13 > 9 → Sum too large, need smaller number

Action: Move right pointer left
right = 1


Step 3: Check current sum
═══════════════════════════════════════════════════════════════════
numbers = [2, 7, 11, 15]
           L   R

left = 0, right = 1
sum = numbers[0] + numbers[1] = 2 + 7 = 9

Compare: 9 vs 9
9 == 9 → FOUND!

Return: [left + 1, right + 1] = [1, 2]


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [1, 2]
═══════════════════════════════════════════════════════════════════

Another Example: numbers = [2, 3, 4], target = 6

Initial: left=0, right=2
═══════════════════════════════════════════════════════════════════

Step 1:
numbers = [2, 3, 4]
           L     R

sum = 2 + 4 = 6
6 == 6 → FOUND!

Return: [1, 3]

Example with Negatives: numbers = [-1, 0], target = -1

Initial: left=0, right=1
═══════════════════════════════════════════════════════════════════

Step 1:
numbers = [-1, 0]
           L   R

sum = -1 + 0 = -1
-1 == -1 → FOUND!

Return: [1, 2]

---

🔍 Edge Cases

Case 1: Minimum array size
Input: numbers = [1, 2], target = 3
Output: [1, 2]
Explanation: Only two elements, they must be the answer

Case 2: Negative numbers
Input: numbers = [-5, -2, 0, 3, 5], target = -2
Output: [1, 4]
Explanation: -5 + 3 = -2

Case 3: All negative numbers
Input: numbers = [-10, -5, -3, -1], target = -8
Output: [2, 3]
Explanation: -5 + -3 = -8

Case 4: Target is zero
Input: numbers = [-3, -1, 0, 2, 3], target = 0
Output: [2, 4]
Explanation: -1 + 2 = 1, 0 + 0 won't work (can't use same element)
Actually: Need to check: -3 + 3 = 0

Case 5: Large numbers
Input: numbers = [-1000, 0, 1000], target = 0
Output: [1, 3]
Explanation: -1000 + 1000 = 0

Case 6: Consecutive numbers
Input: numbers = [1, 2, 3, 4, 5], target = 9
Output: [4, 5]
Explanation: 4 + 5 = 9

Case 7: Duplicates in array
Input: numbers = [1, 2, 2, 3], target = 4
Output: [2, 3]
Explanation: 2 + 2 = 4, return indices [2, 3] (1-indexed)

Case 8: Answer at extremes
Input: numbers = [1, 3, 5, 7, 9], target = 10
Output: [1, 5]
Explanation: 1 + 9 = 10

---

Common Mistakes

Mistake 1: Returning 0-indexed positions
❌ Wrong: 
    return new int[] {left, right};
✓ Right: 
    return new int[] {left + 1, right + 1};
Reason: Problem asks for 1-indexed positions

Mistake 2: Using HashMap when array is sorted
❌ Wrong: 
    // Using O(n) space with HashMap
    Map<Integer, Integer> map = new HashMap<>();
✓ Right: 
    // Using O(1) space with two pointers
    int left = 0, right = numbers.length - 1;
Reason: Problem requires O(1) space, sorted array allows two pointers

Mistake 3: Wrong loop condition
❌ Wrong: 
    while (left <= right) {  // Equal case is wrong
        ...
    }
✓ Right: 
    while (left < right) {
        ...
    }
Reason: Can't use same element twice, need left < right

Mistake 4: Moving wrong pointer
❌ Wrong: 
    if (sum < target) {
        right--;  // Wrong direction!
    }
✓ Right: 
    if (sum < target) {
        left++;   // Need larger sum
    }
Reason: Sum too small means need larger number (move left right)

Mistake 5: Not handling the guaranteed solution
❌ Wrong: 
    // No return statement after loop
✓ Right: 
    // After loop (though should never reach if solution exists)
    return new int[] {-1, -1};
Reason: Need return statement for compilation (even if guaranteed)

Mistake 6: Using binary search unnecessarily
❌ Wrong: 
    for (int i = 0; i < n; i++) {
        // Binary search for target - numbers[i]
    }
✓ Right: 
    // Use two pointers
Reason: Two pointers is simpler and equally efficient O(n)

Mistake 7: Not exploiting sorted property
❌ Wrong: 
    // Checking all pairs with nested loops
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (numbers[i] + numbers[j] == target) {...}
        }
    }
✓ Right: 
    // Use two pointers from both ends
Reason: O(n²) vs O(n), waste of sorted property

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: HashMap
  Time: O(n)
  Space: O(n)
  Use: Works but violates space requirement

Approach 2: Two Pointers (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Optimal solution, best for interviews

🔑 The Core Insight

Sorted Array → Two Pointers Technique

Strategy:
1. Start with two pointers at opposite ends
2. Calculate sum of elements at both pointers
3. Make greedy decision based on comparison:
   - sum == target → Found answer!
   - sum < target → Need larger sum → left++
   - sum > target → Need smaller sum → right--

Why Greedy Works:
- Array is sorted: numbers[left] ≤ ... ≤ numbers[right]
- If sum too small: Only option is to increase (move left right)
- If sum too large: Only option is to decrease (move right left)
- Pointers always converge to correct answer

Key Differences from Two Sum:
- Two Sum: Unsorted → Need HashMap
- Two Sum II: Sorted → Use Two Pointers
- Space: O(n) vs O(1)
- Return: 0-indexed vs 1-indexed

🎯 Pattern Recognition

Problem Type: Two Sum Variant
Core Pattern: Two Pointers on Sorted Array

When to Apply:
✓ Array is sorted
✓ Need to find pairs with specific sum
✓ Constant space requirement
✓ Can make greedy decisions

Key Techniques:
→ Two pointers from opposite ends
→ Compare sum with target
→ Move pointers based on comparison
→ Greedy approach for sorted arrays

Related Problems:
- Two Sum (LC 1) - Unsorted version
- 3Sum (LC 15) - Three numbers
- 3Sum Closest (LC 16) - Closest sum
- 4Sum (LC 18) - Four numbers
- Container With Most Water (LC 11)

🧠 Interview Strategy

Step 1: "Need to find two numbers that sum to target"
Step 2: "Array is sorted - can use two pointers"
Step 3: "Start from both ends, compare sum with target"
Step 4: "Move pointers based on comparison"
Step 5: "O(n) time, O(1) space"

Key Points to Mention:
- Sorted array enables two pointers
- O(1) space vs HashMap's O(n)
- Greedy decisions work due to sorted property
- Return 1-indexed positions (not 0-indexed)
- Guaranteed exactly one solution

---

📝 Quick Revision Notes

🎯 Core Concept:

Sorted array + Two Sum = Two Pointers from both ends. Compare sum with target, move pointers greedily. Return 1-indexed positions.

⚡ Quick Implementation:

public int[] twoSum(int[] a, int k) {        
    // Approach 1 - using hashmap
    // HashMap<Integer, Integer> map = new HashMap<>();
    // for(int i = 0; i < a.length; i++) {
    //     if(map.containsKey(k - a[i])) {
    //         return new int[] {map.get(k - a[i]) + 1, i + 1};
    //     }

    //     map.put(a[i], i);
    // }

    // Approach 2 - using 2 pointers as array is already sorted
    int i = 0;
    int j = a.length - 1;

    while (i < j) {
        int sum = a[i] + a[j];

        if(sum == k) {
            return new int[] {i + 1, j + 1};
        } else if(sum < k) {
            i++;                
        } else {
            j--;
        }
    }

    return new int[] {-1, -1};
}

🔑 Key Insights:

• Sorted array: Enables two pointers technique
• Two pointers: Start from both ends (left=0, right=n-1)
• Greedy decisions:
• sum < target → Need larger → left++
• sum > target → Need smaller → right--
• sum == target → Found!
• 1-indexed: Return [left+1, right+1] not [left, right]
• Loop condition: left < right (can't use same element twice)
• Space: O(1) vs HashMap's O(n)
• Time: O(n) - pointers converge in middle
• Guaranteed solution: Problem states exactly one solution exists

🎪 Memory Aid:

"SORTED → Two Pointers! Sum too SMALL → LEFT++, too LARGE → RIGHT--"
Think: "Sorted = Two ends squeeze to middle"

---

Related Patterns

• Two Sum (LC 1)
• 3Sum (LC 15)
• 3Sum Closest (LC 16)
• 4Sum (LC 18)
• Container With Most Water (LC 11)

---

Happy practicing! 🎯