Cosmic Module

D

Qubits of DPK

March 12, 2026

Core DSA

1️⃣ LC #1 — Two Sum

Core Idea

For each element, check if complement (target - current) exists in HashMap. Check BEFORE putting — prevents self-match.
Brute Force → O(n²) Time | O(1) Space:
java
QUBITS OF DPK
1public int[] twoSum(int[] nums, int target) {
2    for (int i = 0; i < nums.length; i++)
3        for (int j = i + 1; j < nums.length; j++)
4            if (nums[i] + nums[j] == target) return new int[]{i, j};
5    return new int[]{};
6}
Optimized → O(n) Time | O(n) Space:
java
QUBITS OF DPK
1public int[] twoSum(int[] nums, int target) {
2    HashMap<Integer, Integer> map = new HashMap<>();
3    for (int index = 0; index < nums.length; index++) {
4        int complement = target - nums[index];
5        if (map.containsKey(complement)) {
6	        return new int[]{map.get(complement), index};
7	      }  
8        map.put(nums[index], index); //value to index mapping 
9    }
10    return new int[]{};
11}

Dry Run

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Trap case: nums = [3, 3], target = 6
Output: [0, 1] (check-before-put prevents self-match)

Key Tricks

  • Check BEFORE put — prevents using same element twice
  • Map stores value → index (not index → value)
  • One pass is sufficient

30-Second Interview Explanation

For each element compute complement = target - current. If complement in map, found our pair. Check before put prevents self-matching. Time O(n), Space O(n).

️ Interview Traps

  • Putting before checking → self-match bug for target = 2 * nums[i]
  • Returning values instead of indices

Most Common Follow-ups

