Cosmic Module

Qubits of DPK

March 15, 2026

Core DSA

1️⃣ LC #303 — Range Sum Query Immutable

Core Idea

Precompute prefix sums. Any range sum [l,r] = prefix[r+1] - prefix[l] in O(1).

Brute Force → O(n) per query | O(1) Space:

Scan from l to r each query.

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

java

QUBITS OF DPK

1class NumArray {
2    private int[] prefix;
3    public NumArray(int[] nums) {
4        prefix = new int[nums.length + 1];
5        for (int i = 0; i < nums.length; i++)
6            prefix[i + 1] = prefix[i] + nums[i];
7    }
8    public int sumRange(int left, int right) {
9        return prefix[right + 1] - prefix[left];
10    }
11}

Dry Run

Input: nums = [-2, 0, 3, -5, 2, -1]

Prefix array build:

prefix = [0, -2, -2, 1, -4, -2, -3]

Queries:

sumRange(0,2) = prefix[3] - prefix[0] = 1 - 0 = 1
sumRange(2,5) = prefix[6] - prefix[2] = -3 - (-2) = -1

Key Tricks

prefix[0] = 0 — represents empty prefix (crucial)
Size is n+1 not n
Query formula: prefix[right+1] - prefix[left]

30-Second Interview Explanation

Build prefix array of size n+1 where prefix[i] = sum of nums[0..i-1]. Range sum [l,r] = prefix[r+1] - prefix[l]. O(n) build, O(1) per query.

️ Interview Traps

Off-by-one: prefix[right+1] - prefix[left] not prefix[right] - prefix[left-1]
prefix[0] = 0 not prefix[0] = nums[0]

Most Common Follow-ups

Q1: LC #304 — 2D Range Sum (matrix)?

Extend to 2D: prefix[i][j] = sum of rectangle from (0,0) to (i-1,j-1). Query: prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1] (inclusion-exclusion). Build O(mn), query O(1).

Q2: What if array is mutable (updates allowed)?

Use Binary Indexed Tree (Fenwick Tree) or Segment Tree. Both give O(log n) update and O(log n) query instead of O(n) rebuild. This is LC #307 — Range Sum Query Mutable.

2️⃣ LC #2574 — Left and Right Sum Differences

Core Idea

For each index, compute sum of all elements to its left and right. Use prefix and suffix arrays.

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

java

QUBITS OF DPK

1class Solution {
2    public int[] leftRightDifference(int[] nums) {
3        int n = nums.length;
4        int[] leftSum = new int[n], rightSum = new int[n], result = new int[n];
5        for (int i = 1; i < n; i++) leftSum[i] = leftSum[i-1] + nums[i-1];
6        for (int i = n-2; i >= 0; i--) rightSum[i] = rightSum[i+1] + nums[i+1];
7        for (int i = 0; i < n; i++) result[i] = Math.abs(leftSum[i] - rightSum[i]);
8        return result;
9    }
10}

Dry Run

Input: nums = [10, 4, 8, 3]

Output: [15, 1, 11, 22]

Key Tricks

leftSum[0] = 0, rightSum[n-1] = 0 — boundary elements have no left/right
Build left left-to-right, right right-to-left

30-Second Interview Explanation

Build prefix (left sums) and suffix (right sums) in two passes. Result[i] = abs(leftSum[i] - rightSum[i]). Time O(n), Space O(n).

️ Interview Traps

Including current element in left or right sum — they're excluded by definition

Most Common Follow-ups

Q1: Can you do it in O(1) extra space?

