Sliding Window — 進階視窗形態

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()   # stores indices; nums[dq[0]] is always window max
    result = []

    for i, num in enumerate(nums):
        # Remove elements outside window
        if dq and dq[0] == i - k:
            dq.popleft()
        # Maintain decreasing order — remove smaller elements from back
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

// LC 239 - Sliding Window Maximum
// IDEA: Monotonic decreasing deque — front = max of current window
// time = O(N), space = O(k)
public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // stores indices
    for (int i = 0; i < n; i++) {
        // remove out-of-window indices
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
        // maintain decreasing order
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
        deque.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = nums[deque.peekFirst()];
    }
    return ans;
}

# python
# LC 904 - Fruit Into Baskets
# IDEA: SLIDING WINDOW + HASHMAP — longest window with at most 2 distinct types
# time = O(n), space = O(1)  (map holds at most 3 keys)
class Solution(object):
    def totalFruit(self, fruits):
        if not fruits:
            return 0

        basket = {}          # fruit_type -> count in current window
        left = 0
        max_fruit = 0

        for right in range(len(fruits)):
            # 1) expand: add the fruit at right
            f = fruits[right]
            basket[f] = basket.get(f, 0) + 1

            # 2) shrink: while > 2 distinct types, drop from the left
            while len(basket) > 2:
                lf = fruits[left]
                basket[lf] -= 1
                if basket[lf] == 0:   # type fully gone -> remove key
                    del basket[lf]
                left += 1

            # 3) record best valid window width
            max_fruit = max(max_fruit, right - left + 1)

        return max_fruit

