two_pointers.cpp

/*
Two Pointers Pattern
Mathematical Foundation: For array A[0..n-1], use indices i,j where:
- i starts at 0, j starts at n-1 (opposite ends)
- i starts at 0, j starts at 0 (same direction)
- Move based on condition: sum < target → i++, sum > target → j--
Time: O(n), Space: O(1)
*/

#include <bits/stdc++.h>
using namespace std;

// Two Sum - Sorted Array (Opposite Direction Pointers)
// LeetCode: 167. Two Sum II - Input Array Is Sorted
// https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
// Related:
// 1. Two Sum
// https://leetcode.com/problems/two-sum/
// 653. Two Sum IV - BST
// https://leetcode.com/problems/two-sum-iv-bst/
// 1214. Two Sum BSTs
// https://leetcode.com/problems/two-sum-bsts/
// 170. Two Sum III - Data structure design
// https://leetcode.com/problems/two-sum-iii-data-structure-design/
vector<int> twoSum(vector<int>& a, int t) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == t) return {l, r};
        s < t ? l++ : r--;
    }
    return {};
}

// Three Sum = 0 (Fixed + Two Pointers)
// LeetCode: 15. 3Sum
// https://leetcode.com/problems/3sum/
// Related:
// 16. 3Sum Closest
// https://leetcode.com/problems/3sum-closest/
// 18. 4Sum
// https://leetcode.com/problems/4sum/
// 259. 3Sum Smaller
// https://leetcode.com/problems/3sum-smaller/
// 611. Valid Triangle Number
// https://leetcode.com/problems/valid-triangle-number/
// 923. 3Sum With Multiplicity
// https://leetcode.com/problems/3sum-with-multiplicity/
vector<vector<int>> threeSum(vector<int>& a) {
    sort(a.begin(), a.end());
    vector<vector<int>> res;
    int n = a.size();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && a[i] == a[i-1]) continue;
        int l = i + 1, r = n - 1;
        while (l < r) {
            int s = a[i] + a[l] + a[r];
            if (s == 0) {
                res.push_back({a[i], a[l], a[r]});
                while (l < r && a[l] == a[l+1]) l++;
                while (l < r && a[r] == a[r-1]) r--;
                l++; r--;
            } else s < 0 ? l++ : r--;
        }
    }
    return res;
}

// Container With Most Water (Greedy Two Pointers)
// LeetCode: 11. Container With Most Water
// https://leetcode.com/problems/container-with-most-water/
// Related:
// 42. Trapping Rain Water
// https://leetcode.com/problems/trapping-rain-water/
// 84. Largest Rectangle in Histogram
// https://leetcode.com/problems/largest-rectangle-in-histogram/
// 407. Trapping Rain Water II
// https://leetcode.com/problems/trapping-rain-water-ii/
// 1793. Maximum Score of a Good Subarray
// https://leetcode.com/problems/maximum-score-of-a-good-subarray/
int maxArea(vector<int>& h) {
    int l = 0, r = h.size() - 1, mx = 0;
    while (l < r) {
        mx = max(mx, min(h[l], h[r]) * (r - l));
        h[l] < h[r] ? l++ : r--;
    }
    return mx;
}

// Remove Duplicates from Sorted Array (Fast-Slow Pointers)
// LeetCode: 26. Remove Duplicates from Sorted Array
// https://leetcode.com/problems/remove-duplicates-from-sorted-array/
// Related:
// 80. Remove Duplicates from Sorted Array II
// https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
// 27. Remove Element
// https://leetcode.com/problems/remove-element/
// 283. Move Zeroes
// https://leetcode.com/problems/move-zeroes/
// 905. Sort Array By Parity
// https://leetcode.com/problems/sort-array-by-parity/
// 922. Sort Array By Parity II
// https://leetcode.com/problems/sort-array-by-parity-ii/
int removeDuplicates(vector<int>& a) {
    int j = 1;
    for (int i = 1; i < a.size(); i++)
        if (a[i] != a[i-1]) a[j++] = a[i];
    return j;
}

// Valid Palindrome (Opposite Direction Pointers)
// LeetCode: 125. Valid Palindrome
// https://leetcode.com/problems/valid-palindrome/
// Related:
// 680. Valid Palindrome II
// https://leetcode.com/problems/valid-palindrome-ii/
// 234. Palindrome Linked List
// https://leetcode.com/problems/palindrome-linked-list/
// 5. Longest Palindromic Substring
// https://leetcode.com/problems/longest-palindromic-substring/
// 647. Palindromic Substrings
// https://leetcode.com/problems/palindromic-substrings/
// 131. Palindrome Partitioning
// https://leetcode.com/problems/palindrome-partitioning/
bool isPalindrome(string s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        while (l < r && !isalnum(s[l])) l++;
        while (l < r && !isalnum(s[r])) r--;
        if (tolower(s[l++]) != tolower(s[r--])) return false;
    }
    return true;
}

// Trapping Rain Water (Greedy Two Pointers)
// LeetCode: 42. Trapping Rain Water
// https://leetcode.com/problems/trapping-rain-water/
// Related:
// 11. Container With Most Water
// https://leetcode.com/problems/container-with-most-water/
// 407. Trapping Rain Water II
// https://leetcode.com/problems/trapping-rain-water-ii/
// 84. Largest Rectangle in Histogram
// https://leetcode.com/problems/largest-rectangle-in-histogram/
// 1943. Describe the Painting
// https://leetcode.com/problems/describe-the-painting/
// 2334. Subarray With Elements Greater Than Varying Threshold
// https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold/
int trap(vector<int>& h) {
    int l = 0, r = h.size() - 1, lm = 0, rm = 0, w = 0;
    while (l < r) {
        if (h[l] < h[r]) {
            h[l] >= lm ? lm = h[l] : w += lm - h[l];
            l++;
        } else {
            h[r] >= rm ? rm = h[r] : w += rm - h[r];
            r--;
        }
    }
    return w;
}