Yes — compute total sum first. Then single pass: leftSum starts at 0, rightSum = total - leftSum - nums[i]. Same as Pivot Index (LC #724) approach.

3️⃣ LC #1732 — Find the Highest Altitude

Core Idea

Running prefix sum of gain array gives altitude at each point. Find maximum.

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

java

QUBITS OF DPK

1class Solution {
2    public int largestAltitude(int[] gain) {
3        int currentAltitude = 0, maxAltitude = 0;
4        for (int g : gain) {
5            currentAltitude += g;
6            maxAltitude = Math.max(maxAltitude, currentAltitude);
7        }
8        return maxAltitude;
9    }
10}

Dry Run

Input: gain = [-5, 1, 5, 0, -7]

Output: 1

Key Tricks

Start altitude = 0 (starting point), maxAltitude = 0 (starting point is valid)
Running sum of gain = altitude at each biker point

30-Second Interview Explanation

Running prefix sum of gain array = altitude at each point. Track max. Initialize both to 0 since starting altitude is 0. Time O(n), Space O(1).

️ Interview Traps

Initializing maxAltitude to gain[0] instead of 0 — starting point (altitude 0) might be the max

Most Common Follow-ups

Q1: Return the index of highest altitude?

Track maxIndex alongside maxAltitude. Update when new max found.

4️⃣ LC #1991 — Find the Middle Index

Core Idea

Identical to LC #724 Pivot Index. rightSum = totalSum - leftSum - nums[i].

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

java

QUBITS OF DPK

1class Solution {
2    public int findMiddleIndex(int[] nums) {
3        int totalSum = 0;
4        for (int num : nums) totalSum += num;
5        int leftSum = 0;
6        for (int i = 0; i < nums.length; i++) {
7            int rightSum = totalSum - leftSum - nums[i];
8            if (leftSum == rightSum) return i;
9            leftSum += nums[i];
10        }
11        return -1;
12    }
13}

Dry Run

Input: nums = [2, 3, -1, 8, 4], totalSum = 16

Output: 3

Key Tricks

rightSum = totalSum - leftSum - nums[i]
Update leftSum AFTER the check
Identical logic to LC #724

30-Second Interview Explanation

rightSum = totalSum - leftSum - current. Single pass. Time O(n), Space O(1).

️ Interview Traps

Updating leftSum before check — includes current element

Most Common Follow-ups

Q1: This is identical to LC #724 — what's the difference?

Exactly the same problem. LC #1991 asks for leftSum == rightSum (not including pivot), LC #724 asks for the same. They're functionally identical — same code solves both.

5️⃣ LC #1310 — XOR Queries of a Subarray

Core Idea

Prefix XOR. XOR of range [l, r] = prefix[r+1] XOR prefix[l].

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

java

QUBITS OF DPK

1class Solution {
2    public int[] xorQueries(int[] arr, int[][] queries) {
3        int n = arr.length;
4        int[] prefix = new int[n + 1];
5        for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] ^ arr[i];
6        int[] result = new int[queries.length];
7        for (int i = 0; i < queries.length; i++)
8            result[i] = prefix[queries[i][1]+1] ^ prefix[queries[i][0]];
9        return result;
10    }
11}

Dry Run

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]

Prefix XOR:

prefix = [0, 1, 2, 6, 14]

Queries:

[0,1]: prefix[2]^prefix[0] = 2^0 = 2
[1,2]: prefix[3]^prefix[1] = 6^1 = 7
[0,3]: prefix[4]^prefix[0] = 14^0 = 14
[3,3]: prefix[4]^prefix[3] = 14^6 = 8

Key Tricks

Same structure as prefix sum but with XOR operator
prefix[r+1] ^ prefix[l] gives XOR of range [l,r]
Works because XOR is self-inverse: a ^ a = 0

30-Second Interview Explanation

Prefix XOR array. Range XOR [l,r] = prefix[r+1] XOR prefix[l]. Build O(n), each query O(1). Time O(n+q), Space O(n).

️ Interview Traps

Using prefix[r] ^ prefix[l-1] — off by one without the +1 shift

Most Common Follow-ups

Q1: Why does XOR prefix work like sum prefix?

XOR is associative, commutative, and self-inverse (a^a=0). Just like subtraction cancels sum, XOR-ing the same prefix twice cancels it. prefix[r+1] ^ prefix[l] = XOR of elements from l to r because the [0,l-1] portion cancels out.

6️⃣ LC #238 — Product of Array Except Self

Core Idea

result[i] = prefix product left of i × suffix product right of i. Store prefix in result, multiply suffix on the fly.

(This problem appears in Pattern 1 Hard — see that solution page for full details)

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

java

QUBITS OF DPK

1class Solution {
2    public int[] productExceptSelf(int[] nums) {
3        int n = nums.length;
4        int[] result = new int[n];
5        result[0] = 1;
6        for (int i = 1; i < n; i++) result[i] = result[i-1] * nums[i-1];
7        int suffix = 1;
8        for (int i = n-1; i >= 0; i--) { result[i] *= suffix; suffix *= nums[i]; }
9        return result;
10    }
11}

Dry Run

Input: nums = [1,2,3,4]

Left pass: [1,1,2,6]

Right pass (suffix=1): index 3→2→1→0 gives [24,12,8,6]

Output: [24,12,8,6]

Key Tricks

Left pass fills prefix, right pass multiplies suffix in-place
No division allowed — and breaks for zeros

30-Second Interview Explanation

Each answer = left prefix × right suffix. First pass stores prefix. Second pass multiplies suffix on the fly. No division. Time O(n), Space O(1).

️ Interview Traps

Division approach breaks for zeros

Most Common Follow-ups

Q1: What if array has zeros?

Prefx/suffix approach handles naturally — zero contributes 0 to products where it appears, correctly making all products 0 for those positions.

7️⃣ LC #977 — Squares of a Sorted Array

Core Idea

Negatives and positives both increase when squared moving away from zero. Two pointers from both ends, fill result from largest to smallest.

Brute Force → O(n log n): Square all, sort.

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

java

QUBITS OF DPK