// LC 159 - Longest Substring with At Most Two Distinct Characters
// IDEA: Sliding window with HashMap — shrink when distinct > 2
// time = O(N), space = O(1)
public int lengthOfLongestSubstringTwoDistinct(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    int l = 0, ans = 0;
    for (int r = 0; r < s.length(); r++) {
        freq.merge(s.charAt(r), 1, Integer::sum);
        while (freq.size() > 2) {
            char lc = s.charAt(l);
            freq.merge(lc, -1, Integer::sum);
            if (freq.get(lc) == 0) freq.remove(lc);
            l++;
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

"EXACTLY 5 distinct vowels"  →  atMost(5) - atMost(4)
       └── only counts vowel-only windows (consonant resets window)

# Python - LC 2062 Count Vowel Substrings of a String
# IDEA: atMost(5) - atMost(4), with consonant resetting the window
class Solution(object):
    def countVowelSubstrings(self, word):
        # time = O(n) (atMost called twice), space = O(1) (≤ 5 vowels tracked)
        def countAtMost(max_unique):
            vowels = set("aeiou")
            cnt_map = {}
            l = 0
            ans = 0

            for r in range(len(word)):
                # CRITICAL: a consonant ruins the vowel-only window
                # → clear map and jump left past the consonant
                if word[r] not in vowels:
                    cnt_map.clear()
                    l = r + 1
                    continue

                cnt_map[word[r]] = cnt_map.get(word[r], 0) + 1

                # shrink from left while too many distinct vowels
                while len(cnt_map) > max_unique:
                    cnt_map[word[l]] -= 1
                    if cnt_map[word[l]] == 0:
                        del cnt_map[word[l]]
                    l += 1

                # # of valid vowel-only substrings ending at r = window length
                ans += (r - l + 1)

            return ans

        # EXACTLY 5 distinct vowels = atMost(5) - atMost(4)
        return countAtMost(5) - countAtMost(4)

// Java - LC 2062 Count Vowel Substrings of a String
// IDEA: atMost(5) - atMost(4), with consonant resetting the window
class Solution {
    /**
     * time = O(n) (atMost called twice), space = O(1) (≤ 5 vowels tracked)
     */
    public int countVowelSubstrings(String word) {
        // EXACTLY 5 distinct vowels = atMost(5) - atMost(4)
        return countAtMost(word, 5) - countAtMost(word, 4);
    }

    private int countAtMost(String word, int maxUnique) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        Map<Character, Integer> cntMap = new HashMap<>();
        int l = 0, ans = 0;

        for (int r = 0; r < word.length(); r++) {
            char c = word.charAt(r);

            // CRITICAL: a consonant ruins the vowel-only window
            // → clear map and jump left past the consonant
            if (!vowels.contains(c)) {
                cntMap.clear();
                l = r + 1;
                continue;
            }

            cntMap.put(c, cntMap.getOrDefault(c, 0) + 1);

            // shrink from left while too many distinct vowels
            while (cntMap.size() > maxUnique) {
                char leftChar = word.charAt(l);
                cntMap.put(leftChar, cntMap.get(leftChar) - 1);
                if (cntMap.get(leftChar) == 0) {
                    cntMap.remove(leftChar);
                }
                l++;
            }

            // # of valid vowel-only substrings ending at r = window length
            ans += (r - l + 1);
        }

        return ans;
    }
}

Array: [1, 2, 1, 3], K = 2 (exactly 2 distinct)

At Most 2 Distinct:
Index 0 (1): [1] ✓                                 → count = 1
Index 1 (2): [2] ✓, [1,2] ✓                        → count = 2
Index 2 (1): [1] ✓, [2,1] ✓, [1,2,1] ✓             → count = 3
Index 3 (3): [3] ✓, [1,3] ✓, but NOT [2,1,3] ❌    → count = 2
                   (window shrinks to [1,3])

Total At Most 2: 1 + 2 + 3 + 2 = 8

At Most 1 Distinct:
Index 0 (1): [1] ✓                                 → count = 1
Index 1 (2): [2] ✓, but NOT [1,2] ❌               → count = 1
                   (window shrinks to [2])
Index 2 (1): [1] ✓, but NOT [2,1] ❌               → count = 1
                   (window shrinks to [1])
Index 3 (3): [3] ✓, but NOT [1,3] ❌               → count = 1
                   (window shrinks to [3])

Total At Most 1: 1 + 1 + 1 + 1 = 4

Exactly 2 Distinct = 8 - 4 = 4 ✓

The 4 subarrays with exactly 2 distinct:
[1,2], [1,2,1], [2,1], [1,3]

✅ "exactly K distinct/different"
✅ "exactly K times"
✅ "exactly K occurrences"
✅ "subarrays with exactly K ..."
✅ COUNTING problems (not max/min length)

✅ "at most K"
✅ "maximum length with ≤ K"
✅ "minimum length with ≥ K"
✅ "longest substring with at most K"

# Wrong: Doesn't handle k=0
def exactly_k(nums, k):
    return at_most_k(nums, k) - at_most_k(nums, k - 1)
    # at_most_k(nums, -1) may fail!

# Right: Handle k=0 explicitly
def exactly_k(nums, k):
    if k == 0:
        return 0
    return at_most_k(nums, k) - at_most_k(nums, k - 1)

# Wrong: Using "exactly K" transformation for max length
def longest_k_distinct(s, k):
    # This gives COUNT, not LENGTH!
    return at_most_k(s, k) - at_most_k(s, k - 1)  # ❌

# Right: Direct at_most_k for max length
def longest_k_distinct(s, k):
    # Track max window size during at_most_k
    return at_most_k_max_length(s, k)  # ✓

# For COUNTING subarrays: use right - left + 1
count += right - left + 1

# For MAX LENGTH: track max window size
max_length = max(max_length, right - left + 1)

Interviewer: "Count subarrays with exactly K ..."
→ Think: "Exactly K = At Most K - At Most (K-1)"

Interviewer: "Find longest substring with at most K ..."
→ Think: "Direct sliding window, no subtraction needed"

Time: O(n) - each element added once, removed at most once in each pass
      Total: 2 passes × O(n) = O(n)

Space: O(k) - HashMap stores at most K distinct elements

# Naive attempt (WRONG!)
def exactly_k_direct(nums, k):
    left = 0
    count = 0
    window = {}

    for right in range(len(nums)):
        window[nums[right]] = window.get(nums[right], 0) + 1

        # When to shrink? This is tricky!
        # If len(window) > k: shrink (too many distinct)
        # If len(window) < k: can't count yet (too few distinct)
        # If len(window) == k: count, but should we shrink?

        # If we shrink when == k, we might miss valid subarrays
        # If we don't shrink, we might count invalid subarrays

        # There's no clean condition! ❌

    return count

# Window validity is monotonic:
# - If window is valid (≤ K), all sub-windows are valid
# - If window becomes invalid (> K), shrink until valid
# - Clear shrinking condition: while len(window) > k

# This monotonic property makes sliding window perfect!

Let S(k) = set of all subarrays with at most k distinct elements

S(2) = {[1], [1,2], [1,2,1], [2], [2,1], [1], [1,3], [3], ...}
S(1) = {[1], [2], [1], [3], ...}  (only single-element subarrays)

S(2) \ S(1) = subarrays in S(2) but not in S(1)
            = subarrays with MORE than 1 but AT MOST 2 distinct
            = subarrays with EXACTLY 2 distinct ✓

Generalized: S(k) \ S(k-1) = subarrays with exactly k distinct

nums = [2,2,1,2,1], k = 2

At r = 4 (last element), valid subarrays ending here:
  [1,2,1]        → starts at index 2
  [2,1,2,1]      → starts at index 1
  [2,2,1,2,1]    → starts at index 0

→ 3 valid left boundaries — but pure sliding window finds only 1!

Is the condition monotonic? (e.g., sum ≤ k, distinct ≤ k)
  ├── YES → Pure Sliding Window
  └── NO (exactly k, == k) →
        ├── atMost(k) - atMost(k-1)  [two sliding window passes]
        ├── Prefix Sum + HashMap      [one pass, O(n) space]
        └── Prefix Trick in Sliding Window [one pass, O(1) space — see "Prefix Trick Inside the Window" below]

private int atMost(int[] nums, int k) {
    int l = 0, res = 0, oddCount = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] % 2 == 1) oddCount++;
        while (oddCount > k) {
            if (nums[l] % 2 == 1) oddCount--;
            l++;
        }
        res += (r - l + 1);   // all subarrays ending at r with ≤ k odds
    }
    return res;
}

