Meta Interview Audio Refresher

Easy + Medium only (110 questions)

Total 110 Easy 34 Medium 76

This page is optimized for Chrome Reading Mode text-to-speech. Use group jumps, then listen section by section.

Binary Search & Selection (7)

  1. LC 278 - First Bad Version Easy

    Clarify: Is isBadVersion() expensive? (Yes — minimizing calls is the entire point)

    Pattern: Leftmost Binary Search. Core: Versions form a monotonic boolean array: [GOOD...GOOD, BAD...BAD].

    Verify: Input: n=5, bad=4

    Trap: Integer overflow: mid=(lo+hi)//2 overflows when lo+hi approaches INT_MAX.

    Complexity: Time O(log n) | Space O(1). LeetCode

  2. LC 33 - Search in Rotated Sorted Array Medium

    Clarify: Are all elements distinct? (follow-up: LC 81 with duplicates)

    Pattern: Binary Search. Core: Even in a rotated array, ONE of the two halves around mid is ALWAYS normally sorted.

    Verify: Input: nums=[4,5,6,7,0,1,2], target=0 → Output: 4

    Trap: Using strict < instead of <= in nums[lo] <= nums[mid].

    Complexity: Time O(log n) | Space O(1). LeetCode

  3. LC 34 - Find First and Last Position of Element in Sorted Array Medium

    Clarify: Array sorted non-decreasing — confirmed?

    Pattern: Binary Search ×2. Core: Run binary search TWICE — once biased LEFT (find first occurrence), once biased RIGHT (find last).

    Verify: Input: nums=[5,7,7,8,8,10], target=8 → Output: [3,4]

    Trap: Trying to solve in ONE pass — almost always introduces subtle bugs.

    Complexity: Time O(log n) | Space O(1). LeetCode

  4. LC 162 - Find Peak Element Medium

    Clarify: Is there guaranteed to be at least one peak? (Yes — boundaries are -∞)

    Pattern: Binary Search on Answer. Core: At any midpoint, if nums[mid] < nums[mid+1], the slope goes UP — a peak MUST exist to the right.

    Verify: Input: nums=[1,2,3,1] → Output: 2 (nums[2]=3)

    Trap: Writing while lo<=hi with hi=mid-1.

    Complexity: Time O(log n) | Space O(1). LeetCode

  5. LC 215 - Kth Largest Element in an Array Medium

    Clarify: k is 1-indexed largest (k=1 means max)?

    Pattern: Quickselect (or Min-Heap). Core: Quickselect partitions like Quicksort but only recurses/iterates into one side containing the target index.

    Verify: Input: nums=[3,2,1,5,6,4], k=2 -> 5

    Trap: Sorting entire array gives O(n log n), which is accepted but not optimal.

    Complexity: Time Average O(n), worst O(n²) | Space O(1). LeetCode

  6. LC 378 - Kth Smallest Element in a Sorted Matrix Medium

    Clarify: Rows and columns both sorted ascending?

    Pattern: Binary Search on Value Space. Core: Binary search over the VALUE range `[minVal, maxVal]`, not indices.

    Verify: Input: matrix=[[1,5,9],[10,11,13],[12,13,15]], k=8 -> 13

    Trap: Flattening then sorting costs O(n² log n).

    Complexity: Time O(n log(maxVal-minVal)) | Space O(1). LeetCode

  7. LC 528 - Random Pick with Weight Medium

    Clarify: Weights are positive integers?

    Pattern: Prefix Sum + Binary Search. Core: Build prefix sums so each index owns an interval of total weight.

    Verify: Input: w=[1,3]

    Trap: Off-by-one in random target range is common.

    Complexity: Time Init O(n), pick O(log n) | Space O(n). LeetCode

