Cosmic Module

Qubits of DPK

March 15, 2026

Core DSA

1️⃣ LC #76 — Minimum Window Substring

Core Idea

Sliding window with frequency maps. Expand right until all chars covered. Shrink left to minimize. Track valid state with formed counter.

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

java

QUBITS OF DPK

1class Solution {
2    public String minWindow(String s, String t) {
3        if (s.length() < t.length()) return "";
4        HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
5        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
6        int left = 0, formed = 0, required = need.size();
7        int[] ans = {-1, 0, 0}; // length, left, right
8        for (int right = 0; right < s.length(); right++) {
9            char c = s.charAt(right);
10            window.merge(c, 1, Integer::sum);
11            if (need.containsKey(c) && window.get(c).equals(need.get(c))) formed++;
12            while (formed == required && left <= right) {
13                if (ans[0] == -1 || right - left + 1 < ans[0]) {
14                    ans[0] = right - left + 1; ans[1] = left; ans[2] = right;
15                }
16                char lc = s.charAt(left);
17                window.merge(lc, -1, Integer::sum);
18                if (need.containsKey(lc) && window.get(lc) < need.get(lc)) formed--;
19                left++;
20            }
21        }
22        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2]+1);
23    }
24}

Dry Run

Input: s = "ADOBECODEBANC", t = "ABC"

need: {A:1, B:1, C:1}, required=3

Output: "BANC"

Key Tricks

formed counter tracks how many required chars have met their frequency — avoid scanning map each step
Use equals() for Integer comparison, not ==
Record answer inside shrink loop when window is still valid

30-Second Interview Explanation

Two HashMaps: need (from t) and window (current). Expand right until all t chars covered (formed == required). Shrink left to minimize while still valid. Record minimum window. Time O(n+m), Space O(n+m).

️ Interview Traps

Using == for Integer comparison — fails for values > 127 (Integer cache boundary)
Not tracking formed — would need O(|t|) check each step

Most Common Follow-ups

Q1: Why use formed counter instead of checking map equality each step?

Checking map equality is O(|t|) per step — makes total O(n*|t|). The formed counter tracks satisfied characters in O(1) per step. Increment when a char's window count first meets its need, decrement when it drops below. Checking formed == required is O(1).

2️⃣ LC #239 — Sliding Window Maximum

Core Idea

Monotonic deque stores indices of decreasing elements. Front always = max in current window.

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

java

QUBITS OF DPK

1class Solution {
2    public int[] maxSlidingWindow(int[] nums, int k) {
3        int n = nums.length;
4        int[] result = new int[n - k + 1];
5        Deque<Integer> deque = new ArrayDeque<>(); // stores indices
6        for (int i = 0; i < n; i++) {
7            // Remove elements outside window
8            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
9            // Remove smaller elements from back
10            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
11            deque.addLast(i);
12            if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
13        }
14        return result;
15    }
16}

Dry Run

Input: nums = [1,3,-1,-3,5,3,6,7], k=3

Output: [3,3,5,5,6,7]

Key Tricks

Deque stores INDICES not values — needed for out-of-window check
Remove from front when out of window
Remove from back when new element is larger — they can never be max
Front of deque = max of current window

30-Second Interview Explanation

Monotonic decreasing deque of indices. For each element: remove expired indices from front. Remove smaller elements from back (they'll never be max). Add current. Front = window max. Time O(n), Space O(k).

️ Interview Traps

Storing values instead of indices — can't check if element is out of window
Not removing out-of-window elements from front first

Most Common Follow-ups

Q1: Sliding Window Minimum?

Identical approach but maintain INCREASING deque. Remove from back when new element is SMALLER. Front = window minimum.

Q2: Why can we discard smaller elements when a larger element arrives?

If nums[i] > nums[j] where i > j, then j will leave the window before i. So whenever j is in the window, i is also in the window and is larger. j can NEVER be the maximum. Safe to discard permanently.