public int numberOfSubarrays(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);  // base case: empty prefix has 0 odd numbers
    int oddCount = 0, res = 0;
    for (int val : nums) {
        if (val % 2 == 1) oddCount++;
        // how many previous prefixes had (oddCount - k) odds?
        // → those prefixes + current position = subarray with exactly k odds
        res += map.getOrDefault(oddCount - k, 0);
        map.put(oddCount, map.getOrDefault(oddCount, 0) + 1);
    }
    return res;
}

When oddCount reaches k (window has exactly k odds):
  - Count how many even numbers are at the LEFT edge of the window
    before hitting the (k-th-from-left) odd number
  - Each of these even numbers gives one more valid left boundary
  - Store this count as `prefix`

After the window shrinks past the leftmost odd:
  - oddCount drops below k, so the while loop exits
  - But `prefix` (the "even gap") is PRESERVED
  - For every future r that keeps oddCount == k,
    those same left boundaries are still valid → add `prefix` again

// Prefix Trick + Sliding Window
// time = O(N), space = O(1)
public int exactlyK(int[] nums, int k) {
    int l = 0, res = 0, oddCount = 0, prefix = 0;

    for (int r = 0; r < nums.length; r++) {
        if (nums[r] % 2 == 1) {
            oddCount++;
            prefix = 0;  // reset: new odd changes left boundary gap
        }

        // Shrink left while window has exactly k odds,
        // counting even elements we skip at the left edge
        while (oddCount == k) {
            prefix++;                        // one more valid left boundary
            if (nums[l] % 2 == 1) oddCount--;
            l++;
        }

        // prefix = # of valid left boundaries for subarrays ending at r
        res += prefix;
    }

    return res;
}

r=0 (2): oddCount=0, prefix=0  → res=0
r=1 (2): oddCount=0, prefix=0  → res=0
r=2 (1): oddCount=1, prefix=0  → res=0   (new odd, prefix reset)
r=3 (2): oddCount=1, prefix=0  → res=0
r=4 (1): oddCount=2, prefix=0  → new odd, prefix reset to 0
  while oddCount==2:
    prefix=1, nums[0]=2 (even), l=1       → oddCount still 2
    prefix=2, nums[1]=2 (even), l=2       → oddCount still 2
    prefix=3, nums[2]=1 (odd),  l=3, oddCount=1 → exit while
  res += 3 → res=3

Instead of minimizing elements removed from edges,
MAXIMIZE the elements kept in the middle.

Min Edge Removals = Total Length − Max Middle Subarray Length

removed_sum + remaining_sum = total_sum

If removed_sum must equal x:
  remaining_sum = total_sum - x   ← this becomes the sliding window target

Total Elements − Max Middle Subarray (sum = target) = Min Operations