Graphs & Trees (28)

  1. LC 67 - Add Binary Easy

    Clarify: Inputs contain only '0' and '1'?

    Pattern: Simultaneous Traversal + Carry. Core: Identical structure to Add Two Numbers.

    Verify: Input: a="11", b="1" → Output: "100"

    Trap: Building result with string concatenation inside the loop: result = str(digit) + result.

    Complexity: Time O(max(m,n)) | Space O(max(m,n)). LeetCode

  2. LC 100 - Same Tree Easy

    Clarify: Are both trees possibly empty? (Yes)

    Pattern: DFS (Parallel Traversal). Core: Traverse both trees in lockstep.

    Verify: Input: p=[1,2,3], q=[1,2,3] -> true

    Trap: Checking only in-order traversals or value multisets.

    Complexity: Time O(n) | Space O(h). LeetCode

  3. LC 110 - Balanced Binary Tree Easy

    Clarify: Empty tree is balanced? (Yes)

    Pattern: Post-Order DFS + Height Check. Core: Use post-order DFS so each node gets left/right heights from children first.

    Verify: Input: root=[3,9,20,null,null,15,7] -> true

    Trap: Computing height separately for each node (`isBalanced` calls `height` repeatedly) causes O(n^2) in skewed trees.

    Complexity: Time O(n) | Space O(h). LeetCode

  4. LC 257 - Binary Tree Paths Easy

    Clarify: Return root-to-leaf only (not every path)?

    Pattern: DFS + Path Building. Core: Classic DFS.

    Verify: Input: root=[1,2,3,null,5]

    Trap: Using one shared string without backtracking correctly.

    Complexity: Time O(n) | Space O(h). LeetCode

  5. LC 270 - Closest Binary Search Tree Value Easy

    Clarify: Return node value (not node reference)?

    Pattern: BST Guided Traversal. Core: Use BST ordering to discard half the tree each step.

    Verify: Input: root=[4,2,5,1,3], target=3.714286 -> 4

    Trap: Doing full DFS/BFS over all nodes (O(n)) and ignoring BST property.

    Complexity: Time O(h) | Space O(1). LeetCode

  6. LC 339 - Nested List Weight Sum Easy

    Clarify: Root depth starts at 1?

    Pattern: DFS/BFS with Depth Tracking. Core: Traverse all elements while carrying current depth.

    Verify: Input: nestedList=[[1,1],2,[1,1]]

    Trap: Forgetting to increment depth when descending into child lists causes underweighted sums.

    Complexity: Time O(n) | Space O(d). LeetCode

  7. LC 543 - Diameter of Binary Tree Easy

    Clarify: Diameter measured in edges (not nodes)?

    Pattern: DFS Height + Global Max. Core: At each node, candidate diameter is leftHeight + rightHeight.

    Verify: Input: [1,2,3,4,5]

    Trap: Returning `best` from recursion instead of node height.

    Complexity: Time O(n) | Space O(h). LeetCode

  8. LC 938 - Range Sum of BST Easy

    Clarify: Range is inclusive [low, high]?

    Pattern: DFS + BST Pruning. Core: DFS with pruning: if node value is smaller than low, skip entire left subtree; if larger than high, skip entire right subtree.

    Verify: Input: root=[10,5,15,3,7,null,18], low=7, high=15 -> 32

    Trap: Ignoring BST property and doing plain full-tree DFS every time.

    Complexity: Time O(n) worst-case, O(m) average with pruning | Space O(h). LeetCode

  9. LC 2 - Add Two Numbers Medium

    Clarify: Digits stored in REVERSE order — head is the ones place? (This is the gift — no reversal needed)

    Pattern: Simultaneous Traversal + Carry. Core: Simulate third-grade addition: add digit by digit from right to left, carrying overflow.

    Verify: Input: l1=2→4→3 (342), l2=5→6→4 (465)

    Trap: Loop condition 'while l1 OR l2' without the third condition 'OR carry != 0'.

    Complexity: Time O(max(m,n)) | Space O(max(m,n)). LeetCode

  10. LC 98 - Validate Binary Search Tree Medium

    Clarify: Strictly less than or can equal values exist?

    Pattern: DFS + Range Propagation. Core: Naive mistake: only check local parent-child relationship.

    Verify: Input: 2 Output: true

    Trap: Using only local parent-child check (node.left.val < node.val).

    Complexity: Time O(n) | Space O(h). LeetCode

  11. LC 114 - Flatten Binary Tree to Linked List Medium

    Clarify: In-place only — confirmed?

    Pattern: Morris Traversal. Core: For each node: find the RIGHTMOST node of its left subtree (the pre-order predecessor).

    Verify: Input: 1 Output: 1→2→3→4→5→6

    Trap: Recursive solutions get pointer order wrong under pressure — you move a pointer before saving a reference and lose part of the tree.

    Complexity: Time O(n) | Space O(1). LeetCode

  12. LC 129 - Sum Root to Leaf Numbers Medium

    Clarify: Node values are single digits 0..9?

    Pattern: DFS Accumulating Path Value. Core: Carry a running number while traversing: `curr = curr*10 + node.val`.

    Verify: Input: root=[1,2,3]

    Trap: Collecting full path strings/arrays first and converting later adds unnecessary overhead.

    Complexity: Time O(n) | Space O(h). LeetCode

  13. LC 133 - Clone Graph Medium

    Clarify: Can graph have cycles? (Yes — visited map prevents infinite loops)

    Pattern: BFS + HashMap. Core: BFS/DFS traversal + HashMap {original → clone}.

    Verify: Input: adjList=[[2,4],[1,3],[2,4],[1,3]]

    Trap: Adding neighbors before checking visited — creates duplicate clone nodes for the same original.

    Complexity: Time O(V+E) | Space O(V). LeetCode

  14. LC 173 - Binary Search Tree Iterator Medium

    Clarify: Average O(1) for next() — not worst-case?

    Pattern: Controlled In-Order Traversal. Core: Simulate in-order traversal LAZILY — only compute the next element when next() is called.

    Verify: BSTIterator(root=[7,3,15,null,null,9,20])

    Trap: Claiming O(1) worst-case instead of AMORTIZED O(1).

    Complexity: Time Amortized O(1) | Space O(h). LeetCode

  15. LC 199 - Binary Tree Right Side View Medium

    Clarify: Right side = last visible node at each depth level?

    Pattern: BFS Level-Order. Core: BFS level-by-level.

    Verify: Input: 1 Output: [1,3,4]

    Trap: DFS left-first and taking last at each depth gets right/left priority backwards.

    Complexity: Time O(n) | Space O(w). LeetCode

  16. LC 200 - Number of Islands Medium

    Clarify: 4-directional connectivity only (no diagonals)?

    Pattern: BFS Flood Fill. Core: Every time you find an unvisited '1', you've found a new island — increment counter.

    Verify: Input:

    Trap: Marking visited AFTER dequeuing instead of ON ENQUEUE.

    Complexity: Time O(m×n) | Space O(min(m,n)). LeetCode

  17. LC 207 - Course Schedule Medium

    Clarify: Is prerequisite pair [a,b] meaning b -> a edge?

    Pattern: Topological Sort (Kahn). Core: A course plan is possible iff the prerequisite graph is acyclic.

    Verify: Input: numCourses=2, prerequisites=[[1,0]]

    Trap: Only running BFS/DFS from course 0 misses disconnected components.

    Complexity: Time O(V+E) | Space O(V+E). LeetCode

  18. LC 210 - Course Schedule II Medium

    Clarify: Any valid topological order accepted?

    Pattern: Topological Sort (Kahn, Order Construction). Core: Same graph as LC 207, but instead of counting only, record dequeue order during Kahn's algorithm.

    Verify: Input: numCourses=2, prerequisites=[[1,0]]

    Trap: Using DFS without proper cycle-state tracking can return invalid partial orders.

    Complexity: Time O(V+E) | Space O(V+E). LeetCode

  19. LC 211 - Design Add and Search Words Data Structure Medium

    Clarify: '.' matches any SINGLE letter — confirmed?

    Pattern: Trie + DFS Wildcard. Core: Trie for prefix-matching structure.

    Verify: WordDictionary wd

    Trap: Using a flat list for storage and doing regex scan for search — gives O(n×m) per search where n=words stored.

    Complexity: Time O(m) add, O(26^m) search worst | Space O(total chars). LeetCode

  20. LC 236 - Lowest Common Ancestor of a Binary Tree Medium

    Clarify: Are p and q guaranteed to exist? (Logic changes if not)

    Pattern: DFS Post-Order. Core: Post-order DFS.

    Verify: Input: tree=[3,5,1,6,2,0,8,null,null,7,4], p=5, q=1

    Trap: Early-terminating when finding p without checking its subtree for q.

    Complexity: Time O(n) | Space O(h). LeetCode

  21. LC 314 - Binary Tree Vertical Order Traversal Medium

    Clarify: Within same row/column, should order follow BFS left-to-right?

    Pattern: BFS + Column Indexing. Core: Use BFS with (node, column).

    Verify: Input: [3,9,20,null,null,15,7]

    Trap: Using DFS without row tracking can break required ordering for nodes sharing the same column.

    Complexity: Time O(n) | Space O(n). LeetCode

  22. LC 426 - Convert Binary Search Tree to Sorted Doubly Linked List Medium

    Clarify: Output must be circular?

    Pattern: In-Order Traversal + Pointer Stitching. Core: In-order traversal visits nodes in sorted order.

    Verify: Input: [4,2,5,1,3]

    Trap: Forgetting final head-tail linking.

    Complexity: Time O(n) | Space O(h). LeetCode

  23. LC 545 - Boundary of Binary Tree Medium

    Clarify: Boundary is anti-clockwise and starts with root?

    Pattern: Tree Traversal (Left Boundary + Leaves + Right Boundary). Core: Build answer in three non-overlapping passes: left boundary (top-down, skip leaves), leaves (full DFS), right boundary (top-down into temp, skip leaves, then reverse).

    Verify: Input: root=[1,null,2,3,4]

    Trap: Including leaves in left/right boundary loops duplicates them when leaf pass runs.

    Complexity: Time O(n) | Space O(h). LeetCode

  24. LC 721 - Accounts Merge Medium

    Clarify: Same name does not guarantee same person?

    Pattern: Union-Find + Email Graph. Core: Union emails that appear in the same account.

    Verify: Input:

    Trap: Merging by name alone.

    Complexity: Time O(N alpha(N) + E log E) | Space O(E). LeetCode

  25. LC 785 - Is Graph Bipartite? Medium

    Clarify: Can graph be disconnected? (Yes — MUST check ALL components)

    Pattern: BFS 2-Coloring. Core: Try to 2-color the graph — color every node RED or BLUE such that no two adjacent nodes share a color.

    Verify: Input: graph=[[1,2,3],[0,2],[0,1,3],[0,2]]

    Trap: Not handling disconnected graphs.

    Complexity: Time O(V+E) | Space O(V). LeetCode

  26. LC 863 - All Nodes Distance K in Binary Tree Medium

    Clarify: Distance is number of edges?

    Pattern: Tree to Undirected Graph + BFS. Core: Tree nodes only have child pointers, but distance-k search needs moving both downward and upward.

    Verify: Input: root=[3,5,1,6,2,0,8,null,null,7,4], target=5, k=2

    Trap: Forgetting a visited set causes infinite revisits between child and parent pointers after adding parent edges.

    Complexity: Time O(n) | Space O(n). LeetCode

  27. LC 1091 - Shortest Path in Binary Matrix Medium

    Clarify: Moves allowed in all 8 directions (including diagonals)?

    Pattern: 8-Direction BFS on Grid. Core: Treat each clear cell as an unweighted graph node and run BFS from (0,0).

    Verify: Input: grid=[[0,1],[1,0]] -> 2

    Trap: Using DFS/greedy can miss the shortest path in an unweighted graph.

    Complexity: Time O(n^2) | Space O(n^2). LeetCode

  28. LC 1382 - Balance a Binary Search Tree Medium

    Clarify: Need to preserve original node objects, or can create new nodes? (Either accepted on LeetCode)

    Pattern: In-Order Traversal + Rebuild from Sorted Array. Core: In-order traversal of BST gives sorted values.

    Verify: Input: root=[1,null,2,null,3,null,4,null,null]

    Trap: Trying local AVL-style rotations from an arbitrary unbalanced BST is complex and error-prone for interviews.

    Complexity: Time O(n) | Space O(n). LeetCode

