Cosmic Module

D

Qubits of DPK

March 12, 2026

Core DSA

1️⃣ LC #1920 — Build Array from Permutation

Core Idea

Build a result array where result[i] = nums[nums[i]] — a direct index remapping in one pass.
Brute Force → O(n) Time | O(n) Space:
java
QUBITS OF DPK
1public int[] buildArray(int[] nums) {
2    int n = nums.length;
3    int[] result = new int[n];
4    for (int index = 0; index < n; index++) {
5        result[index] = nums[nums[index]];
6    }
7    return result;
8}
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int[] buildArray(int[] nums) {
2    int n = nums.length;
3    for (int index = 0; index < n; index++) {
4        nums[index] += (nums[nums[index]] % n) * n;
5    }
6    for (int index = 0; index < n; index++) {
7        nums[index] /= n;
8    }
9    return nums;
10}

Dry Run

Input: nums = [0, 2, 1, 5, 3, 4], n = 6
After encode: [0, 8, 13, 29, 33, 22]
Output: [0, 1, 2, 4, 5, 3]

Key Tricks

  • % n strips encoded upper half, gives original value
  • += ... * n stores new value in upper half, preserves old in lower half
  • Works because all values are guaranteed in range [0, n-1]

30-Second Interview Explanation

Direct index remapping — result[i] = nums[nums[i]]. O(n) space is trivial. For O(1) space, encode both old and new values using modulo arithmetic since values are bounded by n. First pass encodes, second pass extracts. Time O(n), Space O(1).

️ Interview Traps

  • Forgetting % n when reading during encoding → reads already-modified value
  • Confusing which pass does what

Most Common Follow-ups

Q1: Can you do it in O(1) space?
Yes — in-place encoding. Since values are in [0, n-1], encode new value in upper half: nums[i] += (nums[nums[i]] % n) * n. Then extract with /= n.
Q2: Why does % n work here?
When encoding index j = nums[i], nums[j] may already be partially encoded. Taking % n strips the upper half and gives back the original lower value.
Q3: What if values weren't bounded by n?
The O(1) trick breaks — can't safely encode two values without knowing the bound. Forced to use O(n) extra array.

2️⃣ LC #1480 — Running Sum of 1D Array

Core Idea

Each element becomes the sum of all elements up to that index. In-place accumulation.
Brute Force → O(n²) Time | O(1) Space:
For each index, sum all elements from 0 to i.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int[] runningSum(int[] nums) {
2    for (int index = 1; index < nums.length; index++) {
3        nums[index] = nums[index] + nums[index - 1];
4    }
5    return nums;
6}

Dry Run

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

Key Tricks

  • Modify in-place starting from index 1
  • No extra array needed — each element only depends on its predecessor

30-Second Interview Explanation

Running sum at index i equals running sum at i-1 plus current element. Modify in-place starting from index 1. Time O(n), Space O(1).

️ Interview Traps

  • Starting loop from 0 → overwrites index 0 unnecessarily

Most Common Follow-ups

Q1: Can you do it without modifying the input?
Allocate separate result array. Set result[0] = nums[0], then result[i] = result[i-1] + nums[i]. Time O(n), Space O(n).
Q2: How would you use this for range queries?
Build prefix array once. Range sum [l, r] = prefix[r] - prefix[l-1]. Each query O(1) after O(n) preprocessing. This is LC #303.

3️⃣ LC #2011 — Final Value After Operations

Core Idea

Scan operations once. contains("++") → increment, else decrement.
Brute Force = Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int finalValueAfterOperations(String[] operations) {
2    int value = 0;
3    for (String operation : operations) {
4        if (operation.contains("++")) {
5            value++;
6        } else {
7            value--;
8        }
9    }
10    return value;
11}

Dry Run

Input: operations = ["--X", "X++", "X++"]
Output: 1

Key Tricks

  • contains("++") handles both "X++" and "++X" in one check
  • Single variable, single pass

30-Second Interview Explanation

Single pass checking for "++" in each operation string. Time O(n * L), Space O(1).

️ Interview Traps

  • Checking charAt(1) specifically — breaks for "++X" format

Most Common Follow-ups

Q1: What if operations had more types like *= or /=?
Use switch-case or HashMap mapping each operation string to its effect. Scales cleanly to any number of operation types.

4️⃣ LC #2114 — Maximum Number of Words Found in Sentences

Core Idea