Visual layout:

MIN EDGE PIECES (Ops)              MAX MIDDLE SUBARRAY
 | nums[0] | nums[1] |      | ... | ... | ... |
 \_______________________/  \_______________________/
     Removed from Edges           Left in the Center
          (Sum = x)               (Sum = total_sum - x)

Step 1: Compute total = sum(nums)
Step 2: Compute target = total - x
        • If target == 0 → must remove ALL elements → return nums.length
        • If target < 0  → impossible             → return -1
Step 3: Sliding window to find LONGEST subarray with sum == target
Step 4: return nums.length - maxLen   (or -1 if not found)

public int minOperations(int[] nums, int x) {
    int total = 0;
    for (int num : nums) total += num;

    int target = total - x;
    if (target == 0) return nums.length;
    if (target < 0)  return -1;

    int n = nums.length, l = 0, sum = 0, maxLen = -1;

    for (int r = 0; r < n; r++) {
        sum += nums[r];

        // shrink from left while sum exceeds target
        while (l <= r && sum > target) {
            sum -= nums[l++];
        }

        // valid window found — track longest
        if (sum == target) {
            maxLen = Math.max(maxLen, r - l + 1);
        }
    }

    return maxLen == -1 ? -1 : n - maxLen;
}

total = 11,  target = 11 - 5 = 6

r  nums[r]  window     sum   action          maxLen
0    1      [1]          1   sum < target      -1
1    1      [1,1]        2   sum < target      -1
2    4      [1,1,4]      6   sum == target      3   ← window [0..2]
3    2      [1,1,4,2]    8   shrink left
           [1,4,2]       7   shrink left
           [4,2]         6   sum == target      3   ← window [2..3]
4    3      [4,2,3]      9   shrink left
           [2,3]         5   sum < target       3

maxLen = 3  →  answer = 5 - 3 = 2 ✓

[ take l from front ][ ....... leftover ....... ][ take r from back ],  l + r = k

leftover is ALWAYS a contiguous block of size n - k.
  answer = total - min(sum of any window of size n - k)

This flips a "choose from both ends" problem into a plain fixed-size window scan.
Edge case: k >= n → take everything → return total (window size would be 0).

// LC 1423 - Maximum Points You Can Obtain from Cards
// IDEA: complement trick — maximize ends == total - min fixed window of size n-k
// time = O(n), space = O(1)
public int maxScore(int[] cardPoints, int k) {
    int n = cardPoints.length, total = 0;
    for (int c : cardPoints) total += c;
    if (k >= n) return total;                     // take every card

    int win = n - k, cur = 0;
    for (int i = 0; i < win; i++) cur += cardPoints[i];
    int minWindow = cur;

    for (int i = win; i < n; i++) {               // slide the leftover window
        cur += cardPoints[i] - cardPoints[i - win];
        minWindow = Math.min(minWindow, cur);
    }
    return total - minWindow;
}

# python
# LC 1423 - Maximum Points You Can Obtain from Cards
# IDEA: complement trick — maximize ends == total - min fixed window of size n-k
# time = O(n), space = O(1)
def maxScore(cardPoints, k):
    n = len(cardPoints)
    total = sum(cardPoints)
    if k >= n:
        return total                              # take every card

    win = n - k
    cur = sum(cardPoints[:win])
    min_window = cur

    for i in range(win, n):                       # slide the leftover window
        cur += cardPoints[i] - cardPoints[i - win]
        min_window = min(min_window, cur)
    return total - min_window

n = 7, total = 22, leftover window size = 7 - 3 = 4

window            sum
[1,2,3,4]         10   ← min so far
  [2,3,4,5]       14
    [3,4,5,6]     18
      [4,5,6,1]   16
min = 10 at [1,2,3,4] (indices 0..3)  →  the cards taken are indices 4,5,6 = 5+6+1 = 12
answer = 22 - 10 = 12   (0 from the front, 3 from the back) ✓

✅ "Pick k items from the front and/or back"        → min/max window of size n-k
✅ "Remove a contiguous block to optimize the rest" → same idea, inverted
✅ "Choose a prefix + a suffix under a constraint"  → the gap between them is one window
❌ Picks may come from the middle → complement is no longer contiguous, trick fails

