Two Pointers & Sliding Window

int l = 0, r = n - 1;
 
while (l < r) {
    if (/* condition satisfied */) {
        return result;   // or record answer
    } else if (/* need to increase */) {
        l++;             // Move left pointer right
    } else {
        r--;             // Move right pointer left
    }
}

// Given a sorted array, find indices of two numbers that sum to target.
vector<int> twoSum(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
 
    while (l < r) {
        int sum = nums[l] + nums[r];
        if      (sum == target) return {l + 1, r + 1};  // 1-indexed
        else if (sum <  target) l++;   // Sum too small → increase left
        else                    r--;   // Sum too large → decrease right
    }
    return {};
}
// Time: O(n), Space: O(1)
// Why O(n)? Each iteration moves at least one pointer by 1. Total moves ≤ n.

// Find all unique triplets summing to zero.
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());   // Sort first!
    vector<vector<int>> result;
    int n = nums.size();
 
    for (int i = 0; i < n - 2; i++) {
        // Skip duplicate values for the fixed element
        if (i > 0 && nums[i] == nums[i-1]) continue;
 
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                result.push_back({nums[i], nums[l], nums[r]});
                // Skip duplicates for l and r
                while (l < r && nums[l] == nums[l+1]) l++;
                while (l < r && nums[r] == nums[r-1]) r--;
                l++; r--;
            } else if (sum < 0) {
                l++;
            } else {
                r--;
            }
        }
    }
    return result;
}
// Time: O(n²)  — O(n log n) sort + O(n) per outer element × O(n) outer
// Space: O(1) extra (output not counted)
 
/*
  nums = [-4, -1, -1, 0, 1, 2]
  i=0, nums[i]=-4: l=1(-1), r=5(2)  sum=-3 < 0 → l++
                   l=2(-1), r=5(2)  sum=-3 < 0 → l++
                   l=3(0),  r=5(2)  sum=-2 < 0 → l++
                   l=4(1),  r=5(2)  sum=-1 < 0 → l++
                   l=5 not < r=5, exit
  i=1, nums[i]=-1: l=2(-1), r=5(2)  sum=0 → [-1,-1,2] ✅
                   l=3(0),  r=4(1)  sum=0 → [-1,0,1] ✅
  i=2, skip (nums[2]==nums[1])
  i=3, nums[i]=0:  l=4(1),  r=5(2)  sum=3 > 0 → r--
                   l=4 not < r=4, exit
  Result: [[-1,-1,2],[-1,0,1]]
*/

int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1;
    int maxWater = 0;
 
    while (l < r) {
        int h = min(height[l], height[r]);
        int w = r - l;
        maxWater = max(maxWater, h * w);
 
        // Move the pointer at the shorter wall
        if (height[l] < height[r]) l++;
        else                        r--;
    }
    return maxWater;
}
// Time: O(n), Space: O(1)

// LC 680: Can we delete at most one character to make it a palindrome?
bool validPalindrome(string s) {
    auto isPalin = [&](int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++; r--;
        }
        return true;
    };
 
    int l = 0, r = s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) {
            // Try skipping s[l] or s[r]
            return isPalin(l+1, r) || isPalin(l, r-1);
        }
        l++; r--;
    }
    return true;
}
// Time: O(n), Space: O(1)

int slow = 0;   // Write position (next slot to fill)
 
for (int fast = 0; fast < n; fast++) {
    if (/* nums[fast] should be kept */) {
        nums[slow] = nums[fast];
        slow++;
    }
    // If nums[fast] should be removed, just advance fast — skip writing
}
// Elements [0, slow) are the valid result

// Modify array in-place, return the count of unique elements.
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 1;   // Position to write the next unique element
 
    for (int fast = 1; fast < (int)nums.size(); fast++) {
        if (nums[fast] != nums[fast - 1]) {  // New unique element found
            nums[slow++] = nums[fast];
        }
    }
    return slow;   // First 'slow' elements are unique
}
// Time: O(n), Space: O(1)
 
