Cosmic Module

Qubits of DPK

March 15, 2026

Core DSA

1️⃣ LC #304 — Range Sum Query 2D Immutable

Core Idea

2D prefix sum. prefix[i][j] = sum of rectangle from (0,0) to (i-1,j-1). Use inclusion-exclusion for range queries.

Optimized → O(mn) build | O(1) per query | O(mn) Space:

java

QUBITS OF DPK

1class NumMatrix {
2    private int[][] prefix;
3    public NumMatrix(int[][] matrix) {
4        int m = matrix.length, n = matrix[0].length;
5        prefix = new int[m+1][n+1];
6        for (int i = 1; i <= m; i++)
7            for (int j = 1; j <= n; j++)
8                prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
9    }
10    public int sumRegion(int r1, int c1, int r2, int c2) {
11        return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1];
12    }
13}

Dry Run

Input matrix:

javascript

QUBITS OF DPK

1[[3,0,1,4,2],
2 [5,6,3,2,1],
3 [1,2,0,1,5],
4 [4,1,0,1,7],
5 [1,0,3,0,5]]

Query sumRegion(2,1,4,3):

prefix[5][4] - prefix[2][4] - prefix[5][1] + prefix[2][1]
= 58 - 24 - 8 + 6 = 32

Key Tricks

Build: prefix[i][j] = matrix + top + left - topLeft (avoid double counting)
Query: prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
Both formulas use inclusion-exclusion principle

30-Second Interview Explanation

2D prefix sum using inclusion-exclusion. Build in O(mn). Each query O(1) using the 4-corner formula. Time O(mn) build, O(1) query.

️ Interview Traps

Forgetting to subtract the overlap (topLeft) in both build and query formulas

Most Common Follow-ups

Q1: Extend to mutable 2D matrix?

2D Binary Indexed Tree (Fenwick Tree). O(log m * log n) per update and query.

2️⃣ LC #327 — Count of Range Sum

Core Idea

Prefix sums. Count pairs (i,j) where lower <= prefix[j] - prefix[i] <= upper. Use merge sort to count pairs efficiently.

Optimized → O(n log n) Time | O(n) Space:

java

QUBITS OF DPK

1class Solution {
2    private int lower, upper, count;
3    public int countRangeSum(int[] nums, int lower, int upper) {
4        this.lower = lower; this.upper = upper; count = 0;
5        long[] prefix = new long[nums.length + 1];
6        for (int i = 0; i < nums.length; i++) prefix[i+1] = prefix[i] + nums[i];
7        mergeSort(prefix, 0, prefix.length);
8        return count;
9    }
10    private void mergeSort(long[] prefix, int left, int right) {
11        if (right - left <= 1) return;
12        int mid = left + (right - left) / 2;
13        mergeSort(prefix, left, mid);
14        mergeSort(prefix, mid, right);
15        int j = mid, k = mid;
16        for (int i = left; i < mid; i++) {
17            while (j < right && prefix[j] - prefix[i] < lower) j++;
18            while (k < right && prefix[k] - prefix[i] <= upper) k++;
19            count += k - j;
20        }
21        // standard merge
22        long[] sorted = new long[right - left];
23        int p = left, q = mid, idx = 0;
24        while (p < mid && q < right) sorted[idx++] = (prefix[p] <= prefix[q]) ? prefix[p++] : prefix[q++];
25        while (p < mid) sorted[idx++] = prefix[p++];
26        while (q < right) sorted[idx++] = prefix[q++];
27        System.arraycopy(sorted, 0, prefix, left, right - left);
28    }
29}

Dry Run

Input: nums = [-2,5,-1], lower=-2, upper=2

Prefix sums: [0,-2,3,2]

Valid pairs (prefix[j] - prefix[i] in [-2,2]):

(0,1): -2-0=-2
(0,3): 2-0=2
(2,3): 2-3=-1

Output: 3

Key Tricks

Build prefix sum array first
Merge sort counts valid pairs while sorting
Two pointers j,k advance monotonically across all i iterations

30-Second Interview Explanation

Count prefix sum pairs where difference is in [lower, upper]. Brute force O(n²). Merge sort on prefix array: during merge, count valid right-half entries for each left-half entry using two moving pointers. O(n log n).

️ Interview Traps

Integer overflow — use long[] for prefix sums

Most Common Follow-ups

Q1: Why merge sort and not a simpler approach?

Brute force is O(n²). TreeMap/sorted set gives O(n log n) with subMap range queries. Merge sort is also O(n log n) and elegant. Both valid interview answers.

3️⃣ LC #862 — Shortest Subarray with Sum at Least K

Core Idea

Prefix sum + monotonic deque. For each right, find leftmost prefix such that prefix[right] - prefix[left] >= k. Maintain increasing deque.

Optimized → O(n) Time | O(n) Space:

java

QUBITS OF DPK

1class Solution {
2    public int shortestSubarray(int[] nums, int k) {
3        int n = nums.length;
4        long[] prefix = new long[n+1];
5        for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
6        Deque<Integer> deque = new ArrayDeque<>();
7        int minLen = Integer.MAX_VALUE;
8        for (int i = 0; i <= n; i++) {
9            while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k) {
10                minLen = Math.min(minLen, i - deque.pollFirst());
11            }
12            while (!deque.isEmpty() && prefix[i] <= prefix[deque.peekLast()]) {
13                deque.pollLast();
14            }
15            deque.addLast(i);
16        }
17        return minLen == Integer.MAX_VALUE ? -1 : minLen;
18    }
19}

Dry Run

Input: nums = [2,-1,2], k=3

prefix = [0,2,1,3]

Output: 3

Key Tricks

Negative numbers make sliding window fail — need monotonic deque
Deque stores indices of increasing prefix sums
Pop front when sum condition met (found valid subarray), pop back to maintain monotonicity

30-Second Interview Explanation

Negatives break sliding window. Use prefix sums + monotonic deque. Deque maintains increasing prefix indices. For each right, pop front while sum >= k (valid subarray found). Pop back while current prefix <= back (maintain monotonicity). Time O(n).

️ Interview Traps

Trying sliding window — fails with negatives
Using int for prefix — overflow with large values

Most Common Follow-ups

Q1: Why does sliding window fail here?

Sliding window assumes that shrinking the window from left always reduces the sum. With negative numbers, removing a negative element from the left INCREASES the sum, breaking the monotonic assumption needed for two-pointer correctness.