Step 1: w[i] = sum of the window starting at i  (rolling sum, i in [0, n-k])
Step 2: left[i]  = index of the BEST window start in [0, i]        (prefix argmax, scan →)
        right[i] = index of the BEST window start in [i, n-k]      (suffix argmax, scan ←)
Step 3: for every middle start `mid` in [k, m-1-k]:
            total = w[left[mid-k]] + w[mid] + w[right[mid+k]]
        keep the max.

Lexicographically smallest indices (LC 689 requires it):
  - prefix scan uses STRICT `>`  → keeps the earliest tie
  - suffix scan uses `>=`        → also keeps the earliest tie (scanning right-to-left)
  - middle loop uses strict `>`  → keeps the earliest mid

// LC 689 - Maximum Sum of 3 Non-Overlapping Subarrays
// IDEA: rolling window sums + prefix/suffix argmax, then fix the middle window
// time = O(n), space = O(n)
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    int n = nums.length;
    int[] w = new int[n - k + 1];                     // w[i] = sum of window starting at i
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += nums[i];
        if (i >= k) cur -= nums[i - k];
        if (i >= k - 1) w[i - k + 1] = cur;
    }

    int m = w.length;
    int[] left = new int[m], right = new int[m];
    int best = 0;
    for (int i = 0; i < m; i++) {                     // strict > → earliest tie wins
        if (w[i] > w[best]) best = i;
        left[i] = best;
    }
    best = m - 1;
    for (int i = m - 1; i >= 0; i--) {                // >= while scanning left → earliest tie
        if (w[i] >= w[best]) best = i;
        right[i] = best;
    }

    int[] ans = null;
    int bestSum = -1;
    for (int mid = k; mid + k < m; mid++) {           // fix the middle window
        int l = left[mid - k], r = right[mid + k];
        int sum = w[l] + w[mid] + w[r];
        if (sum > bestSum) {
            bestSum = sum;
            ans = new int[]{l, mid, r};
        }
    }
    return ans;
}

# python
# LC 689 - Maximum Sum of 3 Non-Overlapping Subarrays
# IDEA: rolling window sums + prefix/suffix argmax, then fix the middle window
# time = O(n), space = O(n)
def maxSumOfThreeSubarrays(nums, k):
    n = len(nums)
    w = [0] * (n - k + 1)                      # w[i] = sum of window starting at i
    cur = sum(nums[:k])
    w[0] = cur
    for i in range(k, n):
        cur += nums[i] - nums[i - k]
        w[i - k + 1] = cur

    m = len(w)
    left, right = [0] * m, [0] * m
    best = 0
    for i in range(m):                         # strict > → earliest tie wins
        if w[i] > w[best]:
            best = i
        left[i] = best
    best = m - 1
    for i in range(m - 1, -1, -1):             # >= while scanning left → earliest tie
        if w[i] >= w[best]:
            best = i
        right[i] = best

    ans, best_sum = None, -1
    for mid in range(k, m - k):                # fix the middle window
        l, r = left[mid - k], right[mid + k]
        s = w[l] + w[mid] + w[r]
        if s > best_sum:
            best_sum, ans = s, [l, mid, r]
    return ans

w  = [3, 3, 3, 8, 13, 12, 6]         (sums of every length-2 window)
left  = [0, 0, 0, 3, 4, 4, 4]        (prefix argmax, earliest tie)
right = [4, 4, 4, 4, 4, 5, 6]        (suffix argmax, earliest tie)

mid = 2 → l=left[0]=0, r=right[4]=4 → 3 + 3 + 13 = 19
mid = 3 → l=left[1]=0, r=right[5]=5 → 3 + 8 + 12 = 23  ← best
mid = 4 → l=left[2]=0, r=right[6]=6 → 3 + 13 + 6 = 22
answer = [0, 3, 5] ✓

For j windows (j > 3), drop the fixed-middle trick and go DP:
  dp[j][i] = best total using j windows within the prefix ending at i
           = max(dp[j][i-1],  dp[j-1][i-k] + w[i-k+1])
  → O(n * j) time. The 3-window case just hardcodes j = 3 with prefix/suffix argmax.

Indices:  0 . . . [i-M-L] . . . [i-M] . . . [i] . . . n
                   |--- L window ---| |--- M window ---|

L window sum: prefix[i-M]   - prefix[i-M-L]
M window sum: prefix[i]     - prefix[i-M]