Sliding Window & Two Pointers (19)

  1. LC 26 - Remove Duplicates from Sorted Array Easy

    Clarify: Array is sorted non-decreasing?

    Pattern: Two Pointers (Write Index). Core: Maintain write pointer for next unique slot.

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

    Trap: Comparing against nums[write-1] after overwrites without understanding invariants can cause subtle mistakes.

    Complexity: Time O(n) | Space O(1). LeetCode

  2. LC 88 - Merge Sorted Array Easy

    Clarify: nums1 has enough trailing space?

    Pattern: Two Pointers from End. Core: Fill nums1 from the back.

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

    Trap: Merging from the front overwrites unread values in nums1.

    Complexity: Time O(m+n) | Space O(1). LeetCode

  3. LC 125 - Valid Palindrome Easy

    Clarify: Ignore case and non-alphanumeric — confirmed?

    Pattern: Two Pointers + Inline Filter. Core: Two pointers from both ends.

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

    Trap: Creating a cleaned string first (filter + lowercase) then checking palindrome.

    Complexity: Time O(n) | Space O(1). LeetCode

  4. LC 283 - Move Zeroes Easy

    Clarify: In-place — confirmed?

    Pattern: Two Pointers (Read/Write). Core: slow pointer marks the next write position for non-zero elements.

    Verify: Input: nums=[0,1,0,3,12] → Output: [1,3,12,0,0]

    Trap: Using the swap variant without understanding its trade-off.

    Complexity: Time O(n) | Space O(1). LeetCode

  5. LC 408 - Valid Word Abbreviation Easy

    Clarify: Are leading zeros in a number allowed? (No)

    Pattern: Two Pointers + Number Parsing. Core: Use two pointers: `i` for `word`, `j` for `abbr`.

    Verify: Input: word="internationalization", abbr="i12iz4n" -> true

    Trap: Parsing only one digit at a time instead of full numbers.

    Complexity: Time O(n+m) | Space O(1). LeetCode

  6. LC 680 - Valid Palindrome II Easy

    Clarify: At most one deletion — zero deletions (already palindrome) also returns true?

    Pattern: Two Pointers + One Skip Allowance. Core: Two-pointer palindrome check.

    Verify: Input: s="aba" → true (already palindrome)

    Trap: Allowing recursive skips inside isPalindrome.

    Complexity: Time O(n) | Space O(1). LeetCode

  7. LC 3 - Longest Substring Without Repeating Characters Medium

    Clarify: Return the length or the substring itself?

    Pattern: Sliding Window + HashMap. Core: Sliding window [left, right].

    Verify: Input: s="abcabcbb" → Output: 3 ("abc")

    Trap: Missing the condition map[c] >= left.

    Complexity: Time O(n) | Space O(min(n, alphabet)). LeetCode

  8. LC 11 - Container With Most Water Medium

    Clarify: Return only the max area (not the indices)?

    Pattern: Two Pointers (Greedy). Core: Use two pointers at both ends.

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

    Trap: Brute force O(n^2) checks all pairs and times out at larger constraints.

    Complexity: Time O(n) | Space O(1). LeetCode

  9. LC 15 - 3Sum Medium

    Clarify: Distinct indices but values can repeat?

    Pattern: Sort + Two Pointers. Core: Sort the array.

    Verify: Input: nums=[-1,0,1,2,-1,-4]

    Trap: Duplicate skipping at the wrong level.

    Complexity: Time O(n²) | Space O(1). LeetCode

  10. LC 31 - Next Permutation Medium

    Clarify: Must modify in-place?

    Pattern: Pivot + Reverse Suffix. Core: Find rightmost pivot `i` where nums[i] < nums[i+1].

    Verify: Input: [1,2,3] -> [1,3,2]

    Trap: Sorting the suffix instead of reversing it.

    Complexity: Time O(n) | Space O(1). LeetCode

  11. LC 56 - Merge Intervals Medium

    Clarify: Sort by start time first?

    Pattern: Sort + Linear Scan. Core: Sort by start.

    Verify: Input: intervals=[[1,3],[2,6],[8,10],[15,18]]

    Trap: Writing last.end = curr.end instead of max(last.end, curr.end).

    Complexity: Time O(n log n) | Space O(n). LeetCode

  12. LC 57 - Insert Interval Medium

    Clarify: Input intervals are already sorted and mutually non-overlapping?

    Pattern: Single Pass Merge over Sorted Intervals. Core: Three phases in one pass: (1) append all intervals ending before newInterval starts, (2) merge all overlapping intervals into newInterval, (3) append the rest.

    Verify: Input: intervals=[[1,3],[6,9]], newInterval=[2,5]

    Trap: Using strict overlap check `intervals[i][0] < newInterval[1]` misses touching boundaries like [1,2] and [2,3], which should merge for closed intervals.

    Complexity: Time O(n) | Space O(n). LeetCode

  13. LC 161 - One Edit Distance Medium

    Clarify: Exactly one edit (not zero)?

    Pattern: Two Pointers + Single Mismatch Budget. Core: Scan until first mismatch.

    Verify: Input: s="ab", t="acb" -> true

    Trap: Returning true when strings are identical.

    Complexity: Time O(n) | Space O(1). LeetCode

  14. LC 340 - Longest Substring with At Most K Distinct Characters Medium

    Clarify: Return length or the substring?

    Pattern: Sliding Window + Frequency Map. Core: Variable sliding window.

    Verify: Input: s="eceba", k=2 → Output: 3 ("ece")

    Trap: Not deleting the key from the map when count reaches 0.

    Complexity: Time O(n) | Space O(k). LeetCode

  15. LC 438 - Find All Anagrams in a String Medium

    Clarify: Return starting indices of all anagram substrings?

    Pattern: Sliding Window + Frequency Map. Core: Fixed-size sliding window of exactly len(p).

    Verify: Input: s="cbaebabacd", p="abc" → Output: [0,6]

    Trap: Comparing full frequency maps each window step instead of using the matched counter.

    Complexity: Time O(s+p) | Space O(1). LeetCode

  16. LC 567 - Permutation in String Medium

    Clarify: A permutation of s1 is a substring of s2 — confirmed? (Same as checking for any anagram)

    Pattern: Sliding Window + Frequency Map. Core: Structurally identical to Find All Anagrams — this is the same problem with a boolean return instead of collecting all indices.

    Verify: Input: s1="ab", s2="eidbaooo" → Output: true ("ba" at idx 3)

    Trap: Treating this as a unique problem and re-deriving from scratch.

    Complexity: Time O(s1+s2) | Space O(1). LeetCode

  17. LC 986 - Interval List Intersections Medium

    Clarify: Closed intervals [a,b] — endpoints inclusive? (Yes: [2,3] and [3,4] intersect at [3,3])

    Pattern: Two Pointers on Sorted Intervals. Core: Two pointers, one per list.

    Verify: A=[[0,2],[5,10],[13,23],[24,25]]

    Trap: Over-engineering with elaborate if-else for all overlap cases (A before B, B before A, A contains B, nested...).

    Complexity: Time O(m+n) | Space O(m+n). LeetCode

  18. LC 1868 - Product of Two Run-Length Encoded Arrays Medium

    Clarify: Each pair is [value, frequency]?

    Pattern: Two Pointers over RLE Runs. Core: Walk both encoded arrays with two pointers.

    Verify: Input: encoded1=[[1,3],[2,3]], encoded2=[[6,3],[3,3]]

    Trap: Decoding both arrays first can explode memory/time when frequencies are large.

    Complexity: Time O(n+m) | Space O(1) extra (excluding output). LeetCode

  19. LC 3634 - Minimum Removals to Balance Array Medium

    Clarify: Can we remove elements from any positions (not necessarily contiguous)?

    Pattern: Sort + Sliding Window (Two Pointers). Core: After sorting, keeping a balanced subset is equivalent to finding the longest window `[l..r]` where `nums[r] <= k * nums[l]`.

    Verify: Input: nums=[2,1,5,6], k=3 -> 1

    Trap: Trying unsorted greedy removals by local min/max updates often fails.

    Complexity: Time O(n log n) | Space O(1) extra (or O(log n) sort stack). LeetCode