Word count = number of spaces + 1. Track maximum across all sentences.
Brute Force = Optimized → O(n * L) Time | O(1) Space:
java
QUBITS OF DPK
1public int mostWordsFound(String[] sentences) {
2    int maxWords = 0;
3    for (String sentence : sentences) {
4        int wordCount = 1;
5        for (int charIndex = 0; charIndex < sentence.length(); charIndex++) {
6            if (sentence.charAt(charIndex) == ' ') {
7                wordCount++;
8            }
9        }
10        maxWords = Math.max(maxWords, wordCount);
11    }
12    return maxWords;
13}

Dry Run

Input: sentences = ["alice and bob", "love leetcode", "i am a student"]
Output: 4

Key Tricks

  • Words = spaces + 1 (always at least 1 word)
  • Initialize wordCount to 1, not 0

30-Second Interview Explanation

Word count equals spaces plus one. For each sentence count spaces, add 1, track global max. Time O(n * L), Space O(1).

️ Interview Traps

  • Initializing wordCount to 0 → off by one

Most Common Follow-ups

Q1: What if sentences have multiple consecutive spaces?
Use sentence.trim().split("\\s+").length — splits on one or more whitespace. Handles leading/trailing spaces too.

5️⃣ LC #485 — Max Consecutive Ones

Core Idea

Running count of consecutive ones. Reset on zero. Track global max.
Brute Force → O(n²): For each index, count consecutive ones forward.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int findMaxConsecutiveOnes(int[] nums) {
2    int maxCount = 0;
3    int currentCount = 0;
4    for (int index = 0; index < nums.length; index++) {
5        if (nums[index] == 1) {
6            currentCount++;
7            maxCount = Math.max(maxCount, currentCount);
8        } else {
9            currentCount = 0;
10        }
11    }
12    return maxCount;
13}

Dry Run

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

Key Tricks

  • Reset counter to 0 on zero — not to 1
  • Update maxCount inside the if block

30-Second Interview Explanation

Running count of consecutive ones. Increment on 1, reset to 0 on 0. Track global max. Time O(n), Space O(1).

️ Interview Traps

  • Resetting to 1 instead of 0

Most Common Follow-ups

Q1: LC #487 — Flip at most one zero.
Sliding window. Track zero count. When zeroCount > 1, shrink from left.
Q2: LC #1004 — Flip at most k zeros.
java
QUBITS OF DPK
1public int longestOnes(int[] nums, int k) {
2    int left = 0, zeroCount = 0, maxLen = 0;
3    for (int right = 0; right < nums.length; right++) {
4        if (nums[right] == 0) zeroCount++;
5        while (zeroCount > k) {
6            if (nums[left] == 0) zeroCount--;
7            left++;
8        }
9        maxLen = Math.max(maxLen, right - left + 1);
10    }
11    return maxLen;
12}

6️⃣ LC #724 — Pivot Index

Core Idea

rightSum = totalSum - leftSum - current. No separate right pass needed.
Brute Force → O(n²): For each index, compute left and right sums by scanning.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int pivotIndex(int[] nums) {
2    int totalSum = 0;
3    for (int index = 0; index < nums.length; index++) {
4        totalSum += nums[index];
5    }
6    int leftSum = 0;
7    for (int index = 0; index < nums.length; index++) {
8        int rightSum = totalSum - leftSum - nums[index];
9        if (leftSum == rightSum) return index;
10        leftSum += nums[index];
11    }
12    return -1;
13}

Dry Run

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

Key Tricks

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

30-Second Interview Explanation

rightSum = totalSum - leftSum - current. Compute total first, then single pass deriving rightSum on the fly. Time O(n), Space O(1).

️ Interview Traps

  • Updating leftSum BEFORE the check → includes current element in leftSum

Most Common Follow-ups

Q1: What if multiple pivot indices exist?
Use ArrayList, add all matching indices, don't return early.
Q2: LC #1991 — Find the Middle Index.
Identical logic — same code works directly.

7️⃣ GFG — Largest Element

Core Idea

Initialize with first element. Single pass updating max.
Brute Force = Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int largestElement(int[] arr) {
2    int maxValue = arr[0];
3    for (int index = 1; index < arr.length; index++) {
4        if (arr[index] > maxValue) {
5            maxValue = arr[index];
6        }
7    }
8    return maxValue;
9}

Dry Run

Input: arr = [3, 1, 7, 2, 9, 4]
Output: 9

Key Tricks

  • Initialize with arr[0], not Integer.MIN_VALUE
  • Start loop from index 1

30-Second Interview Explanation

Initialize max with first element, single pass updating if current beats max. Time O(n), Space O(1).

️ Interview Traps

  • Initializing with 0 → fails for all-negative arrays

Most Common Follow-ups