// LC 1031 - Maximum Sum of Two Non-Overlapping Subarrays
// IDEA: Prefix Sum + Sliding Window — try both L-before-M and M-before-L
// time = O(N), space = O(N)
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
    return Math.max(
        helper(nums, firstLen, secondLen),   // firstLen before secondLen
        helper(nums, secondLen, firstLen));  // secondLen before firstLen
}

// L comes before M; i is the exclusive end of the M window
private int helper(int[] nums, int L, int M) {
    int n = nums.length;
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    int maxL = 0; // best L-window sum seen so far (left of current M)
    int ans   = 0;

    /**
     * i = ending position (exclusive) of M window
     *
     * 1. i starts from L + M  (minimum length to fit both windows)
     * 2. i ends at <= n       (prefix has size n+1)
     *
     * Index layout:
     *   0 . . . [i-M-L] . . . [i-M] . . . [i] . . . n
     *            |--- L window ---| |--- M window ---|
     *
     *   L window: prefix[i-M]   - prefix[i-M-L]   (range [i-M-L, i-M))
     *   M window: prefix[i]     - prefix[i-M]      (range [i-M,   i))
     */
    for (int i = L + M; i <= n; i++) {
        // L window: [i-M-L, i-M)
        int lSum = prefix[i - M] - prefix[i - M - L];
        maxL = Math.max(maxL, lSum);          // keep best L seen so far

        // M window: [i-M, i)
        int mSum = prefix[i] - prefix[i - M];

        ans = Math.max(ans, maxL + mSum);     // best non-overlapping pair
    }

    return ans;
}

Window = the last `indexDiff` elements (a fixed-capacity set, evicted by index).
Question per new element x: does the window hold a value within valueDiff of x?

Bucket trick:
  bucket(x) = floor(x / (valueDiff + 1))     ← width = valueDiff + 1
  - Two values in the SAME bucket always differ by <= valueDiff  → answer immediately.
  - Values that differ by <= valueDiff but sit in different buckets
    must be in ADJACENT buckets → check bucket-1 and bucket+1 only.
  - Any bucket holds at most one live value (a second one would have returned true).

Why width = valueDiff + 1, not valueDiff?
  With width w, same-bucket values differ by <= w-1. Setting w = valueDiff + 1
  makes "same bucket ⇒ valid" exactly true.

// LC 220 - Contains Duplicate III
// IDEA: fixed-index sliding window + bucketing by value (width = valueDiff + 1)
// time = O(n), space = O(min(n, indexDiff))
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    if (indexDiff <= 0 || valueDiff < 0) return false;
    long w = (long) valueDiff + 1;                 // bucket width
    Map<Long, Long> buckets = new HashMap<>();     // bucketId -> the single value living there

    for (int i = 0; i < nums.length; i++) {
        long x = nums[i];
        long b = Math.floorDiv(x, w);              // floorDiv (NOT /) keeps negatives correct

        if (buckets.containsKey(b)) return true;                                  // same bucket
        if (buckets.containsKey(b - 1) && x - buckets.get(b - 1) <= valueDiff) return true;
        if (buckets.containsKey(b + 1) && buckets.get(b + 1) - x <= valueDiff) return true;

        buckets.put(b, x);
        // evict the element that just fell out of the index window
        if (i >= indexDiff) buckets.remove(Math.floorDiv((long) nums[i - indexDiff], w));
    }
    return false;
}