Backtracking (7)

  1. LC 17 - Letter Combinations of a Phone Number Medium

    Clarify: Return [] not [''] for empty input — confirmed?

    Pattern: Backtracking. Core: Decision tree — each level is one digit.

    Verify: Input: digits="23"

    Trap: Returning [''] instead of [] for empty input.

    Complexity: Time O(4ⁿ×n) | Space O(n). LeetCode

  2. LC 22 - Generate Parentheses Medium

    Clarify: Return only valid strings?

    Pattern: Backtracking with Valid Prefix Pruning. Core: Build candidates character-by-character while tracking how many opening and closing brackets are used.

    Verify: Input: n=3

    Trap: Generating all 2^(2n) strings and filtering valid ones is too slow.

    Complexity: Time O(Cn×n) | Space O(n). LeetCode

  3. LC 46 - Permutations Medium

    Clarify: All integers distinct? (Duplicates → LC 47)

    Pattern: Backtracking. Core: At each position in the permutation, choose one unused number from the remaining pool.

    Verify: Input: nums=[1,2,3]

    Trap: Not copying path before appending to result.

    Complexity: Time O(n!×n) | Space O(n). LeetCode

  4. LC 47 - Permutations II Medium

    Clarify: Must deduplicate output — confirmed?

    Pattern: Backtracking + Dedup. Core: Sort first.

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

    Trap: The dedup condition is NOT used[i-1].

    Complexity: Time O(n!×n) | Space O(n). LeetCode

  5. LC 77 - Combinations Medium

    Clarify: Numbers are from 1..n inclusive?

    Pattern: Backtracking (Choose k). Core: Backtrack with a start pointer so each number is used at most once and order is naturally increasing.

    Verify: Input: n=4, k=2

    Trap: Using permutations template (loop from 1 every time) generates duplicates like [1,2] and [2,1].

    Complexity: Time O(C(n,k)×k) | Space O(k). LeetCode

  6. LC 78 - Subsets Medium

    Clarify: All elements unique? (Duplicates → LC 90)

    Pattern: Backtracking. Core: At each index, make a binary decision: INCLUDE or EXCLUDE.

    Verify: Input: nums=[1,2,3]

    Trap: Adding to result only at depth==n (copying Permutations template).

    Complexity: Time O(2ⁿ×n) | Space O(n). LeetCode

  7. LC 247 - Strobogrammatic Number II Medium

    Clarify: Can result include numbers with leading zero? (Only allowed when n==1)

    Pattern: Backtracking / Construct from Center. Core: Build from the center outward using valid mirrored pairs.

    Verify: Input: n=2

    Trap: Allowing '0...0' at the outermost layer for n>1.

    Complexity: Time O(5^(n/2)) | Space O(5^(n/2)). LeetCode

