110-two-pointers-problem-11.md

Two-pointers Problem 11

LeetCode: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ Difficulty: Medium

Problem

Solve this two-pointers problem efficiently.

Brute Force Approach

function solve(nums) {
    let result = [];
    // Check all possibilities
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            // Process pairs
            if (/* condition */) {
                result.push([i, j]);
            }
        }
    }
    return result;
}

⏱️ Time: O(n²) or O(n³)
💾 Space: O(n)

Optimal Approach

function solve(nums) {
    const map = new Map();
    const result = [];
    
    for (let i = 0; i < nums.length; i++) {
        // Use hash map for O(1) lookup
        const complement = target - nums[i];
        if (map.has(complement)) {
            result.push([map.get(complement), i]);
        }
        map.set(nums[i], i);
    }
    return result;
}

⏱️ Time: O(n) or O(n log n)
💾 Space: O(n) or O(1)

Visual Diagram

Array: [1, 2, 3, 4, 5]
        L           R
        ↓           ↓
       [1, 2, 3, 4, 5]

Move based on condition:
   L → ← R
      ↓ ↓
     [1,2,3,4,5]

---

Visit LeetCode for full problem description.