Q1: Sorted array — O(1) space?
java
QUBITS OF DPK
1public int[] twoSumSorted(int[] nums, int target) {
2    int left = 0, right = nums.length - 1;
3    while (left < right) {
4        int sum = nums[left] + nums[right];
5        if (sum == target) return new int[]{left, right};
6        else if (sum < target) left++;
7        else right--;
8    }
9    return new int[]{};
10}
Time O(n), Space O(1).
Q2: Return all pairs.
Don't return on first match — collect in ArrayList. Continue iterating. Handle duplicates with careful overwriting.
Q3: Three Sum (LC #15)?
Sort array. Fix one element, use two pointers on remaining subarray to find pairs summing to -nums[i]. Skip duplicates at each level. Time O(n²), Space O(1) extra.

2️⃣ LC #217 — Contains Duplicate

Core Idea

HashSet — check contains before add. Return true on first duplicate.
Brute Force → O(n²) | Optimized → O(n) Time | O(n) Space:
java
QUBITS OF DPK
1public boolean containsDuplicate(int[] nums) {
2    HashSet<Integer> seen = new HashSet<>();
3    for (int num : nums) {
4        if (seen.contains(num)) return true;
5        seen.add(num);
6    }
7    return false;
8}

Dry Run

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

Key Tricks

  • HashSet not HashMap — only need existence
  • Check before add — catches duplicate on second occurrence
  • Early return on first duplicate

30-Second Interview Explanation

HashSet tracking seen elements. Check contains before add. Return true on first duplicate. Time O(n), Space O(n).

️ Interview Traps

  • Using HashMap unnecessarily

Most Common Follow-ups

Q1: LC #219 — Duplicate within k distance.
java
QUBITS OF DPK
1public boolean containsNearbyDuplicate(int[] nums, int k) {
2    HashSet<Integer> window = new HashSet<>();
3    for (int i = 0; i < nums.length; i++) {
4        if (window.contains(nums[i])) return true;
5        window.add(nums[i]);
6        if (window.size() > k) window.remove(nums[i - k]);
7    }
8    return false;
9}
Sliding window HashSet of size k. Time O(n), Space O(k).
Q2: LC #220 — Value difference ≤ t within distance ≤ k.
TreeSet sliding window. Query floor(num+t) — check if >= num-t. Time O(n log k), Space O(k).

3️⃣ LC #242 — Valid Anagram

Core Idea

Frequency count. Increment for s, decrement for t. All zeros at end = anagram.
Brute Force → O(n log n): Sort both, compare.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean isAnagram(String s, String t) {
2    if (s.length() != t.length()) return false;
3    int[] freq = new int[26];
4    for (int i = 0; i < s.length(); i++) {
5        freq[s.charAt(i) - 'a']++;
6        freq[t.charAt(i) - 'a']--;
7    }
8    for (int count : freq) if (count != 0) return false;
9    return true;
10}

Dry Run

Input: s = "anagram", t = "nagaram"
Processing simultaneously (increment for s[i], decrement for t[i]):
All freq values = 0 → Output: true

Key Tricks

  • charAt(i) - 'a' maps char to index 0–25
  • Increment for s, decrement for t — net zero = anagram
  • Length check early exit

30-Second Interview Explanation

Frequency array of 26. Increment for s, decrement for t. All zeros → anagram. Time O(n), Space O(1).

️ Interview Traps

  • Not handling different lengths upfront

Most Common Follow-ups

Q1: Unicode characters?
java
QUBITS OF DPK
1HashMap<Character, Integer> map = new HashMap<>();
2for (char c : s.toCharArray()) map.merge(c, 1, Integer::sum);
3for (char c : t.toCharArray()) {
4    if (!map.containsKey(c)) return false;
5    map.merge(c, -1, Integer::sum);
6    if (map.get(c) == 0) map.remove(c);
7}
8return map.isEmpty();
Q2: LC #49 — Group Anagrams.
java
QUBITS OF DPK
1public List<List<String>> groupAnagrams(String[] strs) {
2    HashMap<String, List<String>> map = new HashMap<>();
3    for (String str : strs) {
4        int[] freq = new int[26];
5        for (char c : str.toCharArray()) freq[c - 'a']++;
6        String key = Arrays.toString(freq);
7        map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
8    }
9    return new ArrayList<>(map.values());
10}
Time O(nL), Space O(nL).

4️⃣ LC #387 — First Unique Character in a String

Core Idea

Two passes: build frequency, then traverse ORIGINAL STRING for first count == 1.
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public int firstUniqChar(String s) {
2    int[] freq = new int[26];
3    for (char c : s.toCharArray()) freq[c - 'a']++;
4    for (int i = 0; i < s.length(); i++)
5        if (freq[s.charAt(i) - 'a'] == 1) return i;
6    return -1;
7}

Dry Run

Input: s = "leetcode"
Pass 1 — build frequency:
Pass 2 — find first with count 1:
Output: 0

Key Tricks

  • Second pass on ORIGINAL STRING — not the map (no order in map)
  • Single pass impossible — need complete frequency first

30-Second Interview Explanation

First pass builds frequency. Second pass iterates original string returning first index with frequency 1. Can't do single pass — need complete count to confirm uniqueness. Time O(n), Space O(1).

️ Interview Traps

  • Iterating HashMap in second pass — no guaranteed order

Most Common Follow-ups

Q1: String is a stream?
Use LinkedHashMap to maintain insertion order + frequency. After stream ends, iterate LinkedHashMap for first entry with count 1. Preserves order while tracking frequency.
Q2: Return character, not index?
Return s.charAt(i) instead of i. Return ' ' or '\0' as sentinel for no unique character.

5️⃣ LC #349 — Intersection of Two Arrays

Core Idea

HashSet from nums1. Check each num in nums2. ResultSet deduplicates.
Optimized → O(n+m) Time | O(n+m) Space:
java
QUBITS OF DPK
1public int[] intersection(int[] nums1, int[] nums2) {
2    HashSet<Integer> set1 = new HashSet<>();
3    for (int num : nums1) set1.add(num);
4    HashSet<Integer> resultSet = new HashSet<>();
5    for (int num : nums2)
6        if (set1.contains(num)) resultSet.add(num);
7    int[] result = new int[resultSet.size()];
8    int index = 0;
9    for (int num : resultSet) result[index++] = num;
10    return result;
11}

Dry Run

Input: nums1 = [4,9,9,5], nums2 = [9,4,9,8,4]
Build set1: {4, 9, 5}
Output: [9, 4] (order may vary)

Key Tricks

  • Build from LARGER array, iterate SMALLER (performance)
  • ResultSet automatically deduplicates
  • No sorting needed

30-Second Interview Explanation

HashSet from nums1. Iterate nums2 — if exists in set, add to resultSet. ResultSet deduplicates. Convert to array. Time O(n+m), Space O(n+m).

️ Interview Traps

  • Using ArrayList for result → needs manual duplicate check

Most Common Follow-ups

Q1: Both arrays sorted — O(1) space?
java
QUBITS OF DPK
1public int[] intersectionSorted(int[] nums1, int[] nums2) {
2    List<Integer> result = new ArrayList<>();
3    int left = 0, right = 0;
4    while (left < nums1.length && right < nums2.length) {
5        if (nums1[left] == nums2[right]) {
6            if (result.isEmpty() || result.get(result.size()-1) != nums1[left])
7                result.add(nums1[left]);
8            left++; right++;
9        } else if (nums1[left] < nums2[right]) left++;
10        else right++;
11    }
12    return result.stream().mapToInt(i->i).toArray();
13}
Q2: One array very large, other small?
Build HashSet from SMALLER array only. Iterate larger. Minimizes memory to O(min(n,m)) space.

6️⃣ LC #350 — Intersection of Two Arrays II

Core Idea

HashMap for frequency. Decrement on match. REMOVE key at zero to prevent false matches.
Optimized → O(n+m) Time | O(min(n,m)) Space:
java
QUBITS OF DPK
1class Solution {
2    public int[] intersect(int[] nums1, int[] nums2) {
3        
4
5        if(nums1.length > nums2.length){
6            return intersect(nums2,nums1);
7        }
8
9        HashMap<Integer,Integer> map = new HashMap<>();
10
11        for(int i=0;i<nums1.length;i++){
12
13            map.put(nums1[i],map.getOrDefault(nums1[i],0)+1);
14            
15        }
16
17        ArrayList<Integer> list = new ArrayList<>();
18
19        for(int i=0;i<nums2.length;i++){
20
21            if(map.containsKey(nums2[i]) && map.get(nums2[i]) > 0){
22                list.add(nums2[i]);
23                map.put(nums2[i],map.get(nums2[i])-1);
24            }
25        }
26
27        int[] ans = new int[list.size()];
28        for(int i = 0; i < list.size(); i++){
29            ans[i] = list.get(i);
30        }       
31
32        return ans;
33
34    }
35}

Dry Run

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Build freqMap from nums2: {2:2}
Output: [2, 2]

Key Tricks

  • REMOVE key at count 0 — prevents false match on third occurrence
  • Build from smaller array for space efficiency
  • ArrayList because result size unknown

30-Second Interview Explanation

HashMap frequency from smaller array. Iterate larger — on match, add to result, decrement count, remove at zero. Time O(n+m), Space O(min(n,m)).

️ Interview Traps

  • Not removing key at zero → third occurrence incorrectly matches

Most Common Follow-ups

Q1: Arrays are sorted — two pointer approach.
java
QUBITS OF DPK
1public int[] intersectSorted(int[] nums1, int[] nums2) {
2    List<Integer> result = new ArrayList<>();
3    int i = 0, j = 0;
4    while (i < nums1.length && j < nums2.length) {
5        if (nums1[i] == nums2[j]) { result.add(nums1[i]); i++; j++; }
6        else if (nums1[i] < nums2[j]) i++;
7        else j++;
8    }
9    return result.stream().mapToInt(x -> x).toArray();
10}
Time O(n+m), Space O(1) extra.
Q2: nums2 stored on disk (too large)?
Load nums1 into HashMap. Stream nums2 in chunks from disk. Process each chunk against HashMap. Only nums1 (smaller) stays in memory.

7️⃣ LC #448 — Find All Numbers Disappeared in an Array

Core Idea

Index marking: negate nums[abs(nums[i])-1] to mark presence. Positive in second pass = missing.
O(1) Space → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public List<Integer> findDisappearedNumbers(int[] nums) {
2    for (int i = 0; i < nums.length; i++) {
3        int index = Math.abs(nums[i]) - 1;
4        if (nums[index] > 0) nums[index] = -nums[index];
5    }
6    List<Integer> result = new ArrayList<>();
7    for (int i = 0; i < nums.length; i++)
8        if (nums[i] > 0) result.add(i + 1);
9    return result;
10}

Dry Run

Input: nums = [4, 3, 2, 7, 8, 2, 3, 1], n=8
Pass 1 — mark negatives:
Pass 2 — find positives (missing numbers):
Output: [5, 6]

Key Tricks

  • Math.abs(nums[i]) — value may already be negative from previous marking
  • Mark negative only if currently positive — prevents double-negation
  • Positive in second pass = i+1 never appeared as a value

30-Second Interview Explanation

Use values as indices to mark presence by negating. Second pass finds positive positions = missing numbers. Time O(n), Space O(1).

️ Interview Traps

  • Forgetting Math.abs when computing index → already-negative values give wrong index → ArrayIndexOutOfBounds

Most Common Follow-ups

Q1: Without modifying input — HashSet approach.
java
QUBITS OF DPK
1public List<Integer> findDisappearedNumbers(int[] nums) {
2    HashSet<Integer> present = new HashSet<>();
3    for (int num : nums) present.add(num);
4    List<Integer> result = new ArrayList<>();
5    for (int i = 1; i <= nums.length; i++)
6        if (!present.contains(i)) result.add(i);
7    return result;
8}
Time O(n), Space O(n).
Q2: LC #41 — First Missing Positive (similar concept, harder).
Place each number at its correct index position (nums[i] should be at index nums[i]-1). Scan for first index where nums[i] != i+1. Time O(n), Space O(1).

8️⃣ LC #383 — Ransom Note

Core Idea

Build frequency from magazine (source). Decrement for ransomNote (demand). Negative = can't construct.
Optimized → O(n+m) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean canConstruct(String ransomNote, String magazine) {
2    int[] freq = new int[26];
3    for (char c : magazine.toCharArray()) freq[c - 'a']++;
4    for (char c : ransomNote.toCharArray()) {
5        freq[c - 'a']--;
6        if (freq[c - 'a'] < 0) return false;
7    }
8    return true;
9}

Dry Run

Input: ransomNote = "aa", magazine = "aab"
Build freq from magazine:
Process ransomNote:
Output: true
Input: ransomNote = "aab", magazine = "aa" → freq[a]=2, freq[b]=0. On 'b': 0-1=-1 < 0 → false

Key Tricks

  • Build from magazine (supply), decrement for ransomNote (demand)
  • Early exit when count goes negative
  • int[26] for O(1) space

30-Second Interview Explanation

Frequency array from magazine. For each char in ransomNote, decrement. Goes negative → can't supply → false. Time O(n+m), Space O(1).

️ Interview Traps

  • Confusing which string to build from and which to decrement

Most Common Follow-ups

Q1: Unicode characters?
java
QUBITS OF DPK
1HashMap<Character, Integer> map = new HashMap<>();
2for (char c : magazine.toCharArray()) map.merge(c, 1, Integer::sum);
3for (char c : ransomNote.toCharArray()) {
4    int count = map.getOrDefault(c, 0) - 1;
5    if (count < 0) return false;
6    if (count == 0) map.remove(c); else map.put(c, count);
7}
8return true;
Q2: Each magazine letter used at most once?
Already the case — each decrement consumes one occurrence. Problem models this exactly.

9️⃣ LC #202 — Happy Number

Core Idea

Sum of squared digits. Non-happy numbers always cycle. HashSet detects cycle.
HashSet → O(log n) per step:
java
QUBITS OF DPK
1public boolean isHappy(int n) {
2    HashSet<Integer> seen = new HashSet<>();
3    int sum = 0;
4    int num = n;
5    while (num != 1 && !seen.contains(num)) {
6        seen.add(num);
7        while (num > 0) {
8            int digit = num % 10;
9            sum += digit * digit;
10            num = num / 10;
11        }
12        num = sum;
13        sum = 0;  // CRITICAL: reset for next iteration
14    }
15    return num == 1;
16}

Dry Run

Input: n = 19
num == 1 → Output: true
Bug demo — without sum = 0 reset:
Wrong from iteration 2 onward!

Key Tricks

  • seen.add(num) BEFORE computing next — so revisit is caught
  • sum = 0 reset at end of each iteration — critical bug if forgotten
  • Non-happy numbers always cycle through: 4→16→37→58→89→145→42→20→4

30-Second Interview Explanation

Compute sum of squared digits repeatedly. Non-happy numbers always cycle — HashSet detects revisit. Reset sum each iteration. Time O(log n) per step, Space O(log n).

️ Interview Traps

  • Forgetting sum = 0 reset → previous sums bleed into next iteration

Most Common Follow-ups

Q1: O(1) space — Floyd's cycle detection.
java
QUBITS OF DPK
1public boolean isHappy(int n) {
2    int slow = n, fast = sumOfSquaredDigits(n);
3    while (fast != 1 && slow != fast) {
4        slow = sumOfSquaredDigits(slow);
5        fast = sumOfSquaredDigits(sumOfSquaredDigits(fast));
6    }
7    return fast == 1;
8}
Slow moves 1 step, fast moves 2. If cycle exists, fast laps slow and they meet. If no cycle (reaches 1), fast gets there first.
Q2: What cycle do non-happy numbers enter?
Fixed cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. You can hardcode: check n == 4 inside loop as O(1) space shortcut.

LC #205 — Isomorphic Strings

Core Idea

Two HashMaps — one for s→t, one for t→s. Both must be consistent (bijection).
Optimized → O(n) Time | O(1) Space:
java
QUBITS OF DPK
1public boolean isIsomorphic(String s, String t) {
2    HashMap<Character, Character> mapST = new HashMap<>();
3    HashMap<Character, Character> mapTS = new HashMap<>();
4    for (int i = 0; i < s.length(); i++) {
5        char sChar = s.charAt(i), tChar = t.charAt(i);
6        if (mapST.containsKey(sChar) && mapST.get(sChar) != tChar) return false;
7        if (mapTS.containsKey(tChar) && mapTS.get(tChar) != sChar) return false;
8        mapST.put(sChar, tChar);
9        mapTS.put(tChar, sChar);
10    }
11    return true;
12}

Dry Run

Input: s = "ab", t = "aa" (one map failure case)
With only mapST:
Returns true — WRONG!
With mapTS catching it:
Output: false
Input: s = "egg", t = "add" (valid isomorphic)
Output: true

Key Tricks

  • ONE map is NOT enough — misses many-to-one mapping
  • Both directions must be checked for bijection
  • Space is O(1) — at most 256 unique characters

30-Second Interview Explanation

Two maps enforcing bidirectional consistency. One-way mapping allows many-to-one which is invalid. Both maps must agree at every step. Time O(n), Space O(1).

️ Interview Traps

  • One map alone → misses different s chars mapping to same t char

Most Common Follow-ups

Q1: Why does one map fail? Concrete example.
s="ab", t="aa". With only mapST: 'a'→'a' and 'b'→'a' both added without conflict. But two different s-chars map to same t-char — not isomorphic. mapTS catches this: when 'a' in t tries to map to both 'a' and 'b' in s, conflict detected on second occurrence.
Q2: LC #290 — Word Pattern (same concept at word level).
java
QUBITS OF DPK
1public boolean wordPattern(String pattern, String s) {
2    String[] words = s.split(" ");
3    if (pattern.length() != words.length) return false;
4    HashMap<Character, String> charToWord = new HashMap<>();
5    HashMap<String, Character> wordToChar = new HashMap<>();
6    for (int i = 0; i < pattern.length(); i++) {
7        char c = pattern.charAt(i); String w = words[i];
8        if (charToWord.containsKey(c) && !charToWord.get(c).equals(w)) return false;
9        if (wordToChar.containsKey(w) && wordToChar.get(w) != c) return false;
10        charToWord.put(c, w); wordToChar.put(w, c);
11    }
12    return true;
13}