DP & Prefix Sum (8)

  1. LC 509 - Fibonacci Number Easy

    Clarify: n range? (usually 0..30 on LC)

    Pattern: DP (Rolling Variables). Core: Bottom-up DP with O(1) space: keep only the previous two Fibonacci values and iteratively build up to n.

    Verify: Input: n=2 -> 1

    Trap: Using plain recursion without memoization leads to exponential O(2^n) time due to repeated subproblems.

    Complexity: Time O(n) | Space O(1). LeetCode

  2. LC 91 - Decode Ways Medium

    Clarify: '0' cannot start any valid encoding — confirmed?

    Pattern: 1D DP. Core: dp[i] = number of ways to decode first i characters.

    Verify: Input: s="12" → Output: 2 ("AB"=1+2, "L"=12)

    Trap: Handling '0' incorrectly.

    Complexity: Time O(n) | Space O(n)→O(1). LeetCode

  3. LC 139 - Word Break Medium

    Clarify: Can same word be reused? (Yes)

    Pattern: 1D DP. Core: dp[i] = can first i chars be segmented.

    Verify: Input: s="leetcode", wordDict=["leet","code"] → true

    Trap: Using a list instead of HashSet for wordDict.

    Complexity: Time O(n²) | Space O(n). LeetCode

  4. LC 304 - Range Sum Query 2D - Immutable Medium

    Clarify: Multiple queries on same fixed matrix? (Preprocessing is the whole motivation)

    Pattern: 2D Prefix Sum. Core: Build 2D prefix sum table.

    Verify: matrix=[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]

    Trap: Getting inclusion-exclusion signs wrong.

    Complexity: Time O(1) query / O(mn) build | Space O(m×n). LeetCode

  5. LC 322 - Coin Change Medium

    Clarify: Unlimited reuse of each coin denomination?

    Pattern: 1D DP (Unbounded Knapsack Min Coins). Core: Let `dp[a]` be the minimum coins required for amount `a`.

    Verify: Input: coins=[1,2,5], amount=11 -> 3

    Trap: Confusing this with 'Coin Change II' (count ways).

    Complexity: Time O(amount × len(coins)) | Space O(amount). LeetCode

  6. LC 523 - Continuous Subarray Sum Medium

    Clarify: Subarray must have at least TWO elements?

    Pattern: Prefix Sum + Modulo HashMap. Core: prefixSum[j] % k == prefixSum[i-1] % k means subarray nums[i..j] is divisible by k.

    Verify: Input: nums=[23,2,4,6,7], k=6 → true ([2,4] sums to 6)

    Trap: Two landmines: (1) Updating map when remainder already exists — must keep EARLIEST index to maximize subarray length.

    Complexity: Time O(n) | Space O(min(n,k)). LeetCode

  7. LC 560 - Subarray Sum Equals K Medium

    Clarify: Count subarrays (not just existence)?

    Pattern: Prefix Sum + HashMap. Core: prefixSum[j] - prefixSum[i] = k means subarray i+1..j sums to k.

    Verify: Input: nums=[1,1,1], k=2 → Output: 2

    Trap: Attempting sliding window.

    Complexity: Time O(n) | Space O(n). LeetCode

  8. LC 1653 - Minimum Deletions to Make String Balanced Medium

    Clarify: Only characters 'a' and 'b' appear?

    Pattern: One-Pass DP (Prefix b Count). Core: Scan left to right.

    Verify: Input: s="aababbab" -> 2

    Trap: Greedy deleting only current 'a' when conflict appears is not always optimal.

    Complexity: Time O(n) | Space O(1). LeetCode

