Cosmic Module

D

Qubits of DPK

March 15, 2026

Core DSA

1️⃣ LC #125 — Valid Palindrome

Core Idea

Two pointers from both ends. Skip non-alphanumeric. Compare lowercase. Move inward.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public boolean isPalindrome(String s) {
3        int left = 0, right = s.length() - 1;
4        while (left < right) {
5            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
6            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
7            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
8            left++; right--;
9        }
10        return true;
11    }
12}

Dry Run

Input: s = "A man, a plan, a canal: Panama"
Output: true

Key Tricks

  • Character.isLetterOrDigit() — handles all punctuation/spaces
  • Character.toLowerCase() — case-insensitive comparison
  • Skip non-alphanumeric BEFORE comparing

30-Second Interview Explanation

Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase versions. Move inward. Mismatch → false. Time O(n), Space O(1).

️ Interview Traps

  • Not skipping non-alphanumeric before comparing
  • Case-sensitive comparison

Most Common Follow-ups

Q1: LC #680 — Valid Palindrome II (at most one deletion)?
Two pointers. On mismatch, try skipping left char OR right char. If either remaining substring is palindrome, return true.
java
QUBITS OF DPK
1public boolean validPalindrome(String s) {
2    int l = 0, r = s.length()-1;
3    while (l < r) {
4        if (s.charAt(l) != s.charAt(r)) return isPalin(s,l+1,r) || isPalin(s,l,r-1);
5        l++; r--;
6    }
7    return true;
8}
9private boolean isPalin(String s, int l, int r) {
10    while (l < r) { if (s.charAt(l++) != s.charAt(r--)) return false; } return true;
11}

2️⃣ LC #167 — Two Sum II (Sorted Array)

Core Idea

Sorted array: left pointer from start, right from end. Sum too small → move left right. Sum too large → move right left.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public int[] twoSum(int[] numbers, int target) {
3        int left = 0, right = numbers.length - 1;
4        while (left < right) {
5            int sum = numbers[left] + numbers[right];
6            if (sum == target) return new int[]{left+1, right+1};
7            else if (sum < target) left++;
8            else right--;
9        }
10        return new int[]{-1, -1};
11    }
12}

Dry Run

Input: numbers = [2,7,11,15], target=9
Output: [1, 2] (1-indexed)

Key Tricks

  • Sorted array is the key — enables two pointer
  • Too small → left++, too large → right--
  • Problem guarantees exactly one solution

30-Second Interview Explanation

Sorted array enables two pointers. Sum too small → increase left. Sum too large → decrease right. Time O(n), Space O(1).

️ Interview Traps

  • 1-indexed output (add +1 to both indices)

Most Common Follow-ups

