Prefix Sum — Advanced Templates

take k from the two ends, MAXIMIZE taken
        ⇕  (complement)
leave a contiguous window of length n-k, MINIMIZE it

answer = total - min(window of fixed length n-k)

[ 1, 2, 3, 4, 5, 6, 1 ]   n=7, k=3  → window length w = 4
  └──── take ────┘           windows: [1,2,3,4]=10  [2,3,4,5]=14
        ↑ leave the cheapest length-4 window          [3,4,5,6]=18  [4,5,6,1]=16
  total = 22, min window = 10  →  answer = 22 - 10 = 12 ✓

// java
// LC 1423 - Maximum Points You Can Obtain from Cards
// IDEA: complement — maximize both ends == minimize the middle window of length n-k
// time = O(n), space = O(1)
public int maxScore(int[] cardPoints, int k) {
    int n = cardPoints.length, w = n - k;
    int total = 0;
    for (int x : cardPoints) total += x;
    if (w == 0) return total;               // take everything

    int win = 0;
    for (int i = 0; i < w; i++) win += cardPoints[i];
    int minWin = win;

    // slide the fixed-length window (rolling prefix-sum difference)
    for (int i = w; i < n; i++) {
        win += cardPoints[i] - cardPoints[i - w];
        minWin = Math.min(minWin, win);
    }
    return total - minWin;
}

# python
# LC 1423 - Maximum Points You Can Obtain from Cards
# IDEA: complement — maximize both ends == minimize the middle window of length n-k
# time = O(n), space = O(1)
def maxScore(cardPoints, k):
    n = len(cardPoints)
    w = n - k
    total = sum(cardPoints)
    if w == 0:
        return total

    win = sum(cardPoints[:w])
    min_win = win
    for i in range(w, n):
        win += cardPoints[i] - cardPoints[i - w]   # slide right, drop left
        min_win = min(min_win, win)

    return total - min_win

// java
// LC 1658 - Minimum Operations to Reduce X to Zero
// IDEA: remove-from-ends summing to x  ==  keep the LONGEST middle subarray summing to (total - x)
// time = O(n), space = O(1)
public int minOperations(int[] nums, int x) {
    int n = nums.length, total = 0;
    for (int v : nums) total += v;
    int target = total - x;
    if (target < 0) return -1;

    int left = 0, sum = 0, best = -1;
    for (int right = 0; right < n; right++) {
        sum += nums[right];
        while (sum > target) sum -= nums[left++];     // values are positive → safe to shrink
        if (sum == target) best = Math.max(best, right - left + 1);
    }
    return best == -1 ? -1 : n - best;                // ops = n - kept
}

# python
# LC 1658 - Minimum Operations to Reduce X to Zero
# time = O(n), space = O(1)
def minOperations(nums, x):
    n = len(nums)
    target = sum(nums) - x
    if target < 0:
        return -1

    left = s = 0
    best = -1
    for right, v in enumerate(nums):
        s += v
        while s > target:
            s -= nums[left]
            left += 1
        if s == target:
            best = max(best, right - left + 1)

    return -1 if best == -1 else n - best

Two rules, both discard indices that can never be the best LEFT end:

1) POP FRONT while  p[i] - p[dq.front] >= K
   → dq.front already satisfies the condition at this i.
     Any later i' > i gives a LONGER subarray, so this front is used once and dropped.

2) POP BACK while  p[dq.back] >= p[i]
   → index i has a prefix sum <= dq.back but is FURTHER RIGHT.
     It is better as a left end in every way (smaller sum AND shorter span). dq.back is dead.

Deque therefore holds indices with STRICTLY INCREASING prefix sums. Each index is
pushed once and popped once → O(n) total.