Stack & Parsing (7)

  1. LC 20 - Valid Parentheses Easy

    Clarify: Can string length be odd? (then immediately false)

    Pattern: Stack. Core: Use a stack of opening brackets.

    Verify: Input: s="()" -> true

    Trap: Trying to validate by counting each bracket type independently (e.g., number of '(' equals ')').

    Complexity: Time O(n) | Space O(n). LeetCode

  2. LC 496 - Next Greater Element I Easy

    Clarify: nums1 values are unique and subset of nums2?

    Pattern: Monotonic Stack + HashMap. Core: Precompute next-greater for every value in nums2 using a decreasing monotonic stack.

    Verify: Input: nums1=[4,1,2], nums2=[1,3,4,2] -> [-1,3,-1]

    Trap: For each nums1 value, linearly scanning right in nums2 gives O(m*n).

    Complexity: Time O(n+m) | Space O(n). LeetCode

  3. LC 8 - String to Integer (atoi) Medium

    Clarify: Skip leading whitespace?

    Pattern: State Machine / Linear Parse. Core: Strict sequential state machine: (1) skip whitespace, (2) read sign, (3) read digits with pre-multiplication overflow check, (4) stop on first non-digit.

    Verify: Input: s="42" → Output: 42

    Trap: Checking overflow AFTER updating result — by then the value has already wrapped or been clamped incorrectly.

    Complexity: Time O(n) | Space O(1). LeetCode

  4. LC 71 - Simplify Path Medium

    Clarify: Input path is absolute (starts with '/')?

    Pattern: Stack + Tokenization. Core: Split by '/'.

    Verify: Input: path="/home/" -> "/home"

    Trap: Trying ad-hoc string replacements (like repeatedly replacing '/./' or '/../') misses edge cases with multiple slashes and root boundary behavior.

    Complexity: Time O(n) | Space O(n). LeetCode

  5. LC 468 - Validate IP Address Medium

    Clarify: IPv4: 4 decimal groups, 0-255, no leading zeros (except '0' itself)?

    Pattern: String Parsing + Case Analysis. Core: Split on '.' for IPv4, ':' for IPv6.

    Verify: Input: "172.16.254.1" → "IPv4"

    Trap: Python's split('.') on '1.2.3.4.' produces ['1','2','3','4',''] — 5 parts.

    Complexity: Time O(1) | Space O(1). LeetCode

  6. LC 636 - Exclusive Time of Functions Medium

    Clarify: Logs are already sorted by timestamp?

    Pattern: Stack + Previous Timestamp. Core: Use a stack of active function IDs and keep `prevTime`.

    Verify: Input:

    Trap: Forgetting that `end` timestamp is inclusive.

    Complexity: Time O(m) | Space O(n). LeetCode

  7. LC 1249 - Minimum Remove to Make Valid Parentheses Medium

    Clarify: Letters should remain in original relative order?

    Pattern: Stack + Mark Invalid Indices. Core: Use a stack to track indices of unmatched '(' and a set to mark invalid indices.

    Verify: Input: s="lee(t(c)o)de)" -> "lee(t(c)o)de"

    Trap: Removing characters directly from the string during traversal causes index shifts and bugs.

    Complexity: Time O(n) | Space O(n). LeetCode

