Cosmic Module

D

Qubits of DPK

March 12, 2026

Core DSA

1️⃣ LC #122 — Best Time to Buy and Sell Stock II

Core Idea

Unlimited transactions. Any multi-day gain = sum of daily increments. Capture every positive consecutive difference.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int maxProfit(int[] prices) {
2    int totalProfit = 0;
3    for (int day = 1; day < prices.length; day++) {
4        if (prices[day] > prices[day - 1])
5            totalProfit += prices[day] - prices[day - 1];
6    }
7    return totalProfit;
8}

Dry Run

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7

Key Tricks

  • Any upward move from day i to j = sum of daily increments
  • Greedy: grab every positive daily difference
  • No need to track buy/sell windows

30-Second Interview Explanation

With unlimited transactions, any multi-day gain = sum of daily increments. Greedily accumulate every positive consecutive difference. Time O(n), Space O(1).

️ Interview Traps

  • Thinking you need to track buy/sell days explicitly

Most Common Follow-ups

Q1: LC #121 — At most 1 transaction.
java
QUBITS OF DPK
1public int maxProfit(int[] prices) {
2    int minPrice = prices[0], maxProfit = 0;
3    for (int day = 1; day < prices.length; day++) {
4        maxProfit = Math.max(maxProfit, prices[day] - minPrice);
5        minPrice = Math.min(minPrice, prices[day]);
6    }
7    return maxProfit;
8}
Q2: LC #123 — At most 2 transactions.
java
QUBITS OF DPK
1public int maxProfit(int[] prices) {
2    int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
3    for (int price : prices) {
4        buy1 = Math.max(buy1, -price); sell1 = Math.max(sell1, buy1 + price);
5        buy2 = Math.max(buy2, sell1 - price); sell2 = Math.max(sell2, buy2 + price);
6    }
7    return sell2;
8}
Q3: LC #714 — With transaction fee.
Track hold and cash states. cash = max(cash, hold + price - fee), hold = max(hold, cash - price).

2️⃣ LC #918 — Maximum Sum Circular Subarray

Core Idea

Two cases: non-circular (Kadane's max) and circular (totalSum - minSubarray). Run both in one pass.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int maxSubarraySumCircular(int[] nums) {
2    int totalSum = 0, currentMax = 0, maxSum = nums[0], currentMin = 0, minSum = nums[0];
3    for (int index = 0; index < nums.length; index++) {
4        currentMax = Math.max(currentMax + nums[index], nums[index]);
5        maxSum = Math.max(maxSum, currentMax);
6        currentMin = Math.min(currentMin + nums[index], nums[index]);
7        minSum = Math.min(minSum, currentMin);
8        totalSum += nums[index];
9    }
10    return maxSum < 0 ? maxSum : Math.max(maxSum, totalSum - minSum);
11}

Dry Run

Input: nums = [5, -3, 5]
maxSum=7 ≥ 0 → return max(7, 7-(-3)) = max(7,10) = 10
Output: 10 (circular: [5, 5] wrapping around)

Key Tricks

  • Circular max = totalSum - minSubarraySum
  • Edge case: if all elements negative (maxSum < 0), return maxSum directly
  • Run Kadane's max and min simultaneously

30-Second Interview Explanation

Non-circular = Kadane's max. Circular = totalSum - Kadane's min. One pass. All-negative edge case → return maxSum. Time O(n), Space O(1).

️ Interview Traps

  • Forgetting all-negative edge case → returns 0

Most Common Follow-ups

Q1: Why does circular max = totalSum - minSubarray?
A circular subarray excludes a contiguous middle segment. To maximize included sum, minimize excluded middle. Excluded middle = minimum subarray. So circular max = totalSum - minSubarray.
Q2: Single element array?
maxSum and minSum both initialized to nums[0]. totalSum - minSum = 0. maxSum < 0 check returns nums[0] correctly.

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

Core Idea

result[i] = prefix product left × suffix product right. Store prefix in result, multiply suffix on the fly.
Brute Force → O(n²) | Better O(n)/O(n) with prefix+suffix arrays
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int[] productExceptSelf(int[] nums) {
2    int n = nums.length;
3    int[] result = new int[n];
4    result[0] = 1;
5    for (int index = 1; index < n; index++)
6        result[index] = result[index - 1] * nums[index - 1];
7    int suffixProduct = 1;
8    for (int index = n - 1; index >= 0; index--) {
9        result[index] = result[index] * suffixProduct;
10        suffixProduct *= nums[index];
11    }
12    return result;
13}