/*
  nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
  slow=1, fast scans:
  fast=1: nums[1]==nums[0] → skip
  fast=2: nums[2]!=nums[1] → nums[1]=1, slow=2
  fast=3: nums[3]==nums[2] → skip
  fast=4: nums[4]==nums[3] → skip
  fast=5: nums[5]!=nums[4] → nums[2]=2, slow=3
  ...
  Result: [0,1,2,3,4,...] with slow=5
*/

void moveZeroes(vector<int>& nums) {
    int slow = 0;   // Next position for non-zero element
 
    // Pass 1: compact all non-zero elements to front
    for (int fast = 0; fast < (int)nums.size(); fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
        }
    }
    // Pass 2: fill rest with zeros
    while (slow < (int)nums.size()) nums[slow++] = 0;
}
// Time: O(n), Space: O(1)
 
// One-pass using swap:
void moveZeroes(vector<int>& nums) {
    int slow = 0;
    for (int fast = 0; fast < (int)nums.size(); fast++) {
        if (nums[fast] != 0) {
            swap(nums[slow++], nums[fast]);
        }
    }
}

// LC 88: nums1 has m elements, nums2 has n elements.
// Merge nums2 into nums1 (nums1 has size m+n).
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1;         // Last valid element in nums1
    int j = n - 1;         // Last element in nums2
    int k = m + n - 1;     // Write position (back of nums1)
 
    while (i >= 0 && j >= 0) {
        if (nums1[i] >= nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    // Copy remaining nums2 elements (if any)
    while (j >= 0) nums1[k--] = nums2[j--];
    // Remaining nums1 elements are already in place
}
// Time: O(m + n), Space: O(1)

// Phase 1: Detect if a cycle exists
// Phase 2: Find the entry point of the cycle
 
// PHASE 1: Does a cycle exist?
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
 
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;   // Cycle detected!
    }
    return false;   // fast hit null → no cycle
}
// Time: O(n), Space: O(1)

// PHASE 2: Find the entry point of the cycle (LC 142)
ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
 
    // Phase 1: find meeting point
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (fast == nullptr || fast->next == nullptr) return nullptr;  // No cycle
 
    // Phase 2: find cycle entry
    // Mathematical proof: distance from head to entry ==
    //                     distance from meeting point to entry
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;   // Both move at same speed now
    }
    return slow;   // Cycle entry point
}
// Time: O(n), Space: O(1)
 
/*
  Why does Phase 2 work?
  Let: F = distance from head to cycle entry
       C = cycle length
       k = distance from entry to meeting point
 
  When they meet:
    slow traveled: F + k
    fast traveled: F + k + m*C  (went around cycle m times)
    fast = 2 * slow → F + k + m*C = 2(F + k)
                    → m*C = F + k
                    → F = m*C - k
 
  Resetting slow to head:
    slow travels F steps to reach entry
    fast travels m*C - k steps = exactly to entry (since it's k steps from
    the entry, and going m*C - k more steps wraps around to the entry)
*/

// When fast reaches the end, slow is at the middle
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
 
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
    // For even length: returns the SECOND middle node
    // e.g., [1,2,3,4] → returns node 3
    // For odd length:  returns the exact middle
    // e.g., [1,2,3,4,5] → returns node 3
}
// Time: O(n), Space: O(1)

bool isHappy(int n) {
    auto sumOfSquares = [](int x) {
        int s = 0;
        while (x > 0) {
            int d = x % 10;
            s += d * d;
            x /= 10;
        }
        return s;
    };
 
    int slow = n;
    int fast = sumOfSquares(n);
 
    while (fast != 1 && slow != fast) {
        slow = sumOfSquares(slow);           // One step
        fast = sumOfSquares(sumOfSquares(fast)); // Two steps
    }
    return fast == 1;
}
// Time: O(log n), Space: O(1)

// Initialize the first window [0, k-1]
datatype windowState = initial_value;
for (int i = 0; i < k; i++) {
    add arr[i] to windowState;
}
updateAnswer(windowState);
 
// Slide the window from position k to n-1
for (int i = k; i < n; i++) {
    add    arr[i]     to windowState;    // New element enters
    remove arr[i - k] from windowState; // Old element leaves
    updateAnswer(windowState);
}