Hashing & Counting (12)

  1. LC 1 - Two Sum Easy

    Clarify: Return indices, not values?

    Pattern: HashMap (Complement Lookup). Core: As you scan left to right, for each value x, you need target-x.

    Verify: Input: nums=[2,7,11,15], target=9 -> Output: [0,1]

    Trap: Sorting first and then using two pointers without preserving original indices.

    Complexity: Time O(n) | Space O(n). LeetCode

  2. LC 217 - Contains Duplicate Easy

    Clarify: Return boolean only?

    Pattern: HashSet. Core: Track seen values in a HashSet.

    Verify: Input: nums=[1,2,3,1] -> true

    Trap: Sorting first and then checking neighbors gives O(n log n) and mutates input order.

    Complexity: Time O(n) | Space O(n). LeetCode

  3. LC 219 - Contains Duplicate II Easy

    Clarify: Distance condition is index distance (abs(i-j))?

    Pattern: HashMap (Last Seen Index). Core: Track last seen index of each value in a HashMap.

    Verify: Input: nums=[1,2,3,1], k=3 -> true

    Trap: Forgetting to update `last[x]` when distance > k.

    Complexity: Time O(n) | Space O(n). LeetCode

  4. LC 349 - Intersection of Two Arrays Easy

    Clarify: Result elements must be unique (not duplicates)?

    Pattern: HashSet. Core: Hash the smaller array into a set.

    Verify: Input: nums1=[1,2,2,1], nums2=[2,2] → Output: [2]

    Trap: Not asking if arrays are sorted.

    Complexity: Time O(n+m) | Space O(min(n,m)). LeetCode

  5. LC 350 - Intersection of Two Arrays II Easy

    Clarify: Preserve duplicate counts — confirmed?

    Pattern: HashMap (Frequency). Core: Frequency map from smaller array.

    Verify: Input: nums1=[1,2,2,1], nums2=[2,2] → Output: [2,2]

    Trap: Not knowing the follow-up: 'What if arrays are too large for memory?' Answer: sort both, stream from disk, use two-pointer merge — O(1) in-memory.

    Complexity: Time O(n+m) | Space O(min(n,m)). LeetCode

  6. LC 953 - Verifying an Alien Dictionary Easy

    Clarify: Need pairwise check across adjacent words only?

    Pattern: Custom Comparator. Core: Build rank map from alien order and compare each adjacent pair by first differing character; handle prefix invalid case.

    Verify: Input: words=["hello","leetcode"], order="hlabcdefgijkmnopqrstuvwxyz"

    Trap: Ignoring prefix invalid case (`"abc"` before `"ab"`).

    Complexity: Time O(total chars) | Space O(1). LeetCode

  7. LC 49 - Group Anagrams Medium

    Clarify: Strings guaranteed lowercase? (Yes in LC)

    Pattern: HashMap + Canonical Key. Core: Two strings are anagrams iff their sorted characters are identical.

    Verify: Input: strs=["eat","tea","tan","ate","nat","bat"]

    Trap: Not knowing the O(k) frequency tuple optimization.

    Complexity: Time O(n×k log k) | Space O(n×k). LeetCode

  8. LC 138 - Copy List with Random Pointer Medium

    Clarify: Random can point to any node OR be null — confirmed?

    Pattern: HashMap or Interleaving. Core: HashMap {original → clone} serves dual purpose: visited set (prevents infinite loops) AND O(1) retrieval of any node's clone when wiring random pointers.

    Verify: Input: [[7,null],[13,0],[11,4],[10,2],[1,0]]

    Trap: In the interleave approach, Step 3 MUST restore the original list's next pointers (curr.next = curr.next.next).

    Complexity: Time O(n) | Space O(n) or O(1). LeetCode

  9. LC 146 - LRU Cache Medium

    Clarify: get and put both must be O(1) — confirmed?

    Pattern: HashMap + Doubly Linked List. Core: Need O(1) key lookup AND O(1) eviction of LRU item.

    Verify: LRUCache(capacity=2)

    Trap: Forgetting to delete the evicted key from the HashMap.

    Complexity: Time O(1) get and put | Space O(capacity). LeetCode

  10. LC 347 - Top K Frequent Elements Medium

    Clarify: Any order in output accepted?

    Pattern: HashMap + Bucket Sort (or Min-Heap). Core: Count frequencies with a HashMap, then retrieve highest frequencies efficiently.

    Verify: Input: nums=[1,1,1,2,2,3], k=2 -> [1,2]

    Trap: Sorting all frequency pairs is O(m log m) where m is unique count, which may still pass but misses the expected linear-time follow-up.

    Complexity: Time O(n) | Space O(n). LeetCode

  11. LC 791 - Custom Sort String Medium

    Clarify: Are all characters lowercase English letters?

    Pattern: Frequency Count + Custom Order. Core: Count frequency of characters in `s`.

    Verify: Input: order="cba", s="abcd" -> "cbad"

    Trap: Sorting `s` with a custom comparator works but is O(n log n).

    Complexity: Time O(|order| + |s|) | Space O(1). LeetCode

  12. LC 3713 - Longest Balanced Substring I Medium

    Clarify: Substring must be contiguous? (Yes)

    Pattern: Enumeration + Frequency Counting. Core: Fix start index `i` and expand end index `j`.

    Verify: Input: s="abbac" -> 4 ("abba")

    Trap: Trying a standard shrinking sliding window fails because the balanced condition is not monotonic as the right boundary grows.

    Complexity: Time O(n^2) | Space O(1). LeetCode

Design & Data Structures (1)

  1. LC 346 - Moving Average from Data Stream Easy

    Clarify: Window size fixed at construction?

    Pattern: Queue + Running Sum. Core: Maintain a queue of current window values and a running sum.

    Verify: MovingAverage(3)

    Trap: Recomputing sum of the whole queue on every `next` call leads to O(size) per operation.

    Complexity: Time O(1) per next | Space O(size). LeetCode