Dry Run

Input: nums = [1, 2, 3, 4]
Left pass (prefix into result):
result = [1, 1, 2, 6], suffixProduct = 1
Right pass (multiply suffix):
Output: [24, 12, 8, 6]

Key Tricks

  • Left pass fills prefix into result — no extra array
  • Right pass uses single suffixProduct variable
  • Division is not allowed and breaks for zeros

30-Second Interview Explanation

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

️ Interview Traps

  • Using division → breaks for arrays containing zeros

Most Common Follow-ups

Q1: What if array contains zeros?
Division approach breaks (divide by zero). Prefix/suffix approach handles naturally — zero in prefix or suffix contributes 0 correctly with no special cases.
Q2: Two zeros in input?
All results become 0 except potentially at zero positions. Prefix/suffix handles this automatically.

4️⃣ LC #414 — Third Maximum Number

Core Idea

Maintain three distinct maximums. Cascade on new max. Skip duplicates. Use null over sentinel.
Brute Force → O(n log n): Sort, find third distinct.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int thirdMax(int[] nums) {
2    Integer firstMax = null, secondMax = null, thirdMax = null;
3    for (int num : nums) {
4        if ((firstMax != null && num == firstMax) ||
5            (secondMax != null && num == secondMax) ||
6            (thirdMax != null && num == thirdMax)) continue;
7        if (firstMax == null || num > firstMax) {
8            thirdMax = secondMax; secondMax = firstMax; firstMax = num;
9        } else if (secondMax == null || num > secondMax) {
10            thirdMax = secondMax; secondMax = num;
11        } else if (thirdMax == null || num > thirdMax) {
12            thirdMax = num;
13        }
14    }
15    return thirdMax == null ? firstMax : thirdMax;
16}

Dry Run

Input: nums = [3, 2, 1]
thirdMax = 1 (not null) → Output: 1
Input: nums = [1, 2]
thirdMax = null → return firstMax = 2

Key Tricks

  • Use null over Long.MIN_VALUE — sentinel fails for Integer.MIN_VALUE input
  • Skip duplicates BEFORE comparison
  • Cascade: push first→second→third before updating

30-Second Interview Explanation

Maintain three distinct running maximums. Skip duplicates. Cascade on each update. null = not yet assigned. Return thirdMax if exists else firstMax. Time O(n), Space O(1).

️ Interview Traps

  • Using Long.MIN_VALUE sentinel → fails if Integer.MIN_VALUE is actual input

Most Common Follow-ups

Q1: K-th maximum for arbitrary k?
java
QUBITS OF DPK
1public int findKthLargest(int[] nums, int k) {
2    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
3    for (int num : nums) {
4        minHeap.offer(num);
5        if (minHeap.size() > k) minHeap.poll();
6    }
7    return minHeap.peek();
8}
Time O(n log k), Space O(k). Heap always holds k largest — top is k-th largest.
Q2: Fewer than 3 distinct elements?
Already handled — thirdMax stays null, return firstMax.

5️⃣ LC #1014 — Best Sightseeing Pair

Core Idea

Score(i,j) = (values[i] + i) + (values[j] - j). Fix j, maximize left contribution with running max.
Brute Force → O(n²) | Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int maxScoreSightseeingPair(int[] values) {
2    int maxLeftScore = values[0] + 0;
3    int bestScore = 0;
4    for (int rightIndex = 1; rightIndex < values.length; rightIndex++) {
5        int rightScore = values[rightIndex] - rightIndex;
6        bestScore = Math.max(bestScore, maxLeftScore + rightScore);
7        int leftScore = values[rightIndex] + rightIndex;
8        maxLeftScore = Math.max(maxLeftScore, leftScore);
9    }
10    return bestScore;
11}

Dry Run

Input: values = [8, 1, 5, 2, 6]
Output: 11 (pair i=0, j=2: 8+5+0-2=11)

Key Tricks

  • Formula split: (values[i]+i) + (values[j]-j)
  • Update bestScore BEFORE maxLeftScore — i must be strictly < j
  • Same pattern as LC #121

30-Second Interview Explanation

Split score into left and right contributions. Maintain running maxLeftScore. Compute candidate at each j, update maxLeftScore after. Time O(n), Space O(1).

️ Interview Traps

  • Updating maxLeftScore before bestScore → j can equal i (invalid)

Most Common Follow-ups

