Two Pointers

// 1) Two sum on a SORTED array — O(n)
function twoSum(arr, target) {
    let i = 0, j = arr.length - 1;
    while (i < j) {
        const s = arr[i] + arr[j];
        if (s === target) return [i, j];
        if (s < target) i++;
        else            j--;
    }
    return null;
}

// 2) Remove duplicates from a sorted array in-place — O(n)
function removeDuplicates(arr) {
    if (arr.length === 0) return 0;
    let w = 0;
    for (let r = 1; r < arr.length; r++) {
        if (arr[r] !== arr[w]) {
            w++;
            arr[w] = arr[r];
        }
    }
    return w + 1;     // new length
}

// 3) Reverse an array in-place
function reverse(arr) {
    let i = 0, j = arr.length - 1;
    while (i < j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++; j--;
    }
}

// 4) Container with most water (LeetCode 11)
function maxArea(h) {
    let i = 0, j = h.length - 1, best = 0;
    while (i < j) {
        const a = (j - i) * Math.min(h[i], h[j]);
        if (a > best) best = a;
        if (h[i] < h[j]) i++;
        else             j--;
    }
    return best;
}

// === Sliding window ===

// 5) Maximum sum subarray of size K — fixed window
function maxSumK(arr, k) {
    let sum = 0;
    for (let i = 0; i < k; i++) sum += arr[i];
    let best = sum;
    for (let i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k];
        if (sum > best) best = sum;
    }
    return best;
}

// 6) Minimum-size subarray with sum >= target — variable window
function minSubLen(target, arr) {
    let l = 0, sum = 0, best = Infinity;
    for (let r = 0; r < arr.length; r++) {
        sum += arr[r];
        while (sum >= target) {
            best = Math.min(best, r - l + 1);
            sum -= arr[l++];
        }
    }
    return best === Infinity ? 0 : best;
}

// 7) Longest substring without repeating characters
function lengthOfLongestSubstring(s) {
    const seen = new Map();
    let l = 0, best = 0;
    for (let r = 0; r < s.length; r++) {
        const c = s[r];
        if (seen.has(c) && seen.get(c) >= l) l = seen.get(c) + 1;
        seen.set(c, r);
        best = Math.max(best, r - l + 1);
    }
    return best;
}

// 8) Permutation in string — does s2 contain any permutation of s1?
function checkInclusion(s1, s2) {
    if (s1.length > s2.length) return false;
    const need = new Array(26).fill(0);
    const have = new Array(26).fill(0);
    const A = 'a'.charCodeAt(0);
    for (const c of s1) need[c.charCodeAt(0) - A]++;
    let matches = 0;
    for (let i = 0; i < 26; i++) if (need[i] === 0) matches++;
    let l = 0;
    for (let r = 0; r < s2.length; r++) {
        const ri = s2.charCodeAt(r) - A;
        have[ri]++;
        if (have[ri] === need[ri]) matches++;
        else if (have[ri] === need[ri] + 1) matches--;
        if (r - l + 1 > s1.length) {
            const li = s2.charCodeAt(l) - A;
            if (have[li] === need[li]) matches--;
            else if (have[li] === need[li] + 1) matches++;
            have[li]--;
            l++;
        }
        if (matches === 26) return true;
    }
    return false;
}

// 9) Partition / move (Dutch national flag style)
function moveZeroesEnd(arr) {
    let w = 0;
    for (let r = 0; r < arr.length; r++) {
        if (arr[r] !== 0) {
            [arr[w], arr[r]] = [arr[r], arr[w]];
            w++;
        }
    }
}

// 10) Three sum — sort + fix-one + two-pointer for the rest
function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const out = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let l = i + 1, r = nums.length - 1;
        while (l < r) {
            const s = nums[i] + nums[l] + nums[r];
            if (s === 0) {
                out.push([nums[i], nums[l], nums[r]]);
                while (l < r && nums[l] === nums[l + 1]) l++;
                while (l < r && nums[r] === nums[r - 1]) r--;
                l++; r--;
            } else if (s < 0) l++;
            else              r--;
        }
    }
    return out;
}

// === When to reach for the technique ===
//   • Array / string with 'subarray with property X' or 'pair / triple with sum X'
//   • Sorted input (or sort-then-solve makes it tractable)
//   • 'Longest / shortest substring satisfying condition' → variable-size sliding window
//   • In-place partition / removal — read + write pointers
//   • Cycle detection in linked list — slow + fast pointer (Floyd)

// === Common pitfalls ===
//   • Forgetting to advance the inner pointer when the condition is met
//   • Off-by-one when shrinking the window (do you remove arr[l] before or after l++?)
//   • Mixed inclusive / exclusive bounds — decide once, stick with it
//   • Two-pointer on UNSORTED arrays for 'two sum' — that's a hash-map problem, not two-pointer

// === Decision flow ===
//   1. Is the array sorted (or can I sort it)?            → two-pointer maybe works
//   2. Am I looking for a subarray / substring property?  → sliding window
//   3. Pair / triplet sum problem?                         → sort + two-pointer
//   4. Otherwise → think hash map, prefix sum, or DP

// Sorted array: find pair summing to target.
function pair(nums, t) {
    let l = 0, r = nums.length - 1;
    while (l < r) {
        const s = nums[l] + nums[r];
        if (s === t) return [l, r];
        if (s < t)   l++; else r--;
    }
    return [];
}