Cosmic Module

Qubits of DPK

March 15, 2026

Core DSA

1️⃣ LC #525 — Contiguous Array

Core Idea

Convert 0s to -1s. Equal 0s and 1s means prefix sum = 0 OR same prefix sum seen before. HashMap stores first occurrence of each prefix sum.

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

java

QUBITS OF DPK

1class Solution {
2    public int findMaxLength(int[] nums) {
3        HashMap<Integer, Integer> firstIndex = new HashMap<>();
4        firstIndex.put(0, -1);
5        int prefixSum = 0, maxLen = 0;
6        for (int i = 0; i < nums.length; i++) {
7            prefixSum += (nums[i] == 1) ? 1 : -1;
8            if (firstIndex.containsKey(prefixSum)) {
9                maxLen = Math.max(maxLen, i - firstIndex.get(prefixSum));
10            } else {
11                firstIndex.put(prefixSum, i);
12            }
13        }
14        return maxLen;
15    }
16}

Dry Run

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

Output: 6

Key Tricks

Convert 0→-1 so equal 0s and 1s make prefix sum = 0
Same prefix sum twice means subarray between them is balanced
Store FIRST occurrence only — maximizes length
put(0, -1) handles subarrays from index 0

30-Second Interview Explanation

Convert 0s to -1s. Balanced subarray = prefix sum appears again. Store first occurrence of each prefix sum. Length = current index - first occurrence index. Time O(n), Space O(n).

️ Interview Traps

Not converting 0 to -1 — can't use prefix sum trick otherwise
Not storing first occurrence — would get shorter subarrays

Most Common Follow-ups

Q1: What's the connection to Subarray Sum Equals K?

Identical pattern. Here k=0 (looking for prefix sum diff = 0 = same prefix sum seen twice). Subarray Sum K: looking for prefix sum diff = k. Same HashMap approach, different target.

2️⃣ LC #42 — Trapping Rain Water

Core Idea

Water at each index = min(maxLeft, maxRight) - height[i]. Precompute maxLeft and maxRight arrays.

Brute Force → O(n²): For each bar, scan left and right for max.

Prefix/Suffix → O(n) Time | O(n) Space:

java

QUBITS OF DPK

1class Solution {
2    public int trap(int[] height) {
3        int n = height.length;
4        int[] maxLeft = new int[n], maxRight = new int[n];
5        maxLeft[0] = height[0];
6        for (int i = 1; i < n; i++) maxLeft[i] = Math.max(maxLeft[i-1], height[i]);
7        maxRight[n-1] = height[n-1];
8        for (int i = n-2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i+1], height[i]);
9        int water = 0;
10        for (int i = 0; i < n; i++) water += Math.min(maxLeft[i], maxRight[i]) - height[i];
11        return water;
12    }
13}

Two Pointer O(1) Space:

java

QUBITS OF DPK

1class Solution {
2    public int trap(int[] height) {
3        int left = 0, right = height.length-1, water = 0;
4        int maxLeft = 0, maxRight = 0;
5        while (left < right) {
6            if (height[left] <= height[right]) {
7                if (height[left] >= maxLeft) maxLeft = height[left];
8                else water += maxLeft - height[left];
9                left++;
10            } else {
11                if (height[right] >= maxRight) maxRight = height[right];
12                else water += maxRight - height[right];
13                right--;
14            }
15        }
16        return water;
17    }
18}

Dry Run

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

maxLeft: [0,1,1,2,2,2,2,3,3,3,3,3]

maxRight: [3,3,3,3,3,3,3,3,2,2,2,1]

Total = 6

Key Tricks

Water at i = min(maxLeft[i], maxRight[i]) - height[i]
Two pointer approach reduces to O(1) space
The bottleneck is the shorter wall, not the taller one

30-Second Interview Explanation

Water at each bar = min(max height to left, max height to right) - current height. Precompute both in two passes. Sum water for all bars. Time O(n), Space O(n). Two-pointer approach achieves O(1) space.

️ Interview Traps

Using max to left/right including current element (same result but clearer to use inclusive)
Forgetting that water can't be negative — min - height is always >= 0 by construction

Most Common Follow-ups

Q1: Two-pointer approach — why is it correct?

The key insight: water at position i is determined by the SHORTER of its two boundaries. When we process from the left side (height[left] <= height[right]), we know maxRight >= height[right] >= height[left], so the limiting factor is the left side. We can safely compute water for the left position.

Q2: LC #11 — Container With Most Water (related)?

Different problem — maximize area between two lines. Two pointers but move the shorter pointer inward. No prefix/suffix needed. Area = min(height[l], height[r]) * (r - l).

3️⃣ LC #1248 — Count Number of Nice Subarrays

Core Idea

Convert odd numbers to 1, even to 0. Count subarrays with sum = k. Prefix sum + HashMap.

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

java

QUBITS OF DPK

1class Solution {
2    public int numberOfSubarrays(int[] nums, int k) {
3        HashMap<Integer, Integer> prefixCount = new HashMap<>();
4        prefixCount.put(0, 1);
5        int prefixSum = 0, count = 0;
6        for (int num : nums) {
7            prefixSum += (num % 2 == 1) ? 1 : 0;
8            count += prefixCount.getOrDefault(prefixSum - k, 0);
9            prefixCount.merge(prefixSum, 1, Integer::sum);
10        }
11        return count;
12    }
13}

Dry Run

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

Output: 2

Key Tricks

Reduce to Subarray Sum = K by treating odd as 1, even as 0
Identical code structure to LC #560

30-Second Interview Explanation

Convert odd→1, even→0. Problem reduces to Subarray Sum Equals K. Apply prefix sum HashMap. Time O(n), Space O(n).

️ Interview Traps

Not recognizing the reduction to LC #560

Most Common Follow-ups

Q1: How does this reduce to Subarray Sum = K?

A subarray with exactly k odd numbers has exactly k 1s in the converted array. Sum of converted array in that range = k. Exact same problem as LC #560 with the converted array.