Q1: Why update bestScore before maxLeftScore?
Must ensure i < j. If we update maxLeftScore first with current index, then when computing bestScore we'd be pairing position j with itself — invalid. Update bestScore first, guaranteeing only positions 0 to j-1 are in maxLeftScore.
Q2: Similar pattern in which problems?
LC #121 (minPrice = running best of -prices[i]), LC #123 two-transaction DP. All share: maintain running best of transformed left, compute answer using current right.

6️⃣ LC #1566 — Detect Pattern of Length M Repeated K or More Times

Core Idea

If pattern repeats, arr[i] == arr[i+m] for m*(k-1) consecutive positions.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean containsPattern(int[] arr, int m, int k) {
2    int matchCount = 0;
3    for (int index = 0; index < arr.length - m; index++) {
4        if (arr[index] == arr[index + m]) {
5            matchCount++;
6            if (matchCount == m * (k - 1)) return true;
7        } else {
8            matchCount = 0;
9        }
10    }
11    return false;
12}

Dry Run

Input: arr = [1,2,4,4,4,4], m=1, k=3 → target = 1*(3-1) = 2
Output: true

Key Tricks

  • Formula m*(k-1): k repetitions = k-1 transitions, each needing m matches
  • Loop boundary arr.length - m prevents out of bounds
  • Reset matchCount on ANY mismatch

30-Second Interview Explanation

If pattern of length m repeats k times, elements spaced m apart match for m*(k-1) consecutive positions. Count matches, reset on mismatch. Time O(n), Space O(1).

️ Interview Traps

  • Wrong loop boundary — arr.length - m - 1 misses last valid index
  • Not resetting on mismatch

Most Common Follow-ups

Q1: Derive m*(k-1) formula from scratch.
k=2, m=2: pattern [a,b] twice = [a,b,a,b] → 2 matches = 2(2-1)=2. k=3, m=2: [a,b,a,b,a,b] → 4 matches = 2(3-1)=4. Each additional repetition adds exactly m more matches.
Q2: What if k=1?
Target = m*(1-1) = 0. Any array with n >= m qualifies since a single occurrence counts. Handle as special case: if (k == 1) return arr.length >= m.

7️⃣ LC #896 — Monotonic Array

Core Idea

Two boolean flags. Invalidate each on violation. Return increasing || decreasing.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean isMonotonic(int[] nums) {
2    boolean increasing = true, decreasing = true;
3    for (int index = 1; index < nums.length; index++) {
4        if (nums[index] > nums[index - 1]) decreasing = false;
5        if (nums[index] < nums[index - 1]) increasing = false;
6    }
7    return increasing || decreasing;
8}

Dry Run

Input: nums = [1, 2, 2, 3]
increasing=true → Output: true
Input: nums = [1, 3, 2]
increasing=false, decreasing=false → Output: false

Key Tricks

  • Two flags start true — assume both valid until proven otherwise
  • Equal elements invalidate neither flag
  • Single pass

30-Second Interview Explanation

Two flags: isIncreasing and isDecreasing. Invalidate on violation. Equal elements affect neither. Return true if at least one survives. Time O(n), Space O(1).

️ Interview Traps

  • Equal elements incorrectly invalidating a flag

Most Common Follow-ups

Q1: Strictly monotonic (no equal elements)?
java
QUBITS OF DPK
1if (nums[index] >= nums[index-1]) decreasing = false;
2if (nums[index] <= nums[index-1]) increasing = false;
Equal elements now invalidate both flags.
Q2: Count elements to remove to make monotonic?
Find Longest Non-Decreasing/Non-Increasing Subsequence (LIS variant). Answer = n - max(longestNonDecreasing, longestNonIncreasing). Time O(n log n).

8️⃣ LC #1752 — Check if Array Is Sorted and Rotated

Core Idea

Sorted rotated array has at most one drop. Use % n for circular comparison.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean check(int[] nums) {
2    int dropCount = 0;
3    int n = nums.length;
4    for (int index = 0; index < n; index++) {
5        if (nums[index] > nums[(index + 1) % n]) dropCount++;
6    }
7    return dropCount <= 1;
8}

Dry Run

Input: nums = [3, 4, 5, 1, 2]
dropCount=1 ≤ 1 → Output: true
Input: nums = [2, 1, 3, 4]
dropCount=2 > 1 → Output: false

Key Tricks

  • (index + 1) % n handles last→first wrap circular comparison
  • 0 drops = already sorted, 1 drop = rotated, 2+ = invalid