int maxSumSubarray(vector<int>& arr, int k) {
    int n = arr.size();
    int windowSum = 0, maxSum = INT_MIN;
 
    // Build first window
    for (int i = 0; i < k; i++) windowSum += arr[i];
    maxSum = windowSum;
 
    // Slide
    for (int i = k; i < n; i++) {
        windowSum += arr[i];         // Add new element
        windowSum -= arr[i - k];     // Remove leftmost element
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}
// Time: O(n), Space: O(1)

bool checkInclusion(string p, string s) {
    if (p.size() > s.size()) return false;
 
    int need[26] = {}, window[26] = {};
    for (char c : p) need[c - 'a']++;
 
    int k = p.size();
    int n = s.size();
 
    // Build first window
    for (int i = 0; i < k; i++) window[s[i] - 'a']++;
 
    if (memcmp(need, window, sizeof(need)) == 0) return true;
 
    // Slide
    for (int i = k; i < n; i++) {
        window[s[i]     - 'a']++;    // Add new right element
        window[s[i - k] - 'a']--;    // Remove old left element
        if (memcmp(need, window, sizeof(need)) == 0) return true;
    }
    return false;
}
// Time: O(n), Space: O(1) — fixed 26-element arrays

bool checkInclusion(string p, string s) {
    if (p.size() > s.size()) return false;
    int need[26] = {}, window[26] = {};
    for (char c : p) need[c - 'a']++;
 
    int k = p.size(), n = s.size();
    int matches = 0;   // Count of characters with matching frequency
 
    // Pre-count how many chars have matching freq (initially 0 window)
    // We'll track this incrementally
 
    for (int i = 0; i < n; i++) {
        // Add s[i] to window
        int c = s[i] - 'a';
        window[c]++;
        if (window[c] == need[c])       matches++;
        else if (window[c] == need[c]+1) matches--;
 
        // Remove s[i-k] from window
        if (i >= k) {
            int lc = s[i - k] - 'a';
            if (window[lc] == need[lc])       matches--;
            else if (window[lc] == need[lc]+1) matches++;
            window[lc]--;
        }
 
        if (matches == 26) return true;
    }
    return false;
}
// Time: O(n), Space: O(1)

// ──── Pattern A: MAXIMUM window that satisfies condition ────
int left = 0, maxLen = 0;
// window state data structure (freq map, sum, count, etc.)
 
for (int right = 0; right < n; right++) {
    // 1. Expand: add nums[right] to window
    updateWindow(add, nums[right]);
 
    // 2. Shrink: while window VIOLATES condition, remove from left
    while (windowViolatesCondition()) {
        updateWindow(remove, nums[left]);
        left++;
    }
 
    // 3. Now window is valid — update answer
    maxLen = max(maxLen, right - left + 1);
}
 
// ──── Pattern B: MINIMUM window that satisfies condition ────
int left = 0, minLen = INT_MAX;
// window state data structure
 
for (int right = 0; right < n; right++) {
    // 1. Expand: add nums[right] to window
    updateWindow(add, nums[right]);
 
    // 2. Shrink: while window SATISFIES condition, try to shrink
    while (windowSatisfiesCondition()) {
        minLen = min(minLen, right - left + 1);  // Record BEFORE removing
        updateWindow(remove, nums[left]);
        left++;
    }
}

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> freq;
    int left = 0, maxLen = 0;
 
    for (int right = 0; right < (int)s.size(); right++) {
        freq[s[right]]++;
 
        // Shrink while duplicate exists
        while (freq[s[right]] > 1) {
            freq[s[left]]--;
            left++;
        }
 
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Time: O(n), Space: O(min(n, 128)) — at most 128 ASCII chars
 
/*
  s = "abcabcbb"
  right=0: window="a",   maxLen=1
  right=1: window="ab",  maxLen=2
  right=2: window="abc", maxLen=3
  right=3: s[3]='a', freq['a']=2 → shrink: remove 'a', left=1
           window="bca", maxLen=3
  right=4: s[4]='b', freq['b']=2 → shrink: remove 'b', left=2
           window="cab", maxLen=3
  right=5: s[5]='c', freq['c']=2 → shrink: remove 'c', left=3
           window="abc", maxLen=3
  ...
  Answer: 3
*/
 
// Optimized with last-seen index (O(n) guaranteed single pass):
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> lastSeen;
    int left = 0, maxLen = 0;
 
    for (int right = 0; right < (int)s.size(); right++) {
        if (lastSeen.count(s[right]) && lastSeen[s[right]] >= left) {
            left = lastSeen[s[right]] + 1;  // Jump left past the duplicate
        }
        lastSeen[s[right]] = right;
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, windowSum = 0;
    int minLen = INT_MAX;
 
    for (int right = 0; right < (int)nums.size(); right++) {
        windowSum += nums[right];
 
        // Shrink while sum is still >= target (Pattern B)
        while (windowSum >= target) {
            minLen = min(minLen, right - left + 1);
            windowSum -= nums[left++];
        }
    }
    return (minLen == INT_MAX) ? 0 : minLen;
}
// Time: O(n) amortized — each element added once, removed once
// Space: O(1)
 
/*
  nums = [2,3,1,2,4,3], target = 7
  right=0: sum=2,  not>=7
  right=1: sum=5,  not>=7
  right=2: sum=6,  not>=7
  right=3: sum=8,  >=7 → minLen=4, remove nums[0]=2, sum=6, left=1
           sum=6,  not>=7 (exit while)
  right=4: sum=10, >=7 → minLen=3, remove nums[1]=3, sum=7, left=2
           sum=7,  >=7 → minLen=3, remove nums[2]=1, sum=6, left=3
           sum=6,  not>=7 (exit while)
  right=5: sum=9,  >=7 → minLen=2, remove nums[3]=2, sum=7, left=4
           sum=7,  >=7 → minLen=2, remove nums[4]=4, sum=3, left=5
           sum=3,  not>=7 (exit while)
  Answer: 2 (subarray [4,3])
*/

int characterReplacement(string s, int k) {
    int freq[26] = {};
    int left = 0, maxCount = 0, maxLen = 0;
 
    for (int right = 0; right < (int)s.size(); right++) {
        freq[s[right] - 'A']++;
        maxCount = max(maxCount, freq[s[right] - 'A']);
 
        // If window is invalid: length - maxCount > k
        while ((right - left + 1) - maxCount > k) {
            freq[s[left] - 'A']--;
            left++;
            // Note: maxCount is NOT decremented here (a subtle optimization)
            // We only care about the maximum window we can achieve
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Time: O(n), Space: O(1)
 
/*
  s = "AABABBA", k = 1
  The valid window condition: windowLen - maxCount <= k
  Best answer: "AABA" → replace one B → "AAAA" (length 4) or
               "ABBA" → replace one B → "AAAA" (length 4)
  Answer: 4
*/

string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";
 
    unordered_map<char, int> need;   // Required frequencies
    for (char c : t) need[c]++;
 
    unordered_map<char, int> window; // Current window frequencies
    int required = need.size();      // # distinct chars needed
    int formed   = 0;                // # distinct chars currently satisfied
 
    int left = 0;
    int minLen = INT_MAX, minLeft = 0;
 
    for (int right = 0; right < (int)s.size(); right++) {
        // 1. Expand: add s[right] to window
        char c = s[right];
        window[c]++;
 
        // Check if this char's frequency in window satisfies its need
        if (need.count(c) && window[c] == need[c]) formed++;
 
        // 2. Shrink: while all characters are satisfied, try to minimize window
        while (formed == required) {
            // Update answer
            if (right - left + 1 < minLen) {
                minLen  = right - left + 1;
                minLeft = left;
            }
            // Remove s[left] from window
            char lc = s[left];
            window[lc]--;
            if (need.count(lc) && window[lc] < need[lc]) formed--;
            left++;
        }
    }
    return (minLen == INT_MAX) ? "" : s.substr(minLeft, minLen);
}
// Time: O(|s| + |t|), Space: O(|s| + |t|)
 
/*
  s = "ADOBECODEBANC", t = "ABC"
  need = {A:1, B:1, C:1}
  Best window: "BANC" (length 4)
*/

vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size() - 1;
    while (l < r) {
        int sum = numbers[l] + numbers[r];
        if      (sum == target) return {l + 1, r + 1};
        else if (sum < target)  l++;
        else                    r--;
    }
    return {};
}
// Time: O(n), Space: O(1)

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 1;
    for (int fast = 1; fast < (int)nums.size(); fast++) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}
// Time: O(n), Space: O(1)

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
 
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;  // Skip duplicate pivot
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                res.push_back({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 (sum < 0) l++;
            else                r--;
        }
    }
    return res;
}
// Time: O(n²), Space: O(1) extra

int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1, maxWater = 0;
    while (l < r) {
        maxWater = max(maxWater, min(height[l], height[r]) * (r - l));
        if (height[l] < height[r]) l++;
        else                        r--;
    }
    return maxWater;
}
// Time: O(n), Space: O(1)

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
// Time: O(n), Space: O(1)

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
// Time: O(n), Space: O(1)
// Note: for even length, returns the SECOND middle node.

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> lastSeen;
    int left = 0, maxLen = 0;
 
    for (int right = 0; right < (int)s.size(); right++) {
        // If s[right] was seen and is in current window, jump left past it
        if (lastSeen.count(s[right]) && lastSeen[s[right]] >= left) {
            left = lastSeen[s[right]] + 1;
        }
        lastSeen[s[right]] = right;
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Time: O(n), Space: O(min(n, 128))

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, sum = 0, minLen = INT_MAX;
 
    for (int right = 0; right < (int)nums.size(); right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return (minLen == INT_MAX) ? 0 : minLen;
}
// Time: O(n), Space: O(1)

bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    int need[26] = {}, win[26] = {};
    for (char c : s1) need[c-'a']++;
 
    int k = s1.size(), n = s2.size();
    for (int i = 0; i < k; i++) win[s2[i]-'a']++;
    if (memcmp(need, win, sizeof(need)) == 0) return true;
 
    for (int i = k; i < n; i++) {
        win[s2[i]-'a']++;
        win[s2[i-k]-'a']--;
        if (memcmp(need, win, sizeof(need)) == 0) return true;
    }
    return false;
}
// Time: O(|s1| + |s2|), Space: O(1)