# python
# LC 220 - Contains Duplicate III
# IDEA: fixed-index sliding window + bucketing by value (width = valueDiff + 1)
# time = O(n), space = O(min(n, indexDiff))
def containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff):
    if indexDiff <= 0 or valueDiff < 0:
        return False
    w = valueDiff + 1                      # bucket width
    buckets = {}                           # bucketId -> the single value living there

    for i, x in enumerate(nums):
        b = x // w                         # python floor division already handles negatives
        if b in buckets:
            return True
        if b - 1 in buckets and abs(x - buckets[b - 1]) <= valueDiff:
            return True
        if b + 1 in buckets and abs(x - buckets[b + 1]) <= valueDiff:
            return True

        buckets[b] = x
        if i >= indexDiff:                 # evict element leaving the index window
            del buckets[nums[i - indexDiff] // w]
    return False

Keep a TreeSet (Java) / SortedList (Python) of the last indexDiff values.
For each x: floor/ceiling query → is there a neighbour within valueDiff?
  TreeSet<Long> set; Long lo = set.floor(x); Long hi = set.ceiling(x);
Slower (log k) but far easier to get right under interview pressure —
state the bucket version as the O(n) follow-up.

❌ b = x / w in Java → truncates toward zero, so -3/5 == 0 == 3/5 (wrong bucket for negatives).
   ✅ Math.floorDiv(x, w)
❌ Using width = valueDiff → same-bucket pairs may differ by valueDiff+... ; off-by-one bugs.
❌ Forgetting the eviction step → window becomes "whole prefix", indexDiff ignored.
❌ int overflow on `x - neighbour` when values span ±2^31 → widen to long.

words all have length L, there are m of them → answer substrings have length L*m.
Any valid start index s satisfies s % L == r for some r in [0, L).
Two starts with the same remainder share chunk boundaries → they belong to
ONE sliding window pass. So run L passes, offset = 0..L-1, each stepping by L.

Inside a pass, this is just the classic "window with a frequency map + match counter":
  - chunk not in need           → hard reset (clear map, jump left past it)
  - chunk over-counted          → shrink from the left until it fits
  - count == m                  → record start, then shrink one chunk to keep scanning

Total work: L passes * (n / L) chunks = O(n) chunk steps, each O(L) to hash a substring.

// LC 30 - Substring with Concatenation of All Words
// IDEA: wordLen independent sliding windows (one per offset) + freq map & match counter
// time = O(wordLen * n), space = O(m * wordLen)
public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> res = new ArrayList<>();
    if (s == null || s.isEmpty() || words.length == 0) return res;
    int wl = words[0].length(), m = words.length;
    if (s.length() < wl * m) return res;

    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.merge(w, 1, Integer::sum);

    for (int offset = 0; offset < wl; offset++) {           // one window per alignment
        int left = offset, count = 0;
        Map<String, Integer> window = new HashMap<>();

        for (int right = offset; right + wl <= s.length(); right += wl) {
            String word = s.substring(right, right + wl);

            if (!need.containsKey(word)) {                  // unusable chunk → hard reset
                window.clear();
                count = 0;
                left = right + wl;
                continue;
            }

            window.merge(word, 1, Integer::sum);
            count++;
            while (window.get(word) > need.get(word)) {     // too many copies → shrink
                window.merge(s.substring(left, left + wl), -1, Integer::sum);
                left += wl;
                count--;
            }
            if (count == m) {                               // full match at `left`
                res.add(left);
                window.merge(s.substring(left, left + wl), -1, Integer::sum);
                left += wl;
                count--;
            }
        }
    }
    return res;
}

# python
# LC 30 - Substring with Concatenation of All Words
# IDEA: wordLen independent sliding windows (one per offset) + freq map & match counter
# time = O(wordLen * n), space = O(m * wordLen)
from collections import Counter, defaultdict

def findSubstring(s, words):
    if not s or not words:
        return []
    wl, m = len(words[0]), len(words)
    need = Counter(words)
    res = []

    for offset in range(wl):                       # one window per alignment
        left, count = offset, 0
        window = defaultdict(int)

        for right in range(offset, len(s) - wl + 1, wl):
            word = s[right:right + wl]

            if word not in need:                   # unusable chunk → hard reset
                window.clear()
                count, left = 0, right + wl
                continue

            window[word] += 1
            count += 1
            while window[word] > need[word]:       # too many copies → shrink
                window[s[left:left + wl]] -= 1
                left += wl
                count -= 1
            if count == m:                         # full match at `left`
                res.append(left)
                window[s[left:left + wl]] -= 1
                left += wl
                count -= 1
    return res

offset = 0 → chunks: bar foo the foo bar man
  right=0  "bar" ✓  count=1
  right=3  "foo" ✓  count=2 == m → record left=0, drop "bar", left=3, count=1
  right=6  "the" ✗  reset, left=9
  right=9  "foo" ✓  count=1
  right=12 "bar" ✓  count=2 == m → record left=9 ✓
offset = 1 → chunks: arf oot hef oob arm  → all ✗, nothing
offset = 2 → chunks: rfo oth efo oba rma  → all ✗, nothing
result = [0, 9]