Greedy / Math / Bit / Misc (21)

  1. LC 9 - Palindrome Number Easy

    Clarify: Negative numbers are not palindromes?

    Pattern: Math (Reverse Half). Core: Do NOT reverse the whole number.

    Verify: Input: x=121 -> true

    Trap: Reversing the entire integer can overflow in fixed-width languages and does unnecessary work.

    Complexity: Time O(log10 n) | Space O(1). LeetCode

  2. LC 13 - Roman to Integer Easy

    Clarify: Input guaranteed valid Roman numeral?

    Pattern: Left-to-Right with Subtractive Rule. Core: If current symbol is smaller than next, subtract it; otherwise add it.

    Verify: Input: "III" -> 3

    Trap: Attempting many special-case if blocks for each subtractive pair.

    Complexity: Time O(n) | Space O(1). LeetCode

  3. LC 21 - Merge Two Sorted Lists Easy

    Clarify: Both lists sorted non-decreasing — confirmed?

    Pattern: Two Pointer Merge + Dummy Head. Core: Classic merge step from merge sort.

    Verify: Input: l1=1→2→4, l2=1→3→4

    Trap: Using the recursive solution without flagging its O(m+n) stack cost.

    Complexity: Time O(m+n) | Space O(1). LeetCode

  4. LC 121 - Best Time to Buy and Sell Stock Easy

    Clarify: At most ONE transaction (one buy + one sell)?

    Pattern: Greedy Single Pass. Core: Track the minimum price seen so far.

    Verify: Input: prices=[7,1,5,3,6,4] → Output: 5 (buy@1, sell@6)

    Trap: Not knowing the follow-up family.

    Complexity: Time O(n) | Space O(1). LeetCode

  5. LC 157 - Read N Characters Given Read4 Easy

    Clarify: read4 returns how many chars actually read (≤4)?

    Pattern: Buffer Management. Core: Repeatedly call read4 into a temp 4-char buffer.

    Verify: File: "abcdefgh" (8 chars)

    Trap: Not capping the copy at n-totalRead.

    Complexity: Time O(n) | Space O(1). LeetCode

  6. LC 231 - Power of Two Easy

    Clarify: Should n<=0 return false?

    Pattern: Bit Manipulation. Core: A positive power of two has exactly one bit set in binary.

    Verify: Input: n=1 -> true (2^0)

    Trap: Forgetting `n > 0` check.

    Complexity: Time O(1) | Space O(1). LeetCode

  7. LC 412 - Fizz Buzz Easy

    Clarify: Output should be array of strings?

    Pattern: Simulation + Modulo. Core: Direct simulation from 1 to n with ordered divisibility checks.

    Verify: Input: n=3 -> ["1","2","Fizz"]

    Trap: Checking `%3` before `%15` and `%5` before `%15` causes multiples of 15 to be labeled incorrectly as just "Fizz" or "Buzz".

    Complexity: Time O(n) | Space O(n). LeetCode

  8. LC 824 - Goat Latin Easy

    Clarify: Words are separated by single spaces?

    Pattern: String Simulation. Core: Process words left to right.

    Verify: Input: "I speak Goat Latin"

    Trap: Rebuilding the 'a' suffix from scratch each word with a nested loop can accidentally become O(n^2) in word count.

    Complexity: Time O(total chars) | Space O(total chars). LeetCode

  9. LC 1929 - Concatenation of Array Easy

    Clarify: Return a new array (not modify in-place)?

    Pattern: Array Construction. Core: Allocate result of size 2n and fill both halves in one pass.

    Verify: Input: nums=[1,2,1] -> [1,2,1,1,2,1]

    Trap: Using nested loops or repeated appends with expensive reallocation.

    Complexity: Time O(n) | Space O(n). LeetCode

  10. LC 5 - Longest Palindromic Substring Medium

    Clarify: Return the substring or just its length?

    Pattern: Expand Around Center. Core: Every palindrome has a CENTER.

    Verify: Input: s="babad" → Output: "bab" (or "aba", both valid)

    Trap: Forgetting even-length centers.

    Complexity: Time O(n²) | Space O(1). LeetCode

  11. LC 29 - Divide Two Integers Medium

    Clarify: Can we use *, /, % operators? (No — entire point)

    Pattern: Bit Manipulation. Core: You can't divide — so fake it with bit shifts.

    Verify: Input: dividend=15, divisor=3 → Output: 5

    Trap: Nearly every candidate forgets INT_MIN ÷ -1.

    Complexity: Time O(log²n) | Space O(1). LeetCode

  12. LC 43 - Multiply Strings Medium

    Clarify: Can we use built-in big integer multiplication? (No — simulate manually)

    Pattern: Grade-School Multiplication. Core: num1[i] × num2[j] contributes to positions [i+j] and [i+j+1] in the result array (0-indexed from left, MSB first).

    Verify: Input: num1="2", num2="3" → Output: "6"

    Trap: Propagating carries inside the inner multiplication loop instead of after.

    Complexity: Time O(m×n) | Space O(m+n). LeetCode

  13. LC 45 - Jump Game II Medium

    Clarify: Need minimum jump count only, not the actual path?

    Pattern: Greedy Layer Expansion. Core: Scan once using greedy ranges, like BFS levels over indices.

    Verify: Input: nums=[2,3,1,1,4] -> 2

    Trap: Using O(n^2) DP (`dp[i]=min(dp[j]+1)`) is correct but too slow for large inputs.

    Complexity: Time O(n) | Space O(1). LeetCode

  14. LC 50 - Pow(x, n) Medium

    Clarify: Can n be negative? (x^-n = 1/x^n)

    Pattern: Fast Exponentiation. Core: x^8 = (x^4)² = ((x^2)²)².

    Verify: Input: x=2.00000, n=10 → Output: 1024.00000

    Trap: Not casting n to long before negating.

    Complexity: Time O(log n) | Space O(log n). LeetCode

  15. LC 55 - Jump Game Medium

    Clarify: Return boolean only?

    Pattern: Greedy Farthest Reach. Core: Track the farthest index reachable so far while scanning left to right.

    Verify: Input: nums=[2,3,1,1,4] -> true

    Trap: Using recursion/DP from each index leads to O(n^2) or worse.

    Complexity: Time O(n) | Space O(1). LeetCode

  16. LC 143 - Reorder List Medium

    Clarify: In-place — no new nodes or extra list?

    Pattern: Find Middle + Reverse + Merge. Core: Decompose into three subproblems: (1) Find the middle using slow/fast pointers.

    Verify: Input: 1→2→3→4

    Trap: Missing slow.next = null (severing the list).

    Complexity: Time O(n) | Space O(1). LeetCode

  17. LC 238 - Product of Array Except Self Medium

    Clarify: Division forbidden? (Yes)

    Pattern: Prefix-Suffix Product. Core: First pass stores left product at each index.

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

    Trap: Using total product with division.

    Complexity: Time O(n) | Space O(1) extra. LeetCode

  18. LC 253 - Meeting Rooms II Medium

    Clarify: Intervals are half-open or closed? (for this problem, if one ends at time t and another starts at t, they can share room)

    Pattern: Sort + Min-Heap (End Times). Core: Sort meetings by start time.

    Verify: Input: intervals=[[0,30],[5,10],[15,20]] -> 2

    Trap: Using strict `<` instead of `<=` when checking room reuse treats back-to-back meetings as overlapping and overcounts rooms.

    Complexity: Time O(n log n) | Space O(n). LeetCode

  19. LC 419 - Battleships in a Board Medium

    Clarify: Ships are only horizontal or vertical, no L-shapes?

    Pattern: One Pass Grid Scan (Count Ship Heads). Core: Count only the TOP-LEFT cell (head) of each ship.

    Verify: Input:

    Trap: Running DFS/BFS flood fill works but usually uses extra visited space or mutates the board.

    Complexity: Time O(m×n) | Space O(1). LeetCode

  20. LC 647 - Palindromic Substrings Medium

    Clarify: Need count of all palindromic substrings, not distinct palindromic values?

    Pattern: Expand Around Center. Core: Every palindrome is centered at a character (odd length) or between characters (even length).

    Verify: Input: s="abc" -> 3

    Trap: Forgetting even centers misses palindromes like "aa" and "abba".

    Complexity: Time O(n²) | Space O(1). LeetCode

  21. LC 921 - Minimum Add to Make Parentheses Valid Medium

    Clarify: Can we add parentheses anywhere in the string?

    Pattern: Greedy Balance Counter. Core: Track open balance.

    Verify: Input: s="())" -> 1

    Trap: Using a stack is valid but unnecessary.

    Complexity: Time O(n) | Space O(1). LeetCode