Q1: Unsorted array — which approach?
HashMap approach (LC #1 Two Sum): O(n) time, O(n) space. Can't use two pointers without sorting.
Q2: Three Sum (LC #15)?
Sort array. Fix one element, use two pointers on the rest. Skip duplicates at each level. O(n²) time.

3️⃣ LC #26 — Remove Duplicates from Sorted Array

Core Idea

Two pointers: slow tracks unique position, fast scans for new unique values.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public int removeDuplicates(int[] nums) {
3        int slow = 1;
4        for (int fast = 1; fast < nums.length; fast++) {
5            if (nums[fast] != nums[fast-1]) {
6                nums[slow++] = nums[fast];
7            }
8        }
9        return slow;
10    }
11}

Dry Run

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

Key Tricks

  • Sorted array: duplicates are always adjacent
  • Compare fast with fast-1 (not with slow-1) — both work but fast-1 is cleaner
  • slow starts at 1 (index 0 is always kept)

30-Second Interview Explanation

Two pointers. Slow tracks next unique position. Fast scans array. When new unique found, write to slow and advance. Time O(n), Space O(1).

️ Interview Traps

  • Starting slow at 0 — off by one, first element written twice

Most Common Follow-ups

Q1: LC #80 — Remove Duplicates II (allow at most 2)?
Same approach, but allow up to 2 copies: check nums[fast] != nums[slow-2] instead of != nums[slow-1].

4️⃣ LC #88 — Merge Sorted Array

Core Idea

Merge from the back to avoid overwriting. Three pointers: p1 at end of nums1, p2 at end of nums2, p at end of total.
Optimized → O(m+n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public void merge(int[] nums1, int m, int[] nums2, int n) {
3        int p1 = m-1, p2 = n-1, p = m+n-1;
4        while (p1 >= 0 && p2 >= 0) {
5            if (nums1[p1] >= nums2[p2]) nums1[p--] = nums1[p1--];
6            else nums1[p--] = nums2[p2--];
7        }
8        while (p2 >= 0) nums1[p--] = nums2[p2--];
9    }
10}

Dry Run

Input: nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3
Output: [1,2,2,3,5,6]

Key Tricks

  • Merge from BACK — avoids overwriting unprocessed nums1 elements
  • No need to handle remaining p1 elements — already in place
  • Only need to handle remaining p2 elements

30-Second Interview Explanation

Merge from back using three pointers. Compare largest unmerged elements, write larger to back. Remaining p2 elements copied if p1 exhausted first. Time O(m+n), Space O(1).

️ Interview Traps

  • Merging from front — overwrites unprocessed elements
  • Handling remaining p1 unnecessarily — they're already in correct positions

Most Common Follow-ups

Q1: Merge k sorted arrays?
Use min-heap of size k. Insert first element of each array. Poll min, add to result, push next element from that array. O(n log k) time.

5️⃣ LC #392 — Is Subsequence

Core Idea

Two pointers: pointer on s advances only when character matches t.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public boolean isSubsequence(String s, String t) {
3        int sPointer = 0;
4        for (int tPointer = 0; tPointer < t.length() && sPointer < s.length(); tPointer++) {
5            if (s.charAt(sPointer) == t.charAt(tPointer)) sPointer++;
6        }
7        return sPointer == s.length();
8    }
9}

Dry Run

Input: s = "abc", t = "ahbgdc"
sPointer == s.length() (3==3) → Output: true

Key Tricks

  • s pointer advances only on match
  • t pointer always advances
  • Return sPointer == s.length() — all of s was matched

30-Second Interview Explanation

Two pointers on s and t. Advance s pointer only on match, t pointer always. If s pointer reaches end, s is subsequence. Time O(n), Space O(1).

️ Interview Traps

  • Confusing subsequence with substring — subsequence allows gaps, substring doesn't

Most Common Follow-ups

Q1: What if there are many queries (many s strings against one t)?
Preprocess t: for each character, store sorted list of indices. For each query s, use binary search to find next occurrence. O(n + q |s| log n).

6️⃣ LC #344 — Reverse String

Core Idea

Two pointers from both ends. Swap and move inward.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public void reverseString(char[] s) {
3        int left = 0, right = s.length - 1;
4        while (left < right) {
5            char temp = s[left];
6            s[left++] = s[right];
7            s[right--] = temp;
8        }
9    }
10}

Dry Run

Input: s = ['h','e','l','l','o']
Output: ['o','l','l','e','h']

Key Tricks

  • In-place swap — no extra space
  • Loop ends when left >= right (middle element needs no swap)

30-Second Interview Explanation

Two pointers from both ends. Swap, move inward. Stop when they meet. Time O(n), Space O(1).

️ Interview Traps

  • Using extra array — violates in-place constraint

Most Common Follow-ups

Q1: Reverse words in a string (LC #151)?
Trim extra spaces, split by spaces, reverse the word array, join. Or: reverse entire string then reverse each word individually.

7️⃣ LC #905 — Sort Array By Parity

Core Idea

Two pointers from both ends. Move evens to front, odds to back.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public int[] sortArrayByParity(int[] nums) {
3        int left = 0, right = nums.length - 1;
4        while (left < right) {
5            if (nums[left] % 2 != 0 && nums[right] % 2 == 0) {
6                int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp;
7            }
8            if (nums[left] % 2 == 0) left++;
9            if (nums[right] % 2 != 0) right--;
10        }
11        return nums;
12    }
13}

Dry Run

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

Key Tricks

  • Swap only when left is odd AND right is even
  • Advance pointers independently based on their values

30-Second Interview Explanation

Two pointers from ends. When left is odd and right is even, swap. Advance left if even, advance right if odd. Time O(n), Space O(1).

