LeetCode

Question 1

1249. Minimum Remove to Make Valid Parentheses
      Problem: Remove the minimum number of parentheses to make the string valid (balanced).

Answer 1

1. First Pass (Left to Right):
   
   • Initialize a stack or counter.
   • Iterate over the string:
     
     • If ‘(‘, push index to stack.
     • If ‘)’:
       
       • If stack is not empty, pop (valid pair).
       • Else, mark index for removal (unmatched ‘)’).
2. Second Pass:
   
   • Remove all unmatched ‘(‘ using indices in the stack.
3. Build Result:
   
   • Rebuild the string skipping marked indices.

Time: O(n), Space: O(n)

Question 2

408. Valid Word Abbreviation
     Problem: Check if a word matches its abbreviation (e.g., “internationalization” vs “i12iz4n”).

Answer 2

1. Use two pointers for word and abbreviation.
2. Iterate through abbreviation:
   
   • If digit, parse full number and skip that many characters in word.
   • If letter, it must match current char in word.
3. Both pointers must reach end.

Time: O(n), Space: O(1)

Question 3

314. Binary Tree Vertical Order Traversal
     Problem: Return the vertical order traversal of a binary tree.

Answer 3

1. Use BFS with queue storing (node, column index).
2. Use defaultdict to map column -> list of node values.
3. For children:
   
   • Left: column - 1
   • Right: column + 1
4. Track min and max columns.
5. Output values from min_col to max_col.

Time: O(n), Space: O(n)

Question 4

680. Valid Palindrome II
     Problem: Return true if the string can become a palindrome by deleting at most one character.

Answer 4

1. Two pointers: left and right.
2. Compare characters:
   
   • If equal: move inward.
   • If not:
     
     • Try skipping left or right and check if resulting substring is a palindrome.
3. Helper: is_palindrome(l, r).

Time: O(n), Space: O(1)

Question 5

215. Kth Largest Element in an Array
     Problem: Find the Kth largest element in an unsorted array.

Answer 5

Min-Heap Method:
1. Create min-heap of size k.
2. Iterate array:
- Push element to heap.
- If heap > k, pop smallest.
3. Top of heap is Kth largest.

Time: O(n log k), Space: O(k)

Alternate: QuickSelect (Avg O(n))

Question 6

Basic Calculator II - Evaluate the expression string containing non-negative integers, ‘+’, ‘-‘, ‘*’, ‘/’, and empty spaces. Return the result following the operator precedence.

Answer 6

1. Initialize stack, current number, and current sign (‘+’).
2. Iterate through the string:
   
   • If digit, build the number.
   • If operator or end of string:
     
     • Based on last sign, push result to stack:
       
       • ’+’ → push number
       • ’-‘ → push -number
       • ‘*’ → pop, multiply, push result
       • ’/’ → pop, divide (truncate toward zero), push result
     • Update sign and reset number.
3. Return sum of stack.

Time: O(n), Space: O(n)

Question 7

Subarray Sum Equals K - Given an array of integers and an integer k, return the total number of subarrays whose sum equals to k.

Answer 7

1. Initialize hashmap {0: 1} to count prefix sums.
2. Track running_sum and result = 0.
3. For each num in array:
   
   • Add num to running_sum.
   • If running_sum - k in hashmap, add its count to result.
   • Increment count of running_sum in hashmap.

Time: O(n), Space: O(n)

Question 8

Nested List Weight Sum - Given a nested list of integers, return the sum weighted by depth (e.g., [1,[4,[6]]] → 11 + 42 + 6*3 = 27).

Answer 8

1. Use DFS helper function with depth parameter.
2. For each element in list:
   
   • If integer, add value * depth.
   • If list, recurse with depth + 1.
3. Return total sum.

Time: O(n), Space: O(d) where d = max depth

Question 9

Lowest Common Ancestor of a Binary Tree - Given a binary tree and two nodes, return their lowest common ancestor (LCA).

Answer 9

1. Use recursive DFS.
2. Base case: if node is None or equals p or q, return node.
3. Recurse left and right.
4. If both sides return non-null, current node is LCA.
5. Else, return the non-null side.

Time: O(n), Space: O(h) where h = height of tree

Question 10

Random Pick with Weight - Given an array of positive integers representing weights, implement a method that randomly picks an index with probability proportional to its weight.

Answer 10

1. Preprocess:
   
   • Build prefix sum array of weights.
2. For pickIndex():
   
   • Generate random number in [1, total_weight].
   • Use binary search to find the first index where prefix sum >= random number.

Time: O(log n) for pickIndex, O(n) preprocessing
Space: O(n)

Question 11

Two Sum - Given an array of integers and a target, return indices of the two numbers such that they add up to the target.

Answer 11

1. Use a hashmap to store num -> index.
2. For each element:
   
   • If target - num exists in hashmap, return [index of complement, current index].
   • Otherwise, add num to hashmap.

Time: O(n), Space: O(n)

Question 12

Diameter of Binary Tree - Given the root of a binary tree, return the length of the longest path between any two nodes.

Answer 12

1. Use DFS to compute depth of each subtree.
2. For each node, update diameter = max(diameter, left_depth + right_depth).
3. Return the global max diameter.

Time: O(n), Space: O(h)

Question 13

Find Peak Element - Given an array, find a peak element where nums[i] > nums[i-1] and nums[i] > nums[i+1].

Answer 13

1. Use binary search:
   
   • If mid > mid+1, peak is in left half.
   • Else, peak is in right half.
2. Return the index when low == high.

Time: O(log n), Space: O(1)

Question 14

Lowest Common Ancestor of a Binary Tree III - Given two nodes in a binary tree with parent pointers, return their lowest common ancestor.

Answer 14

1. Use two pointers p1 and p2.
2. Traverse up until both meet:
   
   • If pointer reaches null, redirect to the other node.
3. When they meet, it’s the LCA.

Time: O(h), Space: O(1)

Question 15

Binary Tree Right Side View - Return the rightmost node at each level of a binary tree.

Answer 15

1. Use BFS with a queue.
2. At each level, record the last node encountered.
3. Append it to result list.

Time: O(n), Space: O(n)

Question 16

Simplify Path - Given a Unix-style file path, simplify it.

Answer 16

1. Split path by ‘/’.
2. Use a stack:
   
   • Ignore empty, ‘.’.
   • ’..’ → pop if not empty.
   • Else, push the directory name.
3. Join stack with ‘/’ prefix.

Time: O(n), Space: O(n)

Question 17

Shortest Path in Binary Matrix - Given a binary matrix, return the shortest path from top-left to bottom-right with only 8-directional moves on 0s.

Answer 17

1. Use BFS starting from (0, 0).
2. Track visited cells.
3. For each cell, explore all 8 directions.
4. Return path length when reaching bottom-right.

Time: O(n^2), Space: O(n^2)