1class Solution {
2    public int[] sortedSquares(int[] nums) {
3        int n = nums.length;
4        int[] result = new int[n];
5        int left = 0, right = n-1, index = n-1;
6        while (left <= right) {
7            int leftSq = nums[left] * nums[left];
8            int rightSq = nums[right] * nums[right];
9            if (leftSq > rightSq) { result[index--] = leftSq; left++; }
10            else { result[index--] = rightSq; right--; }
11        }
12        return result;
13    }
14}

Dry Run

Input: nums = [-4,-1,0,3,10]

Output: [0,1,9,16,100]

Key Tricks

Fill result from back — largest squares go first
Largest square is always at one of the two ends
Two pointers inward, result pointer backward

30-Second Interview Explanation

Largest squares at both ends. Two pointers from ends, fill result array from back. Larger square goes to current back index. Time O(n), Space O(n).

️ Interview Traps

Trying to fill from front — you'd need to shift elements
Not handling all-negative or all-positive arrays (works correctly either way)

Most Common Follow-ups

Q1: Can you do it in-place O(1) extra space?

No clean O(n) in-place solution. The O(n) two-pointer approach requires the output array. Best in-place is O(n log n) sort after squaring.

8️⃣ LC #1413 — Minimum Value to Get Positive Step by Step Sum

Core Idea

Find minimum prefix sum. Answer = max(1, 1 - minPrefixSum) so running total never drops below 1.

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

java

QUBITS OF DPK

1class Solution {
2    public int minStartValue(int[] nums) {
3        int prefixSum = 0, minPrefix = 0;
4        for (int num : nums) {
5            prefixSum += num;
6            minPrefix = Math.min(minPrefix, prefixSum);
7        }
8        return Math.max(1, 1 - minPrefix);
9    }
10}

Dry Run

Input: nums = [-3,2,-3,4,2]

Answer = max(1, 1-(-4)) = max(1, 5) = 5

Key Tricks

Need: startValue + minPrefixSum >= 1 → startValue >= 1 - minPrefixSum
Math.max(1, ...) ensures minimum answer is 1 even if all sums are positive

30-Second Interview Explanation

Find minimum prefix sum across array. Answer = max(1, 1 - minPrefixSum). This ensures startValue + every prefix sum >= 1. Time O(n), Space O(1).

️ Interview Traps

Forgetting Math.max(1, ...) — if all elements positive, answer must still be at least 1

Most Common Follow-ups

Q1: What if we need total >= k instead of >= 1?

Change formula to Math.max(1, k - minPrefixSum). Same logic, just different target threshold.

9️⃣ LC #1893 — Check if All 1's Are at Least Length K Places Apart

Core Idea

Track last seen position of 1. If gap between consecutive 1s is less than k, return false.

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

java

QUBITS OF DPK

1class Solution {
2    public boolean kLengthApart(int[] nums, int k) {
3        int lastOne = -1;
4        for (int i = 0; i < nums.length; i++) {
5            if (nums[i] == 1) {
6                if (lastOne != -1 && i - lastOne - 1 < k) return false;
7                lastOne = i;
8            }
9        }
10        return true;
11    }
12}

Dry Run

Input: nums = [1,0,0,0,1,0,0,1], k=2

Output: true

Key Tricks

i - lastOne - 1 = number of zeros between the two 1s
lastOne = -1 means no 1 seen yet — skip check

30-Second Interview Explanation

Track last 1's position. For each new 1, compute gap = i - lastOne - 1 (zeros between them). If gap < k, return false. Time O(n), Space O(1).

️ Interview Traps

Using i - lastOne instead of i - lastOne - 1 — that counts 1s themselves, not zeros between

Most Common Follow-ups

Q1: What if we want at least k 1s between any two 0s?

Same approach — swap roles of 0 and 1 in the code.

LC #724 — Find Pivot Index

(Core solution in Pattern 1 Easy — see that page)

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

java

QUBITS OF DPK

1class Solution {
2    public int pivotIndex(int[] nums) {
3        int total = 0;
4        for (int num : nums) total += num;
5        int leftSum = 0;
6        for (int i = 0; i < nums.length; i++) {
7            if (leftSum == total - leftSum - nums[i]) return i;
8            leftSum += nums[i];
9        }
10        return -1;
11    }
12}

Dry Run

Input: nums = [1,7,3,6,5,6], total=28

Output: 3

Key Tricks

rightSum = total - leftSum - nums[i] (derived, not computed)
Update leftSum AFTER check

30-Second Interview Explanation

rightSum = totalSum - leftSum - current. Derive rightSum on the fly. Time O(n), Space O(1).

️ Interview Traps

Updating leftSum before check includes current element incorrectly

Most Common Follow-ups

Q1: LC #1991 is identical — same code?

Yes — same problem different name. Same code submits on both.

Q2: Return all pivot indices?

Don't return early — collect all matching indices in ArrayList.