// LC 187 - Repeated DNA Sequences
// IDEA: fixed-size window of 10 + 2-bit rolling encode (A=0,C=1,G=2,T=3) + HashSet
// time = O(n), space = O(n)
public List<String> findRepeatedDnaSequences(String s) {
    int L = 10;
    List<String> res = new ArrayList<>();
    if (s.length() < L) return res;

    int[] code = new int[26];
    code['C' - 'A'] = 1; code['G' - 'A'] = 2; code['T' - 'A'] = 3;   // 'A' stays 0
    int mask = (1 << (2 * L)) - 1, h = 0;
    Set<Integer> seen = new HashSet<>(), added = new HashSet<>();

    for (int i = 0; i < s.length(); i++) {
        h = ((h << 2) | code[s.charAt(i) - 'A']) & mask;   // push 2 bits, drop the oldest
        if (i >= L - 1) {
            if (!seen.add(h) && added.add(h)) res.add(s.substring(i - L + 1, i + 1));
        }
    }
    return res;
}

# python
# LC 187 - Repeated DNA Sequences
# IDEA: fixed-size window of 10 + 2-bit rolling encode (A=0,C=1,G=2,T=3) + set
# time = O(n), space = O(n)
def findRepeatedDnaSequences(s):
    L = 10
    if len(s) < L:
        return []
    code = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
    mask = (1 << (2 * L)) - 1
    h = 0
    seen, out = set(), set()

    for i, ch in enumerate(s):
        h = ((h << 2) | code[ch]) & mask       # push 2 bits, drop the oldest
        if i >= L - 1:
            if h in seen:
                out.add(s[i - L + 1:i + 1])
            else:
                seen.add(h)
    return list(out)

Sort both interval arrays by start time.
Use one pointer per array (i, j).
At each step:
  overlap = [max(start_i, start_j), min(end_i, end_j)]
  If overlap length >= required → answer found.
  Otherwise, advance the pointer whose interval ends EARLIER.

Why advance the earlier-ending interval?
  The interval that ends first can NEVER produce a larger overlap
  with any future interval — it's already exhausted.
  Keeping the later-ending interval gives the best chance of
  overlapping with something further right.

Step 1: Sort both arrays by start time — O(n log n + m log m)
Step 2: i = 0, j = 0 (one pointer per array)
Step 3: while i < len(A) and j < len(B):
          overlapStart = max(A[i][0], B[j][0])
          overlapEnd   = min(A[i][1], B[j][1])
          if overlapEnd - overlapStart >= duration:
              return [overlapStart, overlapStart + duration]
          if A[i][1] < B[j][1]:   # A[i] ends earlier → advance i
              i++
          else:                    # B[j] ends earlier (or tie) → advance j
              j++
Step 4: return [] (no valid overlap found)

// LC 1229 - Meeting Scheduler
// IDEA: Sort + Two Pointers on interval arrays
// time = O(n log n + m log m), space = O(1)
public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
    Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
    Arrays.sort(slots2, (a, b) -> a[0] - b[0]);

    int i = 0, j = 0;
    while (i < slots1.length && j < slots2.length) {
        int overlapStart = Math.max(slots1[i][0], slots2[j][0]);
        int overlapEnd   = Math.min(slots1[i][1], slots2[j][1]);

        if (overlapEnd - overlapStart >= duration) {
            return Arrays.asList(overlapStart, overlapStart + duration);
        }

        // advance the pointer whose interval ends earlier
        if (slots1[i][1] < slots2[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return Collections.emptyList();
}

i  j  overlapStart  overlapEnd  length  action
0  0  max(10,0)=10  min(50,15)=15   5   < 8 → slots1[0][1]=50 > slots2[0][1]=15 → j++
0  1  max(10,60)=60 min(50,70)=50  -10  < 8 → slots1[0][1]=50 < slots2[1][1]=70 → i++
1  1  max(60,60)=60 min(120,70)=70  10  ≥ 8 → return [60, 68] ✓

✅ Use Sort + Two Pointers on Intervals when:
   - Two sorted interval arrays, find first/all overlaps
   - "Earliest common availability" type problems
   - Merging or intersecting two independently sorted lists

✅ Related patterns:
   - Single interval list → sort + greedy scan (LC 56, 435)
   - Min rooms / conflicts → sort starts & ends separately (LC 253)
   - All intersections → same two-pointer loop, collect instead of return early (LC 986)