30-Second Interview Explanation

Sorted rotated array has exactly one break point. Count drops circularly using % n. At most 1 → valid. Time O(n), Space O(1).

️ Interview Traps

  • Not doing circular comparison → misses wrap-around drop

Most Common Follow-ups

Q1: Find the rotation point.
java
QUBITS OF DPK
1public int findRotationPoint(int[] nums) {
2    int n = nums.length;
3    for (int index = 0; index < n; index++) {
4        if (nums[index] > nums[(index + 1) % n]) return (index + 1) % n;
5    }
6    return 0;
7}
Rotation point = index after the single drop.
Q2: What if duplicates exist?
Simple drop-count approach breaks. Example: [1,1,1,0,1] has one drop but isn't a valid sorted rotation. Needs additional checks — similar to LC #81.

9️⃣ LC #1800 — Maximum Ascending Subarray Sum

Core Idea

Running sum. Extend on strict increase, reset to current element on break.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int maxAscendingSum(int[] nums) {
2    int currentSum = nums[0], maxSum = nums[0];
3    for (int index = 1; index < nums.length; index++) {
4        if (nums[index] > nums[index - 1]) currentSum += nums[index];
5        else currentSum = nums[index];
6        maxSum = Math.max(maxSum, currentSum);
7    }
8    return maxSum;
9}

Dry Run

Input: nums = [10, 20, 30, 5, 10, 50]
Output: 65

Key Tricks

  • Reset to nums[index] not 0 — current element starts new subarray
  • Initialize with nums[0]
  • Update maxSum every iteration

30-Second Interview Explanation

Running sum of ascending subarray. Extend on strict increase, reset to current on break. Track global max. Time O(n), Space O(1).

️ Interview Traps

  • Resetting to 0 → misses single-element subarrays

Most Common Follow-ups

Q1: Maximum ascending subarray length?
java
QUBITS OF DPK
1public int maxAscendingLength(int[] nums) {
2    int currentLength = 1, maxLength = 1;
3    for (int index = 1; index < nums.length; index++) {
4        if (nums[index] > nums[index-1]) currentLength++;
5        else currentLength = 1;
6        maxLength = Math.max(maxLength, currentLength);
7    }
8    return maxLength;
9}
Q2: Allow equal elements (non-decreasing)?
Change > to >=. Equal elements extend instead of breaking.

LC #2012 — Sum of Beauty in the Array

Core Idea

Precompute leftMax[i] and rightMin[i] (excluding self). Check beauty-2 then beauty-1.
Brute Force → O(n²) | Optimized → O(n) Time | O(n) Space:
java
QUBITS OF DPK
1public int sumOfBeauties(int[] nums) {
2    int n = nums.length;
3    int[] leftMax = new int[n], rightMin = new int[n];
4    leftMax[0] = nums[0];
5    for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i-1], nums[i-1]);
6    rightMin[n-1] = nums[n-1];
7    for (int i = n-2; i >= 0; i--) rightMin[i] = Math.min(rightMin[i+1], nums[i+1]);
8    int beautyScore = 0;
9    for (int i = 1; i < n-1; i++) {
10        if (nums[i] > leftMax[i] && nums[i] < rightMin[i]) beautyScore += 2;
11        else if (nums[i] > nums[i-1] && nums[i] < nums[i+1]) beautyScore += 1;
12    }
13    return beautyScore;
14}

Dry Run

Input: nums = [1, 2, 3]
leftMax (max of elements strictly LEFT of i):
rightMin (min of elements strictly RIGHT of i):
Evaluation (i=1 only, since n=3):
Output: 2

Key Tricks

  • leftMax[i] = max of elements strictly LEFT (not including i itself)
  • rightMin[i] = min of elements strictly RIGHT (not including i itself)
  • Check beauty-2 first, beauty-1 only in else

30-Second Interview Explanation

Precompute prefix max and suffix min excluding self. Check beauty-2 (beats all) then beauty-1 (beats neighbors). Sum all scores. Time O(n), Space O(n).

️ Interview Traps

  • Including self in leftMax or rightMin → wrong evaluation

Most Common Follow-ups

Q1: Can you do it in O(1) space?
No — both leftMax and rightMin arrays are needed simultaneously during evaluation. They're built in opposite directions. O(n) space is the true lower bound.
Q2: What if beauty had more levels?
Add more precomputed arrays per condition level. For very complex conditions, consider a segment tree for range min/max queries in O(log n) each.