i=0 p=0 : deque empty          → push 0            dq = [0]
i=1 p=2 : 2-0=2 < 3            → push 1            dq = [0,1]
i=2 p=1 : 1-0=1 < 3 ; p[1]=2 >= 1 → pop back 1, push 2   dq = [0,2]
i=3 p=3 : 3-p[0]=3 >= 3 → ans = 3-0 = 3, pop front
          3-p[2]=2 < 3 → stop ; push 3             dq = [2,3]
answer = 3

// java
// LC 862 - Shortest Subarray with Sum at Least K
// IDEA: prefix sum + monotonic increasing deque (handles negative numbers)
// time = O(n), space = O(n)
public int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] p = new long[n + 1];                       // long: sums can overflow int
    for (int i = 0; i < n; i++) p[i + 1] = p[i] + nums[i];

    Deque<Integer> dq = new ArrayDeque<>();           // indices, p[] increasing
    int ans = n + 1;

    for (int i = 0; i <= n; i++) {
        // rule 1: front satisfies the condition -> record and retire it
        while (!dq.isEmpty() && p[i] - p[dq.peekFirst()] >= k) {
            ans = Math.min(ans, i - dq.pollFirst());
        }
        // rule 2: keep prefix sums increasing
        while (!dq.isEmpty() && p[dq.peekLast()] >= p[i]) {
            dq.pollLast();
        }
        dq.offerLast(i);
    }
    return ans <= n ? ans : -1;
}

# python
# LC 862 - Shortest Subarray with Sum at Least K
# IDEA: prefix sum + monotonic increasing deque (handles negative numbers)
# time = O(n), space = O(n)
from collections import deque
from itertools import accumulate

def shortestSubarray(nums, k):
    n = len(nums)
    p = list(accumulate(nums, initial=0))
    dq = deque()          # indices with increasing p[]
    ans = n + 1

    for i in range(n + 1):
        while dq and p[i] - p[dq[0]] >= k:      # rule 1: found a valid left end
            ans = min(ans, i - dq.popleft())
        while dq and p[dq[-1]] >= p[i]:         # rule 2: keep p[] increasing
            dq.pop()
        dq.append(i)

    return ans if ans <= n else -1

fix top/bottom rows                  1-D array of column sums
┌───────────────┐
│ . . . . . . . │
│ a b c d e f g │ ← top          colSum = [a+h, b+i, c+j, ...]
│ h i j k l m n │ ← bottom
│ . . . . . . . │                then answer the 1-D version of the problem
└───────────────┘

O(m²) row pairs × O(n · cost of the 1-D solver)

// java
// LC 363 - Max Sum of Rectangle No Larger Than K
// IDEA: fix row pair -> column sums -> 1D "max subarray sum <= k" via TreeSet ceiling
// time = O(m^2 * n * log n), space = O(n)
public int maxSumSubmatrix(int[][] matrix, int k) {
    int m = matrix.length, n = matrix[0].length;
    int best = Integer.MIN_VALUE;

    for (int top = 0; top < m; top++) {
        int[] colSum = new int[n];                     // reset per top row
        for (int bot = top; bot < m; bot++) {
            for (int c = 0; c < n; c++) colSum[c] += matrix[bot][c];   // extend downward

            // ---- 1D: max subarray sum <= k ----
            TreeSet<Integer> seen = new TreeSet<>();
            seen.add(0);                               // empty prefix sentinel
            int run = 0;
            for (int c = 0; c < n; c++) {
                run += colSum[c];
                // want smallest prefix_j with prefix_j >= run - k
                Integer lo = seen.ceiling(run - k);
                if (lo != null) best = Math.max(best, run - lo);
                seen.add(run);
            }
        }
    }
    return best;
}

# python
# LC 363 - Max Sum of Rectangle No Larger Than K
# IDEA: fix row pair -> column sums -> 1D "max subarray sum <= k" via bisect on sorted prefixes
# time = O(m^2 * n * log n), space = O(n)
from bisect import bisect_left, insort