Q1: Find second largest.
java
QUBITS OF DPK
1public int secondLargest(int[] arr) {
2    Integer largest = null, secondLargest = null;
3    for (int num : arr) {
4        if (largest == null || num > largest) { secondLargest = largest; largest = num; }
5        else if (num != largest && (secondLargest == null || num > secondLargest)) secondLargest = num;
6    }
7    return secondLargest == null ? -1 : secondLargest;
8}
Q2: Find k-th largest — min-heap of size 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).

8️⃣ GFG — Second Largest Element

Core Idea

Two variables: largest and secondLargest. Cascade on new max. Skip duplicates. Use null over sentinel.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int secondLargest(int[] arr) {
2    Integer largest = null, secondLargest = null;
3    for (int index = 0; index < arr.length; index++) {
4        if (largest == null || arr[index] > largest) {
5            secondLargest = largest;
6            largest = arr[index];
7        } else if (arr[index] != largest && (secondLargest == null || arr[index] > secondLargest)) {
8            secondLargest = arr[index];
9        }
10    }
11    return secondLargest == null ? -1 : secondLargest;
12}

Dry Run

Input: arr = [12, 35, 1, 10, 34, 1]
Output: 34

Key Tricks

  • Cascade: old largest becomes secondLargest before updating
  • Skip duplicates: arr[index] != largest
  • Use null over Integer.MIN_VALUE

30-Second Interview Explanation

Two variables. Cascade when new max found. Skip duplicates. Time O(n), Space O(1).

️ Interview Traps

  • Not skipping duplicates → [5,5,3] gives second = 5 instead of 3

Most Common Follow-ups

Q1: K-th largest without sorting?
Min-heap of size k. Time O(n log k), Space O(k). Heap always holds k largest seen so far.
Q2: What if all elements are the same?
Return -1 — secondLargest stays null since all elements equal largest. Null check at end handles correctly.

9️⃣ GFG — Leaders in an Array

Core Idea

Traverse right to left. Any element >= maxFromRight is a leader.
Brute Force → O(n²): For each element, scan all elements to its right.
Optimized → O(n) Time | O(n) Space:
java
QUBITS OF DPK
1public ArrayList<Integer> leaders(int[] arr) {
2    ArrayList<Integer> result = new ArrayList<>();
3    int n = arr.length;
4    int maxFromRight = arr[n - 1];
5    result.add(maxFromRight);
6    for (int index = n - 2; index >= 0; index--) {
7        if (arr[index] >= maxFromRight) {
8            maxFromRight = arr[index];
9            result.add(maxFromRight);
10        }
11    }
12    Collections.reverse(result);
13    return result;
14}

Dry Run

Input: arr = [16, 17, 4, 3, 5, 2]
Collected (reversed): [17, 5, 2]
Output: [17, 5, 2]

Key Tricks

  • Start from rightmost — always a leader
  • >= not > — equal to max from right is still a leader
  • Collect reversed, reverse at end

30-Second Interview Explanation

Right to left, maintaining maxFromRight. Any element >= max is a leader. Collect reversed, reverse at end. Time O(n), Space O(n).

️ Interview Traps

  • Using > instead of >=

Most Common Follow-ups

Q1: Print leaders in original order without reversing?
Use LinkedList with addFirst() — prepend keeps original order without reversing.
Q2: What if leader defined as strictly greater?
Change >= to >. Equal elements no longer qualify.

GFG — Check if Array Is Sorted

Core Idea

Single pass. If any element is smaller than predecessor — not sorted.
Brute Force = Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean isSorted(int[] arr) {
2    for (int index = 1; index < arr.length; index++) {
3        if (arr[index] < arr[index - 1]) return false;
4    }
5    return true;
6}

Dry Run

Input: arr = [1, 2, 1, 2, 1, 3]
Output: false

Key Tricks

  • < not <= — equal elements are fine
  • Early exit on first violation

30-Second Interview Explanation

Single pass from index 1. If any element smaller than predecessor, return false. Time O(n), Space O(1).

️ Interview Traps

  • Using <= → wrongly rejects arrays with duplicate values

Most Common Follow-ups

Q1: Check sorted descending?
java
QUBITS OF DPK
1for (int index = 1; index < arr.length; index++) {
2    if (arr[index] > arr[index - 1]) return false;
3}
4return true;
Q2: LC #896 — Monotonic Array.
java
QUBITS OF DPK
1public boolean isMonotonic(int[] nums) {
2    boolean increasing = true, decreasing = true;
3    for (int i = 1; i < nums.length; i++) {
4        if (nums[i] > nums[i-1]) decreasing = false;
5        if (nums[i] < nums[i-1]) increasing = false;
6    }
7    return increasing || decreasing;
8}