️ Interview Traps

  • Advancing both pointers only after swap — should advance independently

Most Common Follow-ups

Q1: Dutch National Flag (LC #75 — Sort Colors)?
Three-way partition. Three pointers: low, mid, high. 0s before low, 2s after high, 1s between. Swap based on nums[mid].

8️⃣ LC #11 — Container With Most Water

Core Idea

Two pointers from ends. Area = min(h[l], h[r]) * (r - l). Always move the shorter pointer inward.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public int maxArea(int[] height) {
3        int left = 0, right = height.length - 1, maxWater = 0;
4        while (left < right) {
5            int water = Math.min(height[left], height[right]) * (right - left);
6            maxWater = Math.max(maxWater, water);
7            if (height[left] <= height[right]) left++;
8            else right--;
9        }
10        return maxWater;
11    }
12}

Dry Run

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Key Tricks

  • Move shorter pointer — only chance to increase area is taller wall
  • Area = min(heights) * width, so shorter wall is the bottleneck

30-Second Interview Explanation

Two pointers from ends. Area limited by shorter wall. Move shorter pointer inward — only way to potentially find larger area. Track max. Time O(n), Space O(1).

️ Interview Traps

  • Moving the taller pointer — can never improve current area limit

Most Common Follow-ups

Q1: Why move shorter pointer?
Current area is min(h[l], h[r]) * width. Moving taller pointer only decreases width AND the min is still bounded by shorter wall — can only decrease or stay same. Moving shorter gives a chance for higher min on the new position, potentially increasing area.

9️⃣ LC #643 — Maximum Average Subarray I

Core Idea

Fixed window of size k. Slide right, add new element, remove leftmost. Track max sum.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public double findMaxAverage(int[] nums, int k) {
3        int windowSum = 0;
4        for (int i = 0; i < k; i++) windowSum += nums[i];
5        int maxSum = windowSum;
6        for (int i = k; i < nums.length; i++) {
7            windowSum += nums[i] - nums[i - k];
8            maxSum = Math.max(maxSum, windowSum);
9        }
10        return (double) maxSum / k;
11    }
12}

Dry Run

Input: nums = [1,12,-5,-6,50,3], k=4
First window: 1+12+(-5)+(-6) = 2
Output: 51/4 = 12.75

Key Tricks

  • Fixed window: windowSum += nums[i] - nums[i-k]
  • Initialize first window separately
  • Track max sum, divide by k at end

30-Second Interview Explanation

Fixed window of size k. Slide: add rightmost, remove leftmost. Track max sum. Divide by k at end. Time O(n), Space O(1).

️ Interview Traps

  • Computing average inside loop — floating point rounding; better to track max sum

Most Common Follow-ups

Q1: Variable window — maximum average subarray of at least k elements (LC #644)?
Binary search on the answer + prefix sum check. O(n log(max-min)).

LC #1984 — Minimum Difference Between Highest and Lowest of K Scores

Core Idea

Sort array. Minimum difference of any k elements = minimum of (nums[i+k-1] - nums[i]) over all valid windows.
Optimized → O(n log n) Time | O(1) Space:
java
QUBITS OF DPK
1class Solution {
2    public int minimumDifference(int[] nums, int k) {
3        Arrays.sort(nums);
4        int minDiff = Integer.MAX_VALUE;
5        for (int i = 0; i <= nums.length - k; i++)
6            minDiff = Math.min(minDiff, nums[i + k - 1] - nums[i]);
7        return minDiff;
8    }
9}

Dry Run

Input: nums = [90,10,80,20,30], k=3 → sorted: [10,20,30,80,90]
Output: 20

Key Tricks

  • After sorting, minimum spread of k elements is always a contiguous window
  • Fixed window of size k on sorted array

30-Second Interview Explanation

Sort array. Minimum range of k elements is always a sorted contiguous window. Scan all windows of size k, track min difference. Time O(n log n), Space O(1).

️ Interview Traps

  • Not realizing that optimal k elements are always contiguous after sorting

Most Common Follow-ups

Q1: Why are optimal k elements always contiguous after sorting?
If you pick non-contiguous elements, you can always find a better (or equal) set by replacing the outlier with an element between the two. Sorting groups similar values together, so the tightest spread is always a contiguous block.