def maxSumSubmatrix(matrix, k):
    m, n = len(matrix), len(matrix[0])
    best = float('-inf')

    for top in range(m):
        col = [0] * n
        for bot in range(top, m):
            for c in range(n):
                col[c] += matrix[bot][c]

            # ---- 1D: max subarray sum <= k ----
            seen = [0]          # sorted prefix sums, 0 = empty prefix
            run = 0
            for c in range(n):
                run += col[c]
                idx = bisect_left(seen, run - k)   # smallest prefix >= run - k
                if idx < len(seen):
                    best = max(best, run - seen[idx])
                insort(seen, run)

    return best

// java
// LC 1310 - XOR Queries of a Subarray
// IDEA: prefix XOR; xor(l..r) = p[r+1] ^ p[l]  (XOR is its own inverse)
// time = O(n + q), space = O(n)
public int[] xorQueries(int[] arr, int[][] queries) {
    int n = arr.length;
    int[] p = new int[n + 1];
    for (int i = 0; i < n; i++) p[i + 1] = p[i] ^ arr[i];

    int[] res = new int[queries.length];
    for (int i = 0; i < queries.length; i++) {
        res[i] = p[queries[i][1] + 1] ^ p[queries[i][0]];
    }
    return res;
}

# python
# LC 1310 - XOR Queries of a Subarray
# time = O(n + q), space = O(n)
from itertools import accumulate

def xorQueries(arr, queries):
    p = list(accumulate(arr, lambda a, b: a ^ b, initial=0))
    return [p[r + 1] ^ p[l] for l, r in queries]

// java
// LC 1915 - Number of Wonderful Substrings
// IDEA: prefix XOR bitmask (parity fingerprint) + counting map, like Template 2
// time = O(10n), space = O(2^10)
public long wonderfulSubstrings(String word) {
    long[] cnt = new long[1 << 10];       // mask -> how many prefixes had it
    cnt[0] = 1;                           // empty prefix sentinel (== the {0:1} trick)
    int mask = 0;
    long res = 0;

    for (char ch : word.toCharArray()) {
        mask ^= 1 << (ch - 'a');          // flip this letter's parity bit

        res += cnt[mask];                 // all letters even  (mask ^ mask == 0)
        for (int b = 0; b < 10; b++) {
            res += cnt[mask ^ (1 << b)];  // exactly ONE letter odd
        }
        cnt[mask]++;
    }
    return res;
}

# python
# LC 1915 - Number of Wonderful Substrings
# time = O(10n), space = O(2^10)
def wonderfulSubstrings(word):
    cnt = [0] * 1024
    cnt[0] = 1                       # empty prefix
    mask = res = 0

    for ch in word:
        mask ^= 1 << (ord(ch) - ord('a'))
        res += cnt[mask]             # 0 odd letters
        for b in range(10):
            res += cnt[mask ^ (1 << b)]   # exactly 1 odd letter
        cnt[mask] += 1

    return res

# python
# LC 2021 - Brightest Position on Street
# IDEA: hashmap difference array + line sweep over sorted event keys
# time = O(n log n), space = O(n)
from collections import defaultdict

class Solution:
    def brightestPosition(self, lights):
        events = defaultdict(int)

        # 1) mark events: +1 where coverage starts, -1 right AFTER it ends
        for p, r in lights:
            events[p - r] += 1          # starts illuminating at (p - r)
            events[p + r + 1] -= 1      # stops illuminating AFTER (p + r)  <-- note the +1

        max_brightness = curr = ans_pos = 0

        # 2) sweep positions in ascending order (sorted keys == the prefix sum walk)
        for pos in sorted(events.keys()):
            curr += events[pos]
            # STRICT `>` + ascending order => ties keep the SMALLEST position
            if curr > max_brightness:
                max_brightness = curr
                ans_pos = pos

        return ans_pos