int characterReplacement(string s, int k) {
    int freq[26] = {}, left = 0, maxCount = 0, maxLen = 0;
 
    for (int right = 0; right < (int)s.size(); right++) {
        maxCount = max(maxCount, ++freq[s[right]-'A']);
 
        // Window is invalid if: length - maxCount > k
        if ((right - left + 1) - maxCount > k) {
            freq[s[left]-'A']--;
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Time: O(n), Space: O(1)
// Key insight: maxCount is never decremented even when shrinking — we're
// looking for the MAXIMUM window, so we only care if we beat the current best.

int longestOnes(vector<int>& nums, int k) {
    int left = 0, zeros = 0, maxLen = 0;
 
    for (int right = 0; right < (int)nums.size(); right++) {
        if (nums[right] == 0) zeros++;
 
        // Too many zeros flipped → shrink
        while (zeros > k) {
            if (nums[left++] == 0) zeros--;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Time: O(n), Space: O(1)
// Note: identical structure to "char replacement" — both are "at most k bad elements"

string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";
 
    unordered_map<char,int> need;
    for (char c : t) need[c]++;
 
    int required = need.size(), formed = 0;
    unordered_map<char,int> win;
 
    int l = 0, minLen = INT_MAX, minL = 0;
 
    for (int r = 0; r < (int)s.size(); r++) {
        win[s[r]]++;
        if (need.count(s[r]) && win[s[r]] == need[s[r]]) formed++;
 
        while (formed == required) {
            if (r - l + 1 < minLen) { minLen = r - l + 1; minL = l; }
            win[s[l]]--;
            if (need.count(s[l]) && win[s[l]] < need[s[l]]) formed--;
            l++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(minL, minLen);
}
// Time: O(|s| + |t|), Space: O(|s| + |t|)