Cosmic Module

D

Qubits of DPK

March 12, 2026

Core DSA

1️⃣ LC #53 — Maximum Subarray (Kadane's Algorithm)

Core Idea

If running sum goes negative, discard it and start fresh. At each index: extend or restart.
Brute Force → O(n²) Time | O(1) Space:
Check every subarray.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int maxSubArray(int[] nums) {
2    int currentSum = nums[0];
3    int maxSum = nums[0];
4    for (int index = 1; index < nums.length; index++) {
5        currentSum = Math.max(nums[index], currentSum + nums[index]);
6        maxSum = Math.max(maxSum, currentSum);
7    }
8    return maxSum;
9}

Dry Run

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (subarray [4,-1,2,1])

Key Tricks

  • Math.max(nums[i], currentSum + nums[i]) — start fresh vs extend
  • Initialize with nums[0] not 0 — handles all-negative arrays
  • Invariant: currentSum = max subarray sum ending at index i

30-Second Interview Explanation

If running sum is negative it only hurts — discard and start fresh. At each index choose larger of starting new vs extending. Track global max. Kadane's. Time O(n), Space O(1).

️ Interview Traps

  • Initializing with 0 → wrong for all-negative arrays

Most Common Follow-ups

Q1: Return the actual subarray.
Track start, end, tempStart. When fresh start wins, update tempStart. When maxSum updates, save start = tempStart, end = i.
Q2: LC #918 — Maximum Sum Circular Subarray.
java
QUBITS OF DPK
1public int maxSubarraySumCircular(int[] nums) {
2    int totalSum = 0, currMax = 0, maxSum = nums[0], currMin = 0, minSum = nums[0];
3    for (int num : nums) {
4        currMax = Math.max(currMax + num, num); maxSum = Math.max(maxSum, currMax);
5        currMin = Math.min(currMin + num, num); minSum = Math.min(minSum, currMin);
6        totalSum += num;
7    }
8    return maxSum < 0 ? maxSum : Math.max(maxSum, totalSum - minSum);
9}
Q3: LC #152 — Maximum Product Subarray.
Track both currMax and currMin — negative flips them. 3 candidates each. Save tempMax before updating.

2️⃣ LC #121 — Best Time to Buy and Sell Stock

Core Idea

Max profit on any day = today's price - minimum price seen so far.
Brute Force → O(n²) Time | O(1) Space:
Check every pair (i, j) where i < j.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int maxProfit(int[] prices) {
2    int minPrice = prices[0];
3    int maxProfit = 0;
4    for (int day = 1; day < prices.length; day++) {
5        int profit = prices[day] - minPrice;
6        maxProfit = Math.max(maxProfit, profit);
7        minPrice = Math.min(minPrice, prices[day]);
8    }
9    return maxProfit;
10}

Dry Run

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

Key Tricks

  • Compute profit BEFORE updating minPrice
  • Initialize maxProfit = 0 — return 0 if no profit possible

30-Second Interview Explanation

Best profit today = today's price minus running minimum. Single pass. Time O(n), Space O(1).

️ Interview Traps

  • Updating minPrice before profit → buy and sell same day

Most Common Follow-ups

Q1: LC #122 — Unlimited transactions.
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]) totalProfit += prices[day] - prices[day - 1];
5    }
6    return totalProfit;
7}
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 #188 — At most k transactions.
DP with dp[k][n]. For k >= n/2 reduces to unlimited.

3️⃣ LC #169 — Majority Element (Boyer-Moore Voting)

Core Idea

Majority element appears > n/2 times — survives after cancelling all others.
Brute Force → O(n²) | Better O(n)/O(n) HashMap
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int majorityElement(int[] nums) {
2    int count = 0;
3    int candidate = 0;
4    for (int num : nums) {
5        if (count == 0) candidate = num;
6        if (num == candidate) count++;
7        else count--;
8    }
9    return candidate;
10}

Dry Run

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2

Key Tricks

  • When count hits 0 → pick new candidate
  • Works ONLY when majority is guaranteed (> n/2)

30-Second Interview Explanation

Boyer-Moore Voting. Match → increment, different → decrement, zero → new candidate. Majority always survives. Time O(n), Space O(1).

️ Interview Traps

  • Using when majority NOT guaranteed — need verification pass

Most Common Follow-ups

Q1: Majority not guaranteed — add verification pass.
After finding candidate, count its occurrences. Return it if count > n/2, else return -1.
Q2: LC #229 — Majority Element II (appears > n/3, maintain 2 candidates).
java
QUBITS OF DPK
1public List<Integer> majorityElement(int[] nums) {
2    int c1 = 0, c2 = 1, cnt1 = 0, cnt2 = 0;
3    for (int num : nums) {
4        if (num == c1) cnt1++;
5        else if (num == c2) cnt2++;
6        else if (cnt1 == 0) { c1 = num; cnt1 = 1; }
7        else if (cnt2 == 0) { c2 = num; cnt2 = 1; }
8        else { cnt1--; cnt2--; }
9    }
10    List<Integer> result = new ArrayList<>();
11    cnt1 = 0; cnt2 = 0;
12    for (int num : nums) { if (num == c1) cnt1++; else if (num == c2) cnt2++; }
13    if (cnt1 > nums.length / 3) result.add(c1);
14    if (cnt2 > nums.length / 3) result.add(c2);
15    return result;
16}