// java
// LC 2021 - Brightest Position on Street
// IDEA: TreeMap keeps keys sorted, so the sweep is just an in-order walk
// time = O(n log n), space = O(n)
public int brightestPosition(int[][] lights) {
    TreeMap<Integer, Integer> events = new TreeMap<>();
    for (int[] l : lights) {
        int p = l[0], r = l[1];
        events.merge(p - r, 1, Integer::sum);
        events.merge(p + r + 1, -1, Integer::sum);
    }

    int max = 0, curr = 0, ans = 0;
    for (Map.Entry<Integer, Integer> e : events.entrySet()) {  // already ascending
        curr += e.getValue();
        if (curr > max) {          // strict > => smallest position wins ties
            max = curr;
            ans = e.getKey();
        }
    }
    return ans;
}

tree:        1              chains:   1        (prefix 1)
            / \                       1 -> 4   (prefix 5)
           4   5                       1 -> 5   (prefix 6)

correct answer = 1   (the single node `1`)

DFS pre-order, map starts {0: 1}:
  node 1 : cur=1  cnt += map[1-1=0] = 1   -> cnt=1   map{0:1, 1:1}
  node 4 : cur=5  cnt += map[5-1=4] = 0   -> cnt=1   map{0:1, 1:1, 5:1}
  << no undo here: prefix 5 stays in the map >>
  node 5 : cur=6  cnt += map[6-1=5] = 1   -> cnt=2   WRONG
                  ^ that "5" is the left branch's prefix; 4 is not an ancestor of 5

# python
# LC 437 - Path Sum III
# IDEA: pre-order DFS + prefix sum HashMap + backtrack ("2-sum on the root->node chain")
# time = O(n), space = O(h)
from collections import defaultdict

class Solution:
    def pathSum(self, root, targetSum):
        prefix = defaultdict(int)
        prefix[0] = 1                 # the empty prefix: a path starting AT the root
        self.cnt = 0

        def dfs(node, cur):
            if not node:
                return

            cur += node.val                       # 1) extend the chain

            # 2) cur - old = targetSum  ->  old = cur - targetSum
            #    every recorded ancestor prefix `old` is one path ending at `node`
            self.cnt += prefix[cur - targetSum]

            prefix[cur] += 1                      # 3) publish this prefix to the subtree

            dfs(node.left, cur)
            dfs(node.right, cur)

            prefix[cur] -= 1                      # 4) BACKTRACK - leave no trace for siblings

        dfs(root, 0)
        return self.cnt

// java
// LC 437 - Path Sum III
// IDEA: pre-order DFS + prefix sum HashMap + backtrack
// time = O(n), space = O(h)
public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefix = new HashMap<>();
    prefix.put(0L, 1);                       // empty prefix
    return dfs(root, 0L, targetSum, prefix);
}

private int dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) {
    if (node == null) return 0;

    cur += node.val;                                            // 1) extend
    int res = prefix.getOrDefault(cur - target, 0);              // 2) count

    prefix.merge(cur, 1, Integer::sum);                          // 3) publish
    res += dfs(node.left,  cur, target, prefix);
    res += dfs(node.right, cur, target, prefix);
    prefix.merge(cur, -1, Integer::sum);                         // 4) BACKTRACK

    return res;
}

root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

chain 10 -> 5 -> 3 -> 3        map = {0:1}
  10 : cur=10  need 10-8=2   map[2]=0            cnt=0   map{0:1,10:1}
   5 : cur=15  need 15-8=7   map[7]=0            cnt=0   map{...,15:1}
   3 : cur=18  need 18-8=10  map[10]=1  <-- HIT  cnt=1   map{...,18:1}
       the hit prefix 10 is node `10`, so the path is (10..18] = 5 -> 3  = 8  ✓
   3 : cur=21  need 21-8=13  map[13]=0           cnt=1
  ... unwind: 21, 18, 15, 10 each -= 1

the other two paths are found the same way: 5 -> 2 -> 1, and -3 -> 11