4️⃣ LC #665 — Non-decreasing Array

Core Idea

At most one modification. Greedily fix each violation in-place.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean checkPossibility(int[] nums) {
2    int violations = 0;
3    for (int index = 1; index < nums.length; index++) {
4        if (nums[index] < nums[index - 1]) {
5            violations++;
6            if (violations > 1) return false;
7            if (index >= 2 && nums[index] < nums[index - 2]) {
8                nums[index] = nums[index - 1];
9            } else {
10                nums[index - 1] = nums[index];
11            }
12        }
13    }
14    return true;
15}

Dry Run

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

Key Tricks

  • Prefer lowering left unless nums[index] < nums[index-2]
  • Modify in-place so future checks reflect the fix

30-Second Interview Explanation

Single pass counting violations. Greedily fix each — lower left if possible, else raise right. More than 1 → false. Time O(n), Space O(1).

️ Interview Traps

  • Not checking index >= 2 before accessing nums[index-2]

Most Common Follow-ups

Q1: At most k modifications?
Replace violations > 1 with violations > k. Same greedy fix logic.
Q2: Strictly increasing required?
Change violation condition from nums[index] < nums[index-1] to nums[index] <= nums[index-1].

5️⃣ LC #283 — Move Zeroes

Core Idea

insertPosition tracks where next non-zero goes. Compact non-zeros, fill zeros.
Brute Force → O(n²): For each zero, shift all subsequent elements.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public void moveZeroes(int[] nums) {
2    int insertPosition = 0;
3    for (int index = 0; index < nums.length; index++) {
4        if (nums[index] != 0) {
5            nums[insertPosition] = nums[index];
6            insertPosition++;
7        }
8    }
9    while (insertPosition < nums.length) {
10        nums[insertPosition] = 0;
11        insertPosition++;
12    }
13}

Dry Run

Input: nums = [0, 1, 0, 3, 12]
Pass 1 — compact non-zeros:
Pass 2 — fill zeros from insertPosition=3:
Output: [1, 3, 12, 0, 0]

Key Tricks

  • Two passes: compact non-zeros first, fill zeros second
  • Relative order of non-zero elements preserved

30-Second Interview Explanation

insertPosition tracks next non-zero slot. Compact non-zeros, then fill zeros. Time O(n), Space O(1).

️ Interview Traps

  • Not preserving relative order

Most Common Follow-ups

Q1: Move zeros to front?
Traverse right to left, insertPosition starts at n-1. Move non-zeros right, fill zeros left.
Q2: Minimize total writes?
Add if (insertPosition != index) check before assignment — skips unnecessary writes when element already in place.

6️⃣ GFG — Equilibrium Point

Core Idea

rightSum = totalSum - leftSum - current. Identical to LC #724.
Brute Force → O(n²) | Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int equilibriumPoint(int[] arr) {
2    int totalSum = 0;
3    for (int value : arr) totalSum += value;
4    int leftSum = 0;
5    for (int index = 0; index < arr.length; index++) {
6        int rightSum = totalSum - leftSum - arr[index];
7        if (leftSum == rightSum) return index;
8        leftSum += arr[index];
9    }
10    return -1;
11}

Dry Run

Input: arr = [1, 2, 0, 3], totalSum = 6
Output: 2

Key Tricks

  • rightSum = totalSum - leftSum - arr[index]
  • Update leftSum AFTER the check

30-Second Interview Explanation

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

️ Interview Traps

  • Updating leftSum before check

Most Common Follow-ups

Q1: Return all equilibrium points.
Replace return with result.add(index), don't return early. Continue to end.
Q2: No equilibrium exists?
Already handled — final return -1 covers this.

7️⃣ LC #152 — Maximum Product Subarray

Core Idea

Track both currMax and currMin — negative flips them. 3 candidates each.
Brute Force → O(n²) | Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int maxProduct(int[] nums) {
2    int currMax = 1, currMin = 1, maxProduct = nums[0];
3    for (int i = 0; i < nums.length; i++) {
4        int tempMax = currMax;
5        currMax = Math.max(tempMax * nums[i], Math.max(currMin * nums[i], nums[i]));
6        currMin = Math.min(tempMax * nums[i], Math.min(currMin * nums[i], nums[i]));
7        maxProduct = Math.max(maxProduct, currMax);
8    }
9    return maxProduct;
10}

Dry Run

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

Key Tricks

  • Save tempMax before updating — both currMax and currMin need old value
  • 3 candidates: extend max, flip min, start fresh
  • Initialize maxProduct with nums[0] not 0

30-Second Interview Explanation

Negative × negative = positive so min can flip to max. Track both at each index. Save tempMax to avoid overwrites. Time O(n), Space O(1).

️ Interview Traps

  • Forgetting tempMax → wrong results

Most Common Follow-ups

Q1: What if array contains zeros?
Handled automatically — multiplying by 0 makes both currMax and currMin = 0, then nums[i] fresh starts.
Q2: Return the actual subarray?
Track start/end/tempStart alongside currMax updates. Same O(n) time, more bookkeeping.

8️⃣ LC #845 — Longest Mountain in Array

Core Idea

Precompute increasing[i] and decreasing[i]. Valid peak where both > 0. Length = inc + dec + 1.
Brute Force → O(n²) | Optimized → O(n) Time | O(n) Space:
java
QUBITS OF DPK
1public int longestMountain(int[] arr) {
2    int n = arr.length;
3    int[] increasing = new int[n], decreasing = new int[n];
4    int mountainLength = 0;
5    for (int i = 1; i < n; i++)
6        if (arr[i] > arr[i-1]) increasing[i] = increasing[i-1] + 1;
7    for (int i = n-2; i >= 0; i--)
8        if (arr[i] > arr[i+1]) decreasing[i] = decreasing[i+1] + 1;
9    for (int i = 1; i < n-1; i++)
10        if (increasing[i] > 0 && decreasing[i] > 0)
11            mountainLength = Math.max(mountainLength, increasing[i] + decreasing[i] + 1);
12    return mountainLength;
13}

Dry Run

Input: arr = [2, 1, 4, 7, 3, 2, 5]
increasing array (left to right):
decreasing array (right to left):
Evaluation (i=1 to n-2):
Output: 5

Key Tricks

  • +1 in formula = the peak element itself
  • Both directions must be > 0 for valid peak

30-Second Interview Explanation

Precompute increasing run ending at i and decreasing run starting at i. At valid peaks (both > 0), mountain = inc + dec + 1. Time O(n), Space O(n).

️ Interview Traps

  • Forgetting +1 for peak element

Most Common Follow-ups

Q1: Can you do it in O(1) space?
Yes — expand from each valid peak using two pointers. Same O(n) time, eliminates the two extra arrays.
Q2: What defines a valid mountain?
Strictly increasing THEN strictly decreasing. Equal elements (plateaus) disqualify. Minimum 3 elements.

9️⃣ LC #674 — Longest Continuous Increasing Subsequence

Core Idea

Running streak length. Extend on increase, reset to 1 on break.
Brute Force → O(n²) | Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int findLengthOfLCIS(int[] nums) {
2    int maxLength = 1, currentLength = 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}

Dry Run

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

Key Tricks

  • Reset to 1 not 0 — current element starts new subarray
  • Initialize both with 1

30-Second Interview Explanation

Running streak of strictly increasing elements. Extend on increase, reset to 1 on break. Track global max. Time O(n), Space O(1).

️ Interview Traps

  • Resetting to 0 instead of 1

Most Common Follow-ups

Q1: Non-decreasing (allow equal)?
Change > to >=. Equal elements now extend the streak.
Q2: LC #300 — Longest Increasing Subsequence (not contiguous).
Classic DP: dp[i] = LIS ending at i. Check all j < i where nums[j] < nums[i]. O(n²). Optimized with patience sorting to O(n log n).

LC #2765 — Longest Alternating Subarray

Core Idea

Track expectedDiff alternating +1/-1. Special case: diff==1 starts new sequence of length 2.
Brute Force → O(n²) | Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int alternatingSubarray(int[] nums) {
2    int n = nums.length, maxLength = -1, currentLength = 1, expectedDiff = 1;
3    for (int i = 1; i < n; i++) {
4        int diff = nums[i] - nums[i-1];
5        if (diff == expectedDiff) { currentLength++; expectedDiff = -expectedDiff; }
6        else if (diff == 1) { currentLength = 2; expectedDiff = -1; }
7        else { currentLength = 1; expectedDiff = 1; }
8        maxLength = Math.max(maxLength, currentLength);
9    }
10    return maxLength;
11}

Dry Run

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

Key Tricks

  • expectedDiff flips sign every step
  • diff == 1 special case — new sequence starts (length 2, next expected = -1)
  • Update maxLength every iteration

30-Second Interview Explanation

Track expected diff alternating +1/-1. Extend on match, start new seq of 2 if diff==1, else reset. Update max every step. Time O(n), Space O(1).

️ Interview Traps

  • Missing diff == 1 special case

Most Common Follow-ups

Q1: Pattern could start with -1?
Run twice — once with expectedDiff=1, once with expectedDiff=-1. Return max of both results.
Q2: Return the actual subarray?
Track startIndex alongside currentLength. When special case or reset triggers, update startIndex. When maxLength updates, save bestStart.