Leetcode Questions Part 1
A curated list of 100 LeetCode problems for interview preparation with solution templates.
Recommended Study Order
1. Array & Hashing - Foundation concepts
- 1. Two Sum
- 217. Contains Duplicate
- 242. Valid Anagram
- 49. Group Anagrams
- 347. Top K Frequent Elements
- 238. Product of Array Except Self
- 128. Longest Consecutive Sequence
- 36. Valid Sudoku
- 271. Encode and Decode Strings
- 560. Subarray Sum Equals K
2. Two Pointers - Common pattern
- 125. Valid Palindrome
- 167. Two Sum II - Input Array Is Sorted
- 15. 3Sum
- 11. Container With Most Water
- 283. Move Zeroes
- 26. Remove Duplicates from Sorted Array
- 88. Merge Sorted Array
- 977. Squares of a Sorted Array
3. Sliding Window - Builds on two pointers
- 121. Best Time to Buy and Sell Stock
- 3. Longest Substring Without Repeating Characters
- 424. Longest Repeating Character Replacement
- 567. Permutation in String
- 209. Minimum Size Subarray Sum
- 438. Find All Anagrams in a String
- 1456. Maximum Number of Vowels in a Substring of Given Length
4. Stack - Essential data structure
- 20. Valid Parentheses
- 155. Min Stack
- 150. Evaluate Reverse Polish Notation
- 22. Generate Parentheses
- 739. Daily Temperatures
- 853. Car Fleet
- 71. Simplify Path
- 394. Decode String
5. Binary Search - Fundamental algorithm
- 704. Binary Search
- 74. Search a 2D Matrix
- 875. Koko Eating Bananas
- 153. Find Minimum in Rotated Sorted Array
- 33. Search in Rotated Sorted Array
- 981. Time Based Key-Value Store
- 35. Search Insert Position
- 278. First Bad Version
6. Linked List - Pointer manipulation
- 206. Reverse Linked List
- 21. Merge Two Sorted Lists
- 143. Reorder List
- 19. Remove Nth Node From End of List
- 138. Copy List with Random Pointer
- 2. Add Two Numbers
- 141. Linked List Cycle
- 142. Linked List Cycle II
- 287. Find the Duplicate Number
- 148. Sort List
- 234. Palindrome Linked List
- 160. Intersection of Two Linked Lists
7. Trees - Recursive thinking
- 226. Invert Binary Tree
- 104. Maximum Depth of Binary Tree
- 543. Diameter of Binary Tree
- 110. Balanced Binary Tree
- 100. Same Tree
- 572. Subtree of Another Tree
- 235. Lowest Common Ancestor of a Binary Search Tree
- 102. Binary Tree Level Order Traversal
- 199. Binary Tree Right Side View
- 1448. Count Good Nodes in Binary Tree
- 98. Validate Binary Search Tree
- 230. Kth Smallest Element in a BST
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 208. Implement Trie (Prefix Tree)
8. Heap / Priority Queue - Advanced data structure
- 703. Kth Largest Element in a Stream
- 1046. Last Stone Weight
- 973. K Closest Points to Origin
- 215. Kth Largest Element in an Array
- 621. Task Scheduler
- 355. Design Twitter
9. Backtracking - Recursion mastery
- 78. Subsets
- 39. Combination Sum
- 46. Permutations
- 90. Subsets II
- 40. Combination Sum II
- 79. Word Search
- 131. Palindrome Partitioning
- 17. Letter Combinations of a Phone Number
10. Graphs - BFS/DFS applications
- 200. Number of Islands
- 133. Clone Graph
- 695. Max Area of Island
- 417. Pacific Atlantic Water Flow
- 130. Surrounded Regions
- 994. Rotting Oranges
- 286. Walls and Gates
- 207. Course Schedule
- 210. Course Schedule II
- 684. Redundant Connection
11. Dynamic Programming - Problem decomposition
- 70. Climbing Stairs
- 746. Min Cost Climbing Stairs
- 198. House Robber
- 213. House Robber II
- 5. Longest Palindromic Substring
- 647. Palindromic Substrings
- 91. Decode Ways
- 322. Coin Change
- 152. Maximum Product Subarray
- 139. Word Break
- 300. Longest Increasing Subsequence
- 416. Partition Equal Subset Sum
- 62. Unique Paths
- 1143. Longest Common Subsequence
- 53. Maximum Subarray
- 55. Jump Game
12. Intervals - Common interview topic
- 57. Insert Interval
- 56. Merge Intervals
- 435. Non-overlapping Intervals
- 252. Meeting Rooms
- 253. Meeting Rooms II
13. Math & Geometry - Matrix operations
- 48. Rotate Image
- 54. Spiral Matrix
- 73. Set Matrix Zeroes
- 202. Happy Number
- 66. Plus One
- 50. Pow(x, n)
- 43. Multiply Strings
14. Bit Manipulation - Optimization techniques
- 136. Single Number
- 191. Number of 1 Bits
- 338. Counting Bits
- 190. Reverse Bits
- 268. Missing Number
- 371. Sum of Two Integers
Array & Hashing
1. Two Sum (Easy)
1def twoSum(nums: list[int], target: int) -> list[int]:
2 # Hash map approach - O(n) time, O(n) space
3 seen = {}
4 for i, num in enumerate(nums):
5 complement = target - num
6 if complement in seen:
7 return [seen[complement], i]
8 seen[num] = i
9 return []
217. Contains Duplicate (Easy)
1def containsDuplicate(nums: list[int]) -> bool:
2 # Set approach - O(n) time, O(n) space
3 return len(nums) != len(set(nums))
4
5 # Alternative: Hash set with early exit
6 # seen = set()
7 # for num in nums:
8 # if num in seen:
9 # return True
10 # seen.add(num)
11 # return False
242. Valid Anagram (Easy)
1def isAnagram(s: str, t: str) -> bool:
2 # Counter approach - O(n) time, O(1) space (26 letters)
3 if len(s) != len(t):
4 return False
5
6 count = {}
7 for c in s:
8 count[c] = count.get(c, 0) + 1
9 for c in t:
10 count[c] = count.get(c, 0) - 1
11 if count[c] < 0:
12 return False
13 return True
14
15 # Alternative: from collections import Counter
16 # return Counter(s) == Counter(t)
49. Group Anagrams (Medium)
1def groupAnagrams(strs: list[str]) -> list[list[str]]:
2 # Hash map with sorted string as key - O(n * k log k) time
3 from collections import defaultdict
4
5 groups = defaultdict(list)
6 for s in strs:
7 key = tuple(sorted(s))
8 groups[key].append(s)
9 return list(groups.values())
10
11 # Alternative: Use character count as key for O(n * k) time
12 # def count_key(s):
13 # count = [0] * 26
14 # for c in s:
15 # count[ord(c) - ord('a')] += 1
16 # return tuple(count)
347. Top K Frequent Elements (Medium)
1def topKFrequent(nums: list[int], k: int) -> list[int]:
2 # Bucket sort approach - O(n) time, O(n) space
3 from collections import Counter
4
5 count = Counter(nums)
6 # Bucket where index = frequency
7 buckets = [[] for _ in range(len(nums) + 1)]
8
9 for num, freq in count.items():
10 buckets[freq].append(num)
11
12 result = []
13 for i in range(len(buckets) - 1, -1, -1):
14 for num in buckets[i]:
15 result.append(num)
16 if len(result) == k:
17 return result
18 return result
238. Product of Array Except Self (Medium)
1def productExceptSelf(nums: list[int]) -> list[int]:
2 # Two-pass approach - O(n) time, O(1) extra space
3 n = len(nums)
4 result = [1] * n
5
6 # Left products
7 left_product = 1
8 for i in range(n):
9 result[i] = left_product
10 left_product *= nums[i]
11
12 # Right products
13 right_product = 1
14 for i in range(n - 1, -1, -1):
15 result[i] *= right_product
16 right_product *= nums[i]
17
18 return result
128. Longest Consecutive Sequence (Medium)
1def longestConsecutive(nums: list[int]) -> int:
2 # Hash set approach - O(n) time, O(n) space
3 num_set = set(nums)
4 longest = 0
5
6 for num in num_set:
7 # Only start counting from sequence start
8 if num - 1 not in num_set:
9 current = num
10 streak = 1
11
12 while current + 1 in num_set:
13 current += 1
14 streak += 1
15
16 longest = max(longest, streak)
17
18 return longest
36. Valid Sudoku (Medium)
1def isValidSudoku(board: list[list[str]]) -> bool:
2 # Hash sets for rows, cols, boxes - O(81) time, O(81) space
3 rows = [set() for _ in range(9)]
4 cols = [set() for _ in range(9)]
5 boxes = [set() for _ in range(9)]
6
7 for r in range(9):
8 for c in range(9):
9 if board[r][c] == '.':
10 continue
11
12 num = board[r][c]
13 box_idx = (r // 3) * 3 + (c // 3)
14
15 if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
16 return False
17
18 rows[r].add(num)
19 cols[c].add(num)
20 boxes[box_idx].add(num)
21
22 return True
271. Encode and Decode Strings (Medium)
1class Codec:
2 # Length-prefix encoding - O(n) time
3
4 def encode(self, strs: list[str]) -> str:
5 result = []
6 for s in strs:
7 result.append(f"{len(s)}#{s}")
8 return ''.join(result)
9
10 def decode(self, s: str) -> list[str]:
11 result = []
12 i = 0
13 while i < len(s):
14 j = i
15 while s[j] != '#':
16 j += 1
17 length = int(s[i:j])
18 result.append(s[j + 1:j + 1 + length])
19 i = j + 1 + length
20 return result
560. Subarray Sum Equals K (Medium)
1def subarraySum(nums: list[int], k: int) -> int:
2 # Prefix sum with hash map - O(n) time, O(n) space
3 count = 0
4 prefix_sum = 0
5 prefix_counts = {0: 1}
6
7 for num in nums:
8 prefix_sum += num
9 # Check if (prefix_sum - k) exists
10 if prefix_sum - k in prefix_counts:
11 count += prefix_counts[prefix_sum - k]
12 prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1
13
14 return count
Two Pointers
125. Valid Palindrome (Easy)
1def isPalindrome(s: str) -> bool:
2 # Two pointers - O(n) time, O(1) space
3 left, right = 0, len(s) - 1
4
5 while left < right:
6 while left < right and not s[left].isalnum():
7 left += 1
8 while left < right and not s[right].isalnum():
9 right -= 1
10
11 if s[left].lower() != s[right].lower():
12 return False
13
14 left += 1
15 right -= 1
16
17 return True
167. Two Sum II - Input Array Is Sorted (Medium)
1def twoSum(numbers: list[int], target: int) -> list[int]:
2 # Two pointers - O(n) time, O(1) space
3 left, right = 0, len(numbers) - 1
4
5 while left < right:
6 total = numbers[left] + numbers[right]
7 if total == target:
8 return [left + 1, right + 1] # 1-indexed
9 elif total < target:
10 left += 1
11 else:
12 right -= 1
13
14 return []
15. 3Sum (Medium)
1def threeSum(nums: list[int]) -> list[list[int]]:
2 # Sort + Two pointers - O(n^2) time, O(1) extra space
3 nums.sort()
4 result = []
5
6 for i in range(len(nums) - 2):
7 # Skip duplicates for first element
8 if i > 0 and nums[i] == nums[i - 1]:
9 continue
10
11 left, right = i + 1, len(nums) - 1
12 while left < right:
13 total = nums[i] + nums[left] + nums[right]
14 if total == 0:
15 result.append([nums[i], nums[left], nums[right]])
16 # Skip duplicates
17 while left < right and nums[left] == nums[left + 1]:
18 left += 1
19 while left < right and nums[right] == nums[right - 1]:
20 right -= 1
21 left += 1
22 right -= 1
23 elif total < 0:
24 left += 1
25 else:
26 right -= 1
27
28 return result
11. Container With Most Water (Medium)
1def maxArea(height: list[int]) -> int:
2 # Two pointers - O(n) time, O(1) space
3 left, right = 0, len(height) - 1
4 max_water = 0
5
6 while left < right:
7 width = right - left
8 h = min(height[left], height[right])
9 max_water = max(max_water, width * h)
10
11 # Move the shorter line inward
12 if height[left] < height[right]:
13 left += 1
14 else:
15 right -= 1
16
17 return max_water
283. Move Zeroes (Easy)
1def moveZeroes(nums: list[int]) -> None:
2 # Two pointers (in-place) - O(n) time, O(1) space
3 insert_pos = 0
4
5 for i in range(len(nums)):
6 if nums[i] != 0:
7 nums[insert_pos], nums[i] = nums[i], nums[insert_pos]
8 insert_pos += 1
26. Remove Duplicates from Sorted Array (Easy)
1def removeDuplicates(nums: list[int]) -> int:
2 # Two pointers - O(n) time, O(1) space
3 if not nums:
4 return 0
5
6 insert_pos = 1
7 for i in range(1, len(nums)):
8 if nums[i] != nums[i - 1]:
9 nums[insert_pos] = nums[i]
10 insert_pos += 1
11
12 return insert_pos
88. Merge Sorted Array (Easy)
1def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
2 # Three pointers (from end) - O(m+n) time, O(1) space
3 p1, p2, p = m - 1, n - 1, m + n - 1
4
5 while p2 >= 0:
6 if p1 >= 0 and nums1[p1] > nums2[p2]:
7 nums1[p] = nums1[p1]
8 p1 -= 1
9 else:
10 nums1[p] = nums2[p2]
11 p2 -= 1
12 p -= 1
977. Squares of a Sorted Array (Easy)
1def sortedSquares(nums: list[int]) -> list[int]:
2 # Two pointers - O(n) time, O(n) space
3 n = len(nums)
4 result = [0] * n
5 left, right = 0, n - 1
6 pos = n - 1
7
8 while left <= right:
9 if abs(nums[left]) > abs(nums[right]):
10 result[pos] = nums[left] ** 2
11 left += 1
12 else:
13 result[pos] = nums[right] ** 2
14 right -= 1
15 pos -= 1
16
17 return result
Sliding Window
121. Best Time to Buy and Sell Stock (Easy)
1def maxProfit(prices: list[int]) -> int:
2 # Track min price - O(n) time, O(1) space
3 min_price = float('inf')
4 max_profit = 0
5
6 for price in prices:
7 min_price = min(min_price, price)
8 max_profit = max(max_profit, price - min_price)
9
10 return max_profit
3. Longest Substring Without Repeating Characters (Medium)
1def lengthOfLongestSubstring(s: str) -> int:
2 # Sliding window with hash map - O(n) time, O(min(n, 26)) space
3 char_index = {}
4 max_len = 0
5 left = 0
6
7 for right, char in enumerate(s):
8 if char in char_index and char_index[char] >= left:
9 left = char_index[char] + 1
10 char_index[char] = right
11 max_len = max(max_len, right - left + 1)
12
13 return max_len
424. Longest Repeating Character Replacement (Medium)
1def characterReplacement(s: str, k: int) -> int:
2 # Sliding window - O(n) time, O(26) space
3 count = {}
4 max_freq = 0
5 max_len = 0
6 left = 0
7
8 for right in range(len(s)):
9 count[s[right]] = count.get(s[right], 0) + 1
10 max_freq = max(max_freq, count[s[right]])
11
12 # Window size - max freq > k means too many replacements
13 while (right - left + 1) - max_freq > k:
14 count[s[left]] -= 1
15 left += 1
16
17 max_len = max(max_len, right - left + 1)
18
19 return max_len
567. Permutation in String (Medium)
1def checkInclusion(s1: str, s2: str) -> bool:
2 # Sliding window with frequency count - O(n) time, O(26) space
3 if len(s1) > len(s2):
4 return False
5
6 s1_count = [0] * 26
7 window_count = [0] * 26
8
9 for c in s1:
10 s1_count[ord(c) - ord('a')] += 1
11
12 for i, c in enumerate(s2):
13 window_count[ord(c) - ord('a')] += 1
14
15 # Remove leftmost char when window exceeds s1 length
16 if i >= len(s1):
17 window_count[ord(s2[i - len(s1)]) - ord('a')] -= 1
18
19 if window_count == s1_count:
20 return True
21
22 return False
209. Minimum Size Subarray Sum (Medium)
1def minSubArrayLen(target: int, nums: list[int]) -> int:
2 # Sliding window - O(n) time, O(1) space
3 min_len = float('inf')
4 left = 0
5 current_sum = 0
6
7 for right in range(len(nums)):
8 current_sum += nums[right]
9
10 while current_sum >= target:
11 min_len = min(min_len, right - left + 1)
12 current_sum -= nums[left]
13 left += 1
14
15 return min_len if min_len != float('inf') else 0
438. Find All Anagrams in a String (Medium)
1def findAnagrams(s: str, p: str) -> list[int]:
2 # Sliding window - O(n) time, O(26) space
3 if len(p) > len(s):
4 return []
5
6 p_count = [0] * 26
7 window_count = [0] * 26
8 result = []
9
10 for c in p:
11 p_count[ord(c) - ord('a')] += 1
12
13 for i in range(len(s)):
14 window_count[ord(s[i]) - ord('a')] += 1
15
16 if i >= len(p):
17 window_count[ord(s[i - len(p)]) - ord('a')] -= 1
18
19 if window_count == p_count:
20 result.append(i - len(p) + 1)
21
22 return result
1456. Maximum Number of Vowels in a Substring of Given Length (Medium)
1def maxVowels(s: str, k: int) -> int:
2 # Sliding window - O(n) time, O(1) space
3 vowels = set('aeiou')
4 count = sum(1 for c in s[:k] if c in vowels)
5 max_count = count
6
7 for i in range(k, len(s)):
8 if s[i] in vowels:
9 count += 1
10 if s[i - k] in vowels:
11 count -= 1
12 max_count = max(max_count, count)
13
14 return max_count
Stack
20. Valid Parentheses (Easy)
1def isValid(s: str) -> bool:
2 # Stack approach - O(n) time, O(n) space
3 stack = []
4 pairs = {')': '(', '}': '{', ']': '['}
5
6 for char in s:
7 if char in pairs:
8 if not stack or stack[-1] != pairs[char]:
9 return False
10 stack.pop()
11 else:
12 stack.append(char)
13
14 return len(stack) == 0
155. Min Stack (Medium)
1class MinStack:
2 # Two stacks approach - O(1) for all operations
3
4 def __init__(self):
5 self.stack = []
6 self.min_stack = []
7
8 def push(self, val: int) -> None:
9 self.stack.append(val)
10 min_val = min(val, self.min_stack[-1] if self.min_stack else val)
11 self.min_stack.append(min_val)
12
13 def pop(self) -> None:
14 self.stack.pop()
15 self.min_stack.pop()
16
17 def top(self) -> int:
18 return self.stack[-1]
19
20 def getMin(self) -> int:
21 return self.min_stack[-1]
150. Evaluate Reverse Polish Notation (Medium)
1def evalRPN(tokens: list[str]) -> int:
2 # Stack approach - O(n) time, O(n) space
3 stack = []
4 operators = {
5 '+': lambda a, b: a + b,
6 '-': lambda a, b: a - b,
7 '*': lambda a, b: a * b,
8 '/': lambda a, b: int(a / b) # Truncate toward zero
9 }
10
11 for token in tokens:
12 if token in operators:
13 b, a = stack.pop(), stack.pop()
14 stack.append(operators[token](a, b))
15 else:
16 stack.append(int(token))
17
18 return stack[0]
22. Generate Parentheses (Medium)
1def generateParenthesis(n: int) -> list[str]:
2 # Backtracking - O(4^n / sqrt(n)) time (Catalan number)
3 result = []
4
5 def backtrack(current: str, open_count: int, close_count: int):
6 if len(current) == 2 * n:
7 result.append(current)
8 return
9
10 if open_count < n:
11 backtrack(current + '(', open_count + 1, close_count)
12 if close_count < open_count:
13 backtrack(current + ')', open_count, close_count + 1)
14
15 backtrack('', 0, 0)
16 return result
739. Daily Temperatures (Medium)
1def dailyTemperatures(temperatures: list[int]) -> list[int]:
2 # Monotonic decreasing stack - O(n) time, O(n) space
3 n = len(temperatures)
4 result = [0] * n
5 stack = [] # Store indices
6
7 for i, temp in enumerate(temperatures):
8 while stack and temperatures[stack[-1]] < temp:
9 prev_idx = stack.pop()
10 result[prev_idx] = i - prev_idx
11 stack.append(i)
12
13 return result
853. Car Fleet (Medium)
1def carFleet(target: int, position: list[int], speed: list[int]) -> int:
2 # Sort by position + Stack - O(n log n) time, O(n) space
3 cars = sorted(zip(position, speed), reverse=True)
4 stack = []
5
6 for pos, spd in cars:
7 time = (target - pos) / spd
8 if not stack or time > stack[-1]:
9 stack.append(time)
10
11 return len(stack)
71. Simplify Path (Medium)
1def simplifyPath(path: str) -> str:
2 # Stack approach - O(n) time, O(n) space
3 stack = []
4 parts = path.split('/')
5
6 for part in parts:
7 if part == '..':
8 if stack:
9 stack.pop()
10 elif part and part != '.':
11 stack.append(part)
12
13 return '/' + '/'.join(stack)
394. Decode String (Medium)
1def decodeString(s: str) -> str:
2 # Stack approach - O(n) time, O(n) space
3 stack = []
4 current_num = 0
5 current_str = ''
6
7 for char in s:
8 if char.isdigit():
9 current_num = current_num * 10 + int(char)
10 elif char == '[':
11 stack.append((current_str, current_num))
12 current_str = ''
13 current_num = 0
14 elif char == ']':
15 prev_str, num = stack.pop()
16 current_str = prev_str + current_str * num
17 else:
18 current_str += char
19
20 return current_str
Binary Search
704. Binary Search (Easy)
1def search(nums: list[int], target: int) -> int:
2 # Classic binary search - O(log n) time, O(1) space
3 left, right = 0, len(nums) - 1
4
5 while left <= right:
6 mid = left + (right - left) // 2
7 if nums[mid] == target:
8 return mid
9 elif nums[mid] < target:
10 left = mid + 1
11 else:
12 right = mid - 1
13
14 return -1
74. Search a 2D Matrix (Medium)
1def searchMatrix(matrix: list[list[int]], target: int) -> bool:
2 # Treat as 1D array - O(log(m*n)) time, O(1) space
3 if not matrix:
4 return False
5
6 m, n = len(matrix), len(matrix[0])
7 left, right = 0, m * n - 1
8
9 while left <= right:
10 mid = left + (right - left) // 2
11 row, col = mid // n, mid % n
12 val = matrix[row][col]
13
14 if val == target:
15 return True
16 elif val < target:
17 left = mid + 1
18 else:
19 right = mid - 1
20
21 return False
875. Koko Eating Bananas (Medium)
1def minEatingSpeed(piles: list[int], h: int) -> int:
2 # Binary search on answer - O(n log m) time, O(1) space
3 import math
4
5 def can_finish(k):
6 hours = sum(math.ceil(pile / k) for pile in piles)
7 return hours <= h
8
9 left, right = 1, max(piles)
10
11 while left < right:
12 mid = left + (right - left) // 2
13 if can_finish(mid):
14 right = mid
15 else:
16 left = mid + 1
17
18 return left
153. Find Minimum in Rotated Sorted Array (Medium)
1def findMin(nums: list[int]) -> int:
2 # Binary search - O(log n) time, O(1) space
3 left, right = 0, len(nums) - 1
4
5 while left < right:
6 mid = left + (right - left) // 2
7 if nums[mid] > nums[right]:
8 # Min is in right half
9 left = mid + 1
10 else:
11 # Min is in left half (including mid)
12 right = mid
13
14 return nums[left]
33. Search in Rotated Sorted Array (Medium)
1def search(nums: list[int], target: int) -> int:
2 # Modified binary search - O(log n) time, O(1) space
3 left, right = 0, len(nums) - 1
4
5 while left <= right:
6 mid = left + (right - left) // 2
7
8 if nums[mid] == target:
9 return mid
10
11 # Left half is sorted
12 if nums[left] <= nums[mid]:
13 if nums[left] <= target < nums[mid]:
14 right = mid - 1
15 else:
16 left = mid + 1
17 # Right half is sorted
18 else:
19 if nums[mid] < target <= nums[right]:
20 left = mid + 1
21 else:
22 right = mid - 1
23
24 return -1
981. Time Based Key-Value Store (Medium)
1class TimeMap:
2 # Hash map + Binary search - O(1) set, O(log n) get
3
4 def __init__(self):
5 self.store = {} # key -> [(timestamp, value)]
6
7 def set(self, key: str, value: str, timestamp: int) -> None:
8 if key not in self.store:
9 self.store[key] = []
10 self.store[key].append((timestamp, value))
11
12 def get(self, key: str, timestamp: int) -> str:
13 if key not in self.store:
14 return ""
15
16 values = self.store[key]
17 left, right = 0, len(values) - 1
18 result = ""
19
20 while left <= right:
21 mid = left + (right - left) // 2
22 if values[mid][0] <= timestamp:
23 result = values[mid][1]
24 left = mid + 1
25 else:
26 right = mid - 1
27
28 return result
35. Search Insert Position (Easy)
1def searchInsert(nums: list[int], target: int) -> int:
2 # Binary search - O(log n) time, O(1) space
3 left, right = 0, len(nums)
4
5 while left < right:
6 mid = left + (right - left) // 2
7 if nums[mid] < target:
8 left = mid + 1
9 else:
10 right = mid
11
12 return left
278. First Bad Version (Easy)
1def firstBadVersion(n: int) -> int:
2 # Binary search - O(log n) time, O(1) space
3 # isBadVersion(version) is provided API
4 left, right = 1, n
5
6 while left < right:
7 mid = left + (right - left) // 2
8 if isBadVersion(mid):
9 right = mid
10 else:
11 left = mid + 1
12
13 return left
Linked List
206. Reverse Linked List (Easy)
1def reverseList(head: ListNode) -> ListNode:
2 # Iterative - O(n) time, O(1) space
3 prev, curr = None, head
4
5 while curr:
6 next_temp = curr.next
7 curr.next = prev
8 prev = curr
9 curr = next_temp
10
11 return prev
12
13 # Recursive approach:
14 # def reverseList(head):
15 # if not head or not head.next:
16 # return head
17 # new_head = reverseList(head.next)
18 # head.next.next = head
19 # head.next = None
20 # return new_head
21. Merge Two Sorted Lists (Easy)
1def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
2 # Iterative - O(n+m) time, O(1) space
3 dummy = ListNode(0)
4 curr = dummy
5
6 while list1 and list2:
7 if list1.val <= list2.val:
8 curr.next = list1
9 list1 = list1.next
10 else:
11 curr.next = list2
12 list2 = list2.next
13 curr = curr.next
14
15 curr.next = list1 or list2
16 return dummy.next
143. Reorder List (Medium)
1def reorderList(head: ListNode) -> None:
2 # Find middle + Reverse + Merge - O(n) time, O(1) space
3 if not head or not head.next:
4 return
5
6 # Find middle
7 slow, fast = head, head
8 while fast.next and fast.next.next:
9 slow = slow.next
10 fast = fast.next.next
11
12 # Reverse second half
13 prev, curr = None, slow.next
14 slow.next = None
15 while curr:
16 next_temp = curr.next
17 curr.next = prev
18 prev = curr
19 curr = next_temp
20
21 # Merge two halves
22 first, second = head, prev
23 while second:
24 tmp1, tmp2 = first.next, second.next
25 first.next = second
26 second.next = tmp1
27 first, second = tmp1, tmp2
19. Remove Nth Node From End of List (Medium)
1def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
2 # Two pointers - O(n) time, O(1) space
3 dummy = ListNode(0, head)
4 fast = slow = dummy
5
6 # Move fast n+1 steps ahead
7 for _ in range(n + 1):
8 fast = fast.next
9
10 # Move both until fast reaches end
11 while fast:
12 fast = fast.next
13 slow = slow.next
14
15 slow.next = slow.next.next
16 return dummy.next
138. Copy List with Random Pointer (Medium)
1def copyRandomList(head: 'Node') -> 'Node':
2 # Hash map approach - O(n) time, O(n) space
3 if not head:
4 return None
5
6 old_to_new = {}
7
8 # First pass: create all nodes
9 curr = head
10 while curr:
11 old_to_new[curr] = Node(curr.val)
12 curr = curr.next
13
14 # Second pass: set next and random pointers
15 curr = head
16 while curr:
17 old_to_new[curr].next = old_to_new.get(curr.next)
18 old_to_new[curr].random = old_to_new.get(curr.random)
19 curr = curr.next
20
21 return old_to_new[head]
2. Add Two Numbers (Medium)
1def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
2 # Elementary math - O(max(m,n)) time, O(max(m,n)) space
3 dummy = ListNode(0)
4 curr = dummy
5 carry = 0
6
7 while l1 or l2 or carry:
8 val1 = l1.val if l1 else 0
9 val2 = l2.val if l2 else 0
10
11 total = val1 + val2 + carry
12 carry = total // 10
13 curr.next = ListNode(total % 10)
14 curr = curr.next
15
16 l1 = l1.next if l1 else None
17 l2 = l2.next if l2 else None
18
19 return dummy.next
141. Linked List Cycle (Easy)
1def hasCycle(head: ListNode) -> bool:
2 # Floyd's Cycle Detection - O(n) time, O(1) space
3 slow = fast = head
4
5 while fast and fast.next:
6 slow = slow.next
7 fast = fast.next.next
8 if slow == fast:
9 return True
10
11 return False
142. Linked List Cycle II (Medium)
1def detectCycle(head: ListNode) -> ListNode:
2 # Floyd's algorithm - O(n) time, O(1) space
3 slow = fast = head
4
5 # Detect cycle
6 while fast and fast.next:
7 slow = slow.next
8 fast = fast.next.next
9 if slow == fast:
10 break
11 else:
12 return None
13
14 # Find cycle start
15 slow = head
16 while slow != fast:
17 slow = slow.next
18 fast = fast.next
19
20 return slow
287. Find the Duplicate Number (Medium)
1def findDuplicate(nums: list[int]) -> int:
2 # Floyd's Cycle Detection - O(n) time, O(1) space
3 slow = fast = nums[0]
4
5 # Find intersection point
6 while True:
7 slow = nums[slow]
8 fast = nums[nums[fast]]
9 if slow == fast:
10 break
11
12 # Find cycle start
13 slow = nums[0]
14 while slow != fast:
15 slow = nums[slow]
16 fast = nums[fast]
17
18 return slow
148. Sort List (Medium)
1def sortList(head: ListNode) -> ListNode:
2 # Merge sort - O(n log n) time, O(log n) space
3 if not head or not head.next:
4 return head
5
6 # Find middle
7 slow, fast = head, head.next
8 while fast and fast.next:
9 slow = slow.next
10 fast = fast.next.next
11
12 mid = slow.next
13 slow.next = None
14
15 # Recursively sort both halves
16 left = sortList(head)
17 right = sortList(mid)
18
19 # Merge sorted halves
20 dummy = ListNode(0)
21 curr = dummy
22 while left and right:
23 if left.val < right.val:
24 curr.next = left
25 left = left.next
26 else:
27 curr.next = right
28 right = right.next
29 curr = curr.next
30 curr.next = left or right
31
32 return dummy.next
234. Palindrome Linked List (Easy)
1def isPalindrome(head: ListNode) -> bool:
2 # Reverse second half - O(n) time, O(1) space
3 # Find middle
4 slow = fast = head
5 while fast and fast.next:
6 slow = slow.next
7 fast = fast.next.next
8
9 # Reverse second half
10 prev = None
11 while slow:
12 next_temp = slow.next
13 slow.next = prev
14 prev = slow
15 slow = next_temp
16
17 # Compare
18 left, right = head, prev
19 while right:
20 if left.val != right.val:
21 return False
22 left = left.next
23 right = right.next
24
25 return True
160. Intersection of Two Linked Lists (Easy)
1def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
2 # Two pointers - O(n+m) time, O(1) space
3 if not headA or not headB:
4 return None
5
6 pA, pB = headA, headB
7
8 while pA != pB:
9 pA = pA.next if pA else headB
10 pB = pB.next if pB else headA
11
12 return pA
Trees
226. Invert Binary Tree (Easy)
1def invertTree(root: TreeNode) -> TreeNode:
2 # Recursive DFS - O(n) time, O(h) space
3 if not root:
4 return None
5
6 root.left, root.right = root.right, root.left
7 invertTree(root.left)
8 invertTree(root.right)
9
10 return root
104. Maximum Depth of Binary Tree (Easy)
1def maxDepth(root: TreeNode) -> int:
2 # Recursive DFS - O(n) time, O(h) space
3 if not root:
4 return 0
5 return 1 + max(maxDepth(root.left), maxDepth(root.right))
543. Diameter of Binary Tree (Easy)
1def diameterOfBinaryTree(root: TreeNode) -> int:
2 # DFS with global max - O(n) time, O(h) space
3 diameter = 0
4
5 def depth(node):
6 nonlocal diameter
7 if not node:
8 return 0
9
10 left = depth(node.left)
11 right = depth(node.right)
12 diameter = max(diameter, left + right)
13
14 return 1 + max(left, right)
15
16 depth(root)
17 return diameter
110. Balanced Binary Tree (Easy)
1def isBalanced(root: TreeNode) -> bool:
2 # DFS with height check - O(n) time, O(h) space
3 def check(node):
4 if not node:
5 return 0
6
7 left = check(node.left)
8 right = check(node.right)
9
10 if left == -1 or right == -1 or abs(left - right) > 1:
11 return -1
12
13 return 1 + max(left, right)
14
15 return check(root) != -1
100. Same Tree (Easy)
1def isSameTree(p: TreeNode, q: TreeNode) -> bool:
2 # Recursive comparison - O(n) time, O(h) space
3 if not p and not q:
4 return True
5 if not p or not q or p.val != q.val:
6 return False
7 return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
572. Subtree of Another Tree (Easy)
1def isSubtree(root: TreeNode, subRoot: TreeNode) -> bool:
2 # DFS + Same tree check - O(m*n) time, O(h) space
3 def isSame(p, q):
4 if not p and not q:
5 return True
6 if not p or not q or p.val != q.val:
7 return False
8 return isSame(p.left, q.left) and isSame(p.right, q.right)
9
10 if not root:
11 return False
12 if isSame(root, subRoot):
13 return True
14 return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)
235. Lowest Common Ancestor of a Binary Search Tree (Medium)
1def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
2 # BST property - O(h) time, O(1) space
3 while root:
4 if p.val < root.val and q.val < root.val:
5 root = root.left
6 elif p.val > root.val and q.val > root.val:
7 root = root.right
8 else:
9 return root
102. Binary Tree Level Order Traversal (Medium)
1def levelOrder(root: TreeNode) -> list[list[int]]:
2 # BFS - O(n) time, O(n) space
3 if not root:
4 return []
5
6 from collections import deque
7 result = []
8 queue = deque([root])
9
10 while queue:
11 level = []
12 for _ in range(len(queue)):
13 node = queue.popleft()
14 level.append(node.val)
15 if node.left:
16 queue.append(node.left)
17 if node.right:
18 queue.append(node.right)
19 result.append(level)
20
21 return result
199. Binary Tree Right Side View (Medium)
1def rightSideView(root: TreeNode) -> list[int]:
2 # BFS, take last of each level - O(n) time, O(n) space
3 if not root:
4 return []
5
6 from collections import deque
7 result = []
8 queue = deque([root])
9
10 while queue:
11 level_size = len(queue)
12 for i in range(level_size):
13 node = queue.popleft()
14 if i == level_size - 1:
15 result.append(node.val)
16 if node.left:
17 queue.append(node.left)
18 if node.right:
19 queue.append(node.right)
20
21 return result
1448. Count Good Nodes in Binary Tree (Medium)
1def goodNodes(root: TreeNode) -> int:
2 # DFS with max tracking - O(n) time, O(h) space
3 def dfs(node, max_val):
4 if not node:
5 return 0
6
7 count = 1 if node.val >= max_val else 0
8 max_val = max(max_val, node.val)
9
10 count += dfs(node.left, max_val)
11 count += dfs(node.right, max_val)
12
13 return count
14
15 return dfs(root, root.val)
98. Validate Binary Search Tree (Medium)
1def isValidBST(root: TreeNode) -> bool:
2 # DFS with bounds - O(n) time, O(h) space
3 def validate(node, min_val, max_val):
4 if not node:
5 return True
6
7 if node.val <= min_val or node.val >= max_val:
8 return False
9
10 return (validate(node.left, min_val, node.val) and
11 validate(node.right, node.val, max_val))
12
13 return validate(root, float('-inf'), float('inf'))
230. Kth Smallest Element in a BST (Medium)
1def kthSmallest(root: TreeNode, k: int) -> int:
2 # Inorder traversal - O(h + k) time, O(h) space
3 stack = []
4 curr = root
5 count = 0
6
7 while stack or curr:
8 while curr:
9 stack.append(curr)
10 curr = curr.left
11
12 curr = stack.pop()
13 count += 1
14 if count == k:
15 return curr.val
16
17 curr = curr.right
105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
1def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode:
2 # Recursive with index map - O(n) time, O(n) space
3 inorder_map = {val: idx for idx, val in enumerate(inorder)}
4
5 def build(pre_start, pre_end, in_start, in_end):
6 if pre_start > pre_end:
7 return None
8
9 root_val = preorder[pre_start]
10 root = TreeNode(root_val)
11
12 in_root = inorder_map[root_val]
13 left_size = in_root - in_start
14
15 root.left = build(pre_start + 1, pre_start + left_size,
16 in_start, in_root - 1)
17 root.right = build(pre_start + left_size + 1, pre_end,
18 in_root + 1, in_end)
19
20 return root
21
22 return build(0, len(preorder) - 1, 0, len(inorder) - 1)
208. Implement Trie (Prefix Tree) (Medium)
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end = False
5
6class Trie:
7 def __init__(self):
8 self.root = TrieNode()
9
10 def insert(self, word: str) -> None:
11 # O(n) time, O(n) space
12 node = self.root
13 for char in word:
14 if char not in node.children:
15 node.children[char] = TrieNode()
16 node = node.children[char]
17 node.is_end = True
18
19 def search(self, word: str) -> bool:
20 # O(n) time, O(1) space
21 node = self.root
22 for char in word:
23 if char not in node.children:
24 return False
25 node = node.children[char]
26 return node.is_end
27
28 def startsWith(self, prefix: str) -> bool:
29 # O(n) time, O(1) space
30 node = self.root
31 for char in prefix:
32 if char not in node.children:
33 return False
34 node = node.children[char]
35 return True
Heap / Priority Queue
703. Kth Largest Element in a Stream (Easy)
1import heapq
2
3class KthLargest:
4 # Min heap of size k - O(log k) add, O(n log k) init
5
6 def __init__(self, k: int, nums: list[int]):
7 self.k = k
8 self.heap = nums
9 heapq.heapify(self.heap)
10 while len(self.heap) > k:
11 heapq.heappop(self.heap)
12
13 def add(self, val: int) -> int:
14 heapq.heappush(self.heap, val)
15 if len(self.heap) > self.k:
16 heapq.heappop(self.heap)
17 return self.heap[0]
1046. Last Stone Weight (Easy)
1def lastStoneWeight(stones: list[int]) -> int:
2 # Max heap - O(n log n) time, O(n) space
3 import heapq
4
5 # Python has min heap, so negate values
6 heap = [-s for s in stones]
7 heapq.heapify(heap)
8
9 while len(heap) > 1:
10 first = -heapq.heappop(heap)
11 second = -heapq.heappop(heap)
12 if first != second:
13 heapq.heappush(heap, -(first - second))
14
15 return -heap[0] if heap else 0
973. K Closest Points to Origin (Medium)
1def kClosest(points: list[list[int]], k: int) -> list[list[int]]:
2 # Max heap of size k - O(n log k) time, O(k) space
3 import heapq
4
5 # Use max heap (negate distance)
6 heap = []
7 for x, y in points:
8 dist = -(x * x + y * y)
9 if len(heap) < k:
10 heapq.heappush(heap, (dist, x, y))
11 elif dist > heap[0][0]:
12 heapq.heapreplace(heap, (dist, x, y))
13
14 return [[x, y] for (_, x, y) in heap]
215. Kth Largest Element in an Array (Medium)
1def findKthLargest(nums: list[int], k: int) -> int:
2 # Min heap of size k - O(n log k) time, O(k) space
3 import heapq
4
5 heap = []
6 for num in nums:
7 heapq.heappush(heap, num)
8 if len(heap) > k:
9 heapq.heappop(heap)
10
11 return heap[0]
12
13 # Alternative: Quickselect - O(n) average time
621. Task Scheduler (Medium)
1def leastInterval(tasks: list[str], n: int) -> int:
2 # Greedy with max heap - O(m) time where m = total tasks
3 import heapq
4 from collections import Counter
5
6 count = Counter(tasks)
7 max_heap = [-c for c in count.values()]
8 heapq.heapify(max_heap)
9
10 time = 0
11 queue = [] # (available_time, count)
12
13 while max_heap or queue:
14 time += 1
15
16 if max_heap:
17 cnt = heapq.heappop(max_heap) + 1 # Process one task
18 if cnt < 0:
19 queue.append((time + n, cnt))
20
21 if queue and queue[0][0] == time:
22 heapq.heappush(max_heap, queue.pop(0)[1])
23
24 return time
355. Design Twitter (Medium)
1import heapq
2from collections import defaultdict
3
4class Twitter:
5 def __init__(self):
6 self.time = 0
7 self.tweets = defaultdict(list) # userId -> [(time, tweetId)]
8 self.following = defaultdict(set) # userId -> set of followeeIds
9
10 def postTweet(self, userId: int, tweetId: int) -> None:
11 self.tweets[userId].append((self.time, tweetId))
12 self.time -= 1 # Decrement for max heap behavior
13
14 def getNewsFeed(self, userId: int) -> list[int]:
15 # Merge k sorted lists with heap
16 heap = []
17 self.following[userId].add(userId)
18
19 for followeeId in self.following[userId]:
20 if self.tweets[followeeId]:
21 idx = len(self.tweets[followeeId]) - 1
22 time, tweetId = self.tweets[followeeId][idx]
23 heap.append((time, tweetId, followeeId, idx))
24
25 heapq.heapify(heap)
26 result = []
27
28 while heap and len(result) < 10:
29 time, tweetId, followeeId, idx = heapq.heappop(heap)
30 result.append(tweetId)
31 if idx > 0:
32 idx -= 1
33 time, tweetId = self.tweets[followeeId][idx]
34 heapq.heappush(heap, (time, tweetId, followeeId, idx))
35
36 return result
37
38 def follow(self, followerId: int, followeeId: int) -> None:
39 self.following[followerId].add(followeeId)
40
41 def unfollow(self, followerId: int, followeeId: int) -> None:
42 self.following[followerId].discard(followeeId)
Backtracking
78. Subsets (Medium)
1def subsets(nums: list[int]) -> list[list[int]]:
2 # Backtracking - O(n * 2^n) time, O(n) space
3 result = []
4
5 def backtrack(start, current):
6 result.append(current[:])
7
8 for i in range(start, len(nums)):
9 current.append(nums[i])
10 backtrack(i + 1, current)
11 current.pop()
12
13 backtrack(0, [])
14 return result
39. Combination Sum (Medium)
1def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
2 # Backtracking - O(n^(target/min)) time
3 result = []
4
5 def backtrack(start, current, remaining):
6 if remaining == 0:
7 result.append(current[:])
8 return
9 if remaining < 0:
10 return
11
12 for i in range(start, len(candidates)):
13 current.append(candidates[i])
14 backtrack(i, current, remaining - candidates[i]) # Can reuse same element
15 current.pop()
16
17 backtrack(0, [], target)
18 return result
46. Permutations (Medium)
1def permute(nums: list[int]) -> list[list[int]]:
2 # Backtracking - O(n! * n) time, O(n) space
3 result = []
4
5 def backtrack(current):
6 if len(current) == len(nums):
7 result.append(current[:])
8 return
9
10 for num in nums:
11 if num not in current:
12 current.append(num)
13 backtrack(current)
14 current.pop()
15
16 backtrack([])
17 return result
90. Subsets II (Medium)
1def subsetsWithDup(nums: list[int]) -> list[list[int]]:
2 # Backtracking with skip duplicates - O(n * 2^n) time
3 nums.sort()
4 result = []
5
6 def backtrack(start, current):
7 result.append(current[:])
8
9 for i in range(start, len(nums)):
10 # Skip duplicates
11 if i > start and nums[i] == nums[i - 1]:
12 continue
13 current.append(nums[i])
14 backtrack(i + 1, current)
15 current.pop()
16
17 backtrack(0, [])
18 return result
40. Combination Sum II (Medium)
1def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
2 # Backtracking with skip duplicates - O(2^n) time
3 candidates.sort()
4 result = []
5
6 def backtrack(start, current, remaining):
7 if remaining == 0:
8 result.append(current[:])
9 return
10
11 for i in range(start, len(candidates)):
12 if candidates[i] > remaining:
13 break
14 if i > start and candidates[i] == candidates[i - 1]:
15 continue
16
17 current.append(candidates[i])
18 backtrack(i + 1, current, remaining - candidates[i])
19 current.pop()
20
21 backtrack(0, [], target)
22 return result
79. Word Search (Medium)
1def exist(board: list[list[str]], word: str) -> bool:
2 # DFS backtracking - O(m*n*4^L) time
3 rows, cols = len(board), len(board[0])
4
5 def dfs(r, c, idx):
6 if idx == len(word):
7 return True
8 if (r < 0 or r >= rows or c < 0 or c >= cols or
9 board[r][c] != word[idx]):
10 return False
11
12 # Mark visited
13 temp = board[r][c]
14 board[r][c] = '#'
15
16 found = (dfs(r + 1, c, idx + 1) or
17 dfs(r - 1, c, idx + 1) or
18 dfs(r, c + 1, idx + 1) or
19 dfs(r, c - 1, idx + 1))
20
21 # Restore
22 board[r][c] = temp
23 return found
24
25 for r in range(rows):
26 for c in range(cols):
27 if dfs(r, c, 0):
28 return True
29 return False
131. Palindrome Partitioning (Medium)
1def partition(s: str) -> list[list[str]]:
2 # Backtracking - O(n * 2^n) time
3 result = []
4
5 def is_palindrome(sub):
6 return sub == sub[::-1]
7
8 def backtrack(start, current):
9 if start == len(s):
10 result.append(current[:])
11 return
12
13 for end in range(start + 1, len(s) + 1):
14 substring = s[start:end]
15 if is_palindrome(substring):
16 current.append(substring)
17 backtrack(end, current)
18 current.pop()
19
20 backtrack(0, [])
21 return result
17. Letter Combinations of a Phone Number (Medium)
1def letterCombinations(digits: str) -> list[str]:
2 # Backtracking - O(4^n * n) time
3 if not digits:
4 return []
5
6 phone = {
7 '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
8 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
9 }
10
11 result = []
12
13 def backtrack(idx, current):
14 if idx == len(digits):
15 result.append(''.join(current))
16 return
17
18 for char in phone[digits[idx]]:
19 current.append(char)
20 backtrack(idx + 1, current)
21 current.pop()
22
23 backtrack(0, [])
24 return result
Graphs
200. Number of Islands (Medium)
1def numIslands(grid: list[list[str]]) -> int:
2 # DFS - O(m*n) time, O(m*n) space
3 if not grid:
4 return 0
5
6 rows, cols = len(grid), len(grid[0])
7 count = 0
8
9 def dfs(r, c):
10 if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
11 return
12 grid[r][c] = '0' # Mark visited
13 dfs(r + 1, c)
14 dfs(r - 1, c)
15 dfs(r, c + 1)
16 dfs(r, c - 1)
17
18 for r in range(rows):
19 for c in range(cols):
20 if grid[r][c] == '1':
21 count += 1
22 dfs(r, c)
23
24 return count
133. Clone Graph (Medium)
1def cloneGraph(node: 'Node') -> 'Node':
2 # DFS with hash map - O(V+E) time, O(V) space
3 if not node:
4 return None
5
6 visited = {}
7
8 def dfs(node):
9 if node in visited:
10 return visited[node]
11
12 clone = Node(node.val)
13 visited[node] = clone
14
15 for neighbor in node.neighbors:
16 clone.neighbors.append(dfs(neighbor))
17
18 return clone
19
20 return dfs(node)
695. Max Area of Island (Medium)
1def maxAreaOfIsland(grid: list[list[int]]) -> int:
2 # DFS - O(m*n) time, O(m*n) space
3 rows, cols = len(grid), len(grid[0])
4 max_area = 0
5
6 def dfs(r, c):
7 if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
8 return 0
9 grid[r][c] = 0 # Mark visited
10 return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
11
12 for r in range(rows):
13 for c in range(cols):
14 if grid[r][c] == 1:
15 max_area = max(max_area, dfs(r, c))
16
17 return max_area
417. Pacific Atlantic Water Flow (Medium)
1def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
2 # DFS from oceans - O(m*n) time, O(m*n) space
3 rows, cols = len(heights), len(heights[0])
4 pacific = set()
5 atlantic = set()
6
7 def dfs(r, c, visited, prev_height):
8 if (r < 0 or r >= rows or c < 0 or c >= cols or
9 (r, c) in visited or heights[r][c] < prev_height):
10 return
11
12 visited.add((r, c))
13 for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
14 dfs(r + dr, c + dc, visited, heights[r][c])
15
16 for c in range(cols):
17 dfs(0, c, pacific, heights[0][c])
18 dfs(rows - 1, c, atlantic, heights[rows - 1][c])
19
20 for r in range(rows):
21 dfs(r, 0, pacific, heights[r][0])
22 dfs(r, cols - 1, atlantic, heights[r][cols - 1])
23
24 return list(pacific & atlantic)
130. Surrounded Regions (Medium)
1def solve(board: list[list[str]]) -> None:
2 # DFS from border - O(m*n) time, O(m*n) space
3 if not board:
4 return
5
6 rows, cols = len(board), len(board[0])
7
8 def dfs(r, c):
9 if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
10 return
11 board[r][c] = 'T' # Temporary mark
12 dfs(r + 1, c)
13 dfs(r - 1, c)
14 dfs(r, c + 1)
15 dfs(r, c - 1)
16
17 # Mark border-connected O's
18 for r in range(rows):
19 dfs(r, 0)
20 dfs(r, cols - 1)
21 for c in range(cols):
22 dfs(0, c)
23 dfs(rows - 1, c)
24
25 # Convert
26 for r in range(rows):
27 for c in range(cols):
28 if board[r][c] == 'O':
29 board[r][c] = 'X'
30 elif board[r][c] == 'T':
31 board[r][c] = 'O'
994. Rotting Oranges (Medium)
1def orangesRotting(grid: list[list[int]]) -> int:
2 # Multi-source BFS - O(m*n) time, O(m*n) space
3 from collections import deque
4
5 rows, cols = len(grid), len(grid[0])
6 queue = deque()
7 fresh = 0
8
9 for r in range(rows):
10 for c in range(cols):
11 if grid[r][c] == 2:
12 queue.append((r, c))
13 elif grid[r][c] == 1:
14 fresh += 1
15
16 minutes = 0
17 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
18
19 while queue and fresh > 0:
20 minutes += 1
21 for _ in range(len(queue)):
22 r, c = queue.popleft()
23 for dr, dc in directions:
24 nr, nc = r + dr, c + dc
25 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
26 grid[nr][nc] = 2
27 fresh -= 1
28 queue.append((nr, nc))
29
30 return minutes if fresh == 0 else -1
286. Walls and Gates (Medium)
1def wallsAndGates(rooms: list[list[int]]) -> None:
2 # Multi-source BFS from gates - O(m*n) time, O(m*n) space
3 from collections import deque
4
5 if not rooms:
6 return
7
8 rows, cols = len(rooms), len(rooms[0])
9 INF = 2147483647
10 queue = deque()
11
12 # Add all gates to queue
13 for r in range(rows):
14 for c in range(cols):
15 if rooms[r][c] == 0:
16 queue.append((r, c))
17
18 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
19
20 while queue:
21 r, c = queue.popleft()
22 for dr, dc in directions:
23 nr, nc = r + dr, c + dc
24 if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
25 rooms[nr][nc] = rooms[r][c] + 1
26 queue.append((nr, nc))
207. Course Schedule (Medium)
1def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
2 # Topological sort (cycle detection) - O(V+E) time
3 from collections import defaultdict, deque
4
5 graph = defaultdict(list)
6 in_degree = [0] * numCourses
7
8 for course, prereq in prerequisites:
9 graph[prereq].append(course)
10 in_degree[course] += 1
11
12 queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
13 completed = 0
14
15 while queue:
16 course = queue.popleft()
17 completed += 1
18 for next_course in graph[course]:
19 in_degree[next_course] -= 1
20 if in_degree[next_course] == 0:
21 queue.append(next_course)
22
23 return completed == numCourses
210. Course Schedule II (Medium)
1def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
2 # Topological sort - O(V+E) time
3 from collections import defaultdict, deque
4
5 graph = defaultdict(list)
6 in_degree = [0] * numCourses
7
8 for course, prereq in prerequisites:
9 graph[prereq].append(course)
10 in_degree[course] += 1
11
12 queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
13 order = []
14
15 while queue:
16 course = queue.popleft()
17 order.append(course)
18 for next_course in graph[course]:
19 in_degree[next_course] -= 1
20 if in_degree[next_course] == 0:
21 queue.append(next_course)
22
23 return order if len(order) == numCourses else []
684. Redundant Connection (Medium)
1def findRedundantConnection(edges: list[list[int]]) -> list[int]:
2 # Union-Find - O(n * α(n)) time, O(n) space
3 n = len(edges)
4 parent = list(range(n + 1))
5 rank = [0] * (n + 1)
6
7 def find(x):
8 if parent[x] != x:
9 parent[x] = find(parent[x])
10 return parent[x]
11
12 def union(x, y):
13 px, py = find(x), find(y)
14 if px == py:
15 return False
16 if rank[px] < rank[py]:
17 px, py = py, px
18 parent[py] = px
19 if rank[px] == rank[py]:
20 rank[px] += 1
21 return True
22
23 for u, v in edges:
24 if not union(u, v):
25 return [u, v]
Dynamic Programming
70. Climbing Stairs (Easy)
1def climbStairs(n: int) -> int:
2 # DP (Fibonacci) - O(n) time, O(1) space
3 if n <= 2:
4 return n
5
6 prev2, prev1 = 1, 2
7 for _ in range(3, n + 1):
8 curr = prev1 + prev2
9 prev2, prev1 = prev1, curr
10
11 return prev1
746. Min Cost Climbing Stairs (Easy)
1def minCostClimbingStairs(cost: list[int]) -> int:
2 # DP - O(n) time, O(1) space
3 prev2, prev1 = 0, 0
4
5 for i in range(2, len(cost) + 1):
6 curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
7 prev2, prev1 = prev1, curr
8
9 return prev1
198. House Robber (Medium)
1def rob(nums: list[int]) -> int:
2 # DP - O(n) time, O(1) space
3 prev2, prev1 = 0, 0
4
5 for num in nums:
6 curr = max(prev1, prev2 + num)
7 prev2, prev1 = prev1, curr
8
9 return prev1
213. House Robber II (Medium)
1def rob(nums: list[int]) -> int:
2 # Two passes (exclude first or last) - O(n) time, O(1) space
3 if len(nums) == 1:
4 return nums[0]
5
6 def rob_linear(houses):
7 prev2, prev1 = 0, 0
8 for h in houses:
9 curr = max(prev1, prev2 + h)
10 prev2, prev1 = prev1, curr
11 return prev1
12
13 return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
5. Longest Palindromic Substring (Medium)
1def longestPalindrome(s: str) -> str:
2 # Expand from center - O(n^2) time, O(1) space
3 def expand(left, right):
4 while left >= 0 and right < len(s) and s[left] == s[right]:
5 left -= 1
6 right += 1
7 return s[left + 1:right]
8
9 result = ""
10 for i in range(len(s)):
11 # Odd length
12 odd = expand(i, i)
13 if len(odd) > len(result):
14 result = odd
15 # Even length
16 even = expand(i, i + 1)
17 if len(even) > len(result):
18 result = even
19
20 return result
647. Palindromic Substrings (Medium)
1def countSubstrings(s: str) -> int:
2 # Expand from center - O(n^2) time, O(1) space
3 count = 0
4
5 def expand(left, right):
6 nonlocal count
7 while left >= 0 and right < len(s) and s[left] == s[right]:
8 count += 1
9 left -= 1
10 right += 1
11
12 for i in range(len(s)):
13 expand(i, i) # Odd length
14 expand(i, i + 1) # Even length
15
16 return count
91. Decode Ways (Medium)
1def numDecodings(s: str) -> int:
2 # DP - O(n) time, O(1) space
3 if not s or s[0] == '0':
4 return 0
5
6 prev2, prev1 = 1, 1
7
8 for i in range(1, len(s)):
9 curr = 0
10
11 # Single digit
12 if s[i] != '0':
13 curr += prev1
14
15 # Two digits
16 two_digit = int(s[i-1:i+1])
17 if 10 <= two_digit <= 26:
18 curr += prev2
19
20 prev2, prev1 = prev1, curr
21
22 return prev1
322. Coin Change (Medium)
1def coinChange(coins: list[int], amount: int) -> int:
2 # DP - O(amount * n) time, O(amount) space
3 dp = [float('inf')] * (amount + 1)
4 dp[0] = 0
5
6 for i in range(1, amount + 1):
7 for coin in coins:
8 if coin <= i and dp[i - coin] != float('inf'):
9 dp[i] = min(dp[i], dp[i - coin] + 1)
10
11 return dp[amount] if dp[amount] != float('inf') else -1
152. Maximum Product Subarray (Medium)
1def maxProduct(nums: list[int]) -> int:
2 # Track min and max - O(n) time, O(1) space
3 result = nums[0]
4 cur_max = cur_min = 1
5
6 for num in nums:
7 candidates = (num, num * cur_max, num * cur_min)
8 cur_max = max(candidates)
9 cur_min = min(candidates)
10 result = max(result, cur_max)
11
12 return result
139. Word Break (Medium)
1def wordBreak(s: str, wordDict: list[str]) -> bool:
2 # DP - O(n^2 * m) time, O(n) space
3 word_set = set(wordDict)
4 dp = [False] * (len(s) + 1)
5 dp[0] = True
6
7 for i in range(1, len(s) + 1):
8 for j in range(i):
9 if dp[j] and s[j:i] in word_set:
10 dp[i] = True
11 break
12
13 return dp[len(s)]
300. Longest Increasing Subsequence (Medium)
1def lengthOfLIS(nums: list[int]) -> int:
2 # Binary search - O(n log n) time, O(n) space
3 from bisect import bisect_left
4
5 sub = []
6 for num in nums:
7 pos = bisect_left(sub, num)
8 if pos == len(sub):
9 sub.append(num)
10 else:
11 sub[pos] = num
12
13 return len(sub)
14
15 # DP approach: O(n^2) time
16 # dp = [1] * len(nums)
17 # for i in range(1, len(nums)):
18 # for j in range(i):
19 # if nums[j] < nums[i]:
20 # dp[i] = max(dp[i], dp[j] + 1)
21 # return max(dp)
416. Partition Equal Subset Sum (Medium)
1def canPartition(nums: list[int]) -> bool:
2 # DP - O(n * sum) time, O(sum) space
3 total = sum(nums)
4 if total % 2 != 0:
5 return False
6
7 target = total // 2
8 dp = [False] * (target + 1)
9 dp[0] = True
10
11 for num in nums:
12 for j in range(target, num - 1, -1):
13 dp[j] = dp[j] or dp[j - num]
14
15 return dp[target]
62. Unique Paths (Medium)
1def uniquePaths(m: int, n: int) -> int:
2 # DP - O(m*n) time, O(n) space
3 dp = [1] * n
4
5 for _ in range(1, m):
6 for j in range(1, n):
7 dp[j] += dp[j - 1]
8
9 return dp[n - 1]
1143. Longest Common Subsequence (Medium)
1def longestCommonSubsequence(text1: str, text2: str) -> int:
2 # DP - O(m*n) time, O(n) space
3 m, n = len(text1), len(text2)
4 dp = [0] * (n + 1)
5
6 for i in range(1, m + 1):
7 prev = 0
8 for j in range(1, n + 1):
9 temp = dp[j]
10 if text1[i - 1] == text2[j - 1]:
11 dp[j] = prev + 1
12 else:
13 dp[j] = max(dp[j], dp[j - 1])
14 prev = temp
15
16 return dp[n]
53. Maximum Subarray (Medium)
1def maxSubArray(nums: list[int]) -> int:
2 # Kadane's algorithm - O(n) time, O(1) space
3 max_sum = nums[0]
4 current_sum = nums[0]
5
6 for i in range(1, len(nums)):
7 current_sum = max(nums[i], current_sum + nums[i])
8 max_sum = max(max_sum, current_sum)
9
10 return max_sum
55. Jump Game (Medium)
1def canJump(nums: list[int]) -> bool:
2 # Greedy - O(n) time, O(1) space
3 max_reach = 0
4
5 for i in range(len(nums)):
6 if i > max_reach:
7 return False
8 max_reach = max(max_reach, i + nums[i])
9
10 return True
Intervals
57. Insert Interval (Medium)
1def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
2 # Linear scan - O(n) time, O(n) space
3 result = []
4 i = 0
5 n = len(intervals)
6
7 # Add all intervals before newInterval
8 while i < n and intervals[i][1] < newInterval[0]:
9 result.append(intervals[i])
10 i += 1
11
12 # Merge overlapping intervals
13 while i < n and intervals[i][0] <= newInterval[1]:
14 newInterval[0] = min(newInterval[0], intervals[i][0])
15 newInterval[1] = max(newInterval[1], intervals[i][1])
16 i += 1
17 result.append(newInterval)
18
19 # Add remaining intervals
20 while i < n:
21 result.append(intervals[i])
22 i += 1
23
24 return result
56. Merge Intervals (Medium)
1def merge(intervals: list[list[int]]) -> list[list[int]]:
2 # Sort + merge - O(n log n) time, O(n) space
3 intervals.sort(key=lambda x: x[0])
4 merged = [intervals[0]]
5
6 for start, end in intervals[1:]:
7 if start <= merged[-1][1]:
8 merged[-1][1] = max(merged[-1][1], end)
9 else:
10 merged.append([start, end])
11
12 return merged
435. Non-overlapping Intervals (Medium)
1def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
2 # Greedy (sort by end) - O(n log n) time, O(1) space
3 intervals.sort(key=lambda x: x[1])
4 count = 0
5 prev_end = float('-inf')
6
7 for start, end in intervals:
8 if start >= prev_end:
9 prev_end = end
10 else:
11 count += 1
12
13 return count
252. Meeting Rooms (Easy)
1def canAttendMeetings(intervals: list[list[int]]) -> bool:
2 # Sort and check overlap - O(n log n) time, O(1) space
3 intervals.sort(key=lambda x: x[0])
4
5 for i in range(1, len(intervals)):
6 if intervals[i][0] < intervals[i - 1][1]:
7 return False
8
9 return True
253. Meeting Rooms II (Medium)
1def minMeetingRooms(intervals: list[list[int]]) -> int:
2 # Two arrays (start/end times) - O(n log n) time, O(n) space
3 starts = sorted(i[0] for i in intervals)
4 ends = sorted(i[1] for i in intervals)
5
6 rooms = 0
7 end_ptr = 0
8
9 for start in starts:
10 if start < ends[end_ptr]:
11 rooms += 1
12 else:
13 end_ptr += 1
14
15 return rooms
16
17 # Alternative: Min heap
18 # import heapq
19 # intervals.sort(key=lambda x: x[0])
20 # heap = []
21 # for start, end in intervals:
22 # if heap and heap[0] <= start:
23 # heapq.heappop(heap)
24 # heapq.heappush(heap, end)
25 # return len(heap)
Math & Geometry
48. Rotate Image (Medium)
1def rotate(matrix: list[list[int]]) -> None:
2 # Transpose + Reverse - O(n^2) time, O(1) space
3 n = len(matrix)
4
5 # Transpose
6 for i in range(n):
7 for j in range(i + 1, n):
8 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
9
10 # Reverse each row
11 for row in matrix:
12 row.reverse()
54. Spiral Matrix (Medium)
1def spiralOrder(matrix: list[list[int]]) -> list[int]:
2 # Boundary tracking - O(m*n) time, O(1) extra space
3 result = []
4 top, bottom = 0, len(matrix) - 1
5 left, right = 0, len(matrix[0]) - 1
6
7 while top <= bottom and left <= right:
8 # Right
9 for c in range(left, right + 1):
10 result.append(matrix[top][c])
11 top += 1
12
13 # Down
14 for r in range(top, bottom + 1):
15 result.append(matrix[r][right])
16 right -= 1
17
18 # Left
19 if top <= bottom:
20 for c in range(right, left - 1, -1):
21 result.append(matrix[bottom][c])
22 bottom -= 1
23
24 # Up
25 if left <= right:
26 for r in range(bottom, top - 1, -1):
27 result.append(matrix[r][left])
28 left += 1
29
30 return result
73. Set Matrix Zeroes (Medium)
1def setZeroes(matrix: list[list[int]]) -> None:
2 # Use first row/col as markers - O(m*n) time, O(1) space
3 m, n = len(matrix), len(matrix[0])
4 first_row_zero = any(matrix[0][j] == 0 for j in range(n))
5 first_col_zero = any(matrix[i][0] == 0 for i in range(m))
6
7 # Mark zeros
8 for i in range(1, m):
9 for j in range(1, n):
10 if matrix[i][j] == 0:
11 matrix[i][0] = 0
12 matrix[0][j] = 0
13
14 # Set zeros based on markers
15 for i in range(1, m):
16 for j in range(1, n):
17 if matrix[i][0] == 0 or matrix[0][j] == 0:
18 matrix[i][j] = 0
19
20 # Handle first row and column
21 if first_row_zero:
22 for j in range(n):
23 matrix[0][j] = 0
24 if first_col_zero:
25 for i in range(m):
26 matrix[i][0] = 0
202. Happy Number (Easy)
1def isHappy(n: int) -> bool:
2 # Floyd's cycle detection - O(log n) time, O(1) space
3 def get_next(num):
4 total = 0
5 while num > 0:
6 digit = num % 10
7 total += digit * digit
8 num //= 10
9 return total
10
11 slow = fast = n
12 while True:
13 slow = get_next(slow)
14 fast = get_next(get_next(fast))
15 if fast == 1:
16 return True
17 if slow == fast:
18 return False
66. Plus One (Easy)
1def plusOne(digits: list[int]) -> list[int]:
2 # Right to left - O(n) time, O(1) space
3 for i in range(len(digits) - 1, -1, -1):
4 if digits[i] < 9:
5 digits[i] += 1
6 return digits
7 digits[i] = 0
8
9 return [1] + digits
50. Pow(x, n) (Medium)
1def myPow(x: float, n: int) -> float:
2 # Binary exponentiation - O(log n) time, O(1) space
3 if n < 0:
4 x = 1 / x
5 n = -n
6
7 result = 1
8 while n:
9 if n & 1:
10 result *= x
11 x *= x
12 n >>= 1
13
14 return result
43. Multiply Strings (Medium)
1def multiply(num1: str, num2: str) -> str:
2 # Grade school multiplication - O(m*n) time, O(m+n) space
3 if num1 == "0" or num2 == "0":
4 return "0"
5
6 m, n = len(num1), len(num2)
7 result = [0] * (m + n)
8
9 for i in range(m - 1, -1, -1):
10 for j in range(n - 1, -1, -1):
11 product = int(num1[i]) * int(num2[j])
12 pos1, pos2 = i + j, i + j + 1
13 total = product + result[pos2]
14
15 result[pos2] = total % 10
16 result[pos1] += total // 10
17
18 # Remove leading zeros
19 start = 0
20 while start < len(result) - 1 and result[start] == 0:
21 start += 1
22
23 return ''.join(map(str, result[start:]))
Bit Manipulation
136. Single Number (Easy)
1def singleNumber(nums: list[int]) -> int:
2 # XOR - O(n) time, O(1) space
3 result = 0
4 for num in nums:
5 result ^= num
6 return result
191. Number of 1 Bits (Easy)
1def hammingWeight(n: int) -> int:
2 # Brian Kernighan's algorithm - O(k) time where k = number of 1s
3 count = 0
4 while n:
5 n &= (n - 1) # Remove rightmost 1 bit
6 count += 1
7 return count
338. Counting Bits (Easy)
1def countBits(n: int) -> list[int]:
2 # DP with bit manipulation - O(n) time, O(n) space
3 dp = [0] * (n + 1)
4 for i in range(1, n + 1):
5 dp[i] = dp[i >> 1] + (i & 1)
6 return dp
190. Reverse Bits (Easy)
1def reverseBits(n: int) -> int:
2 # Bit by bit - O(32) time, O(1) space
3 result = 0
4 for _ in range(32):
5 result = (result << 1) | (n & 1)
6 n >>= 1
7 return result
268. Missing Number (Easy)
1def missingNumber(nums: list[int]) -> int:
2 # XOR - O(n) time, O(1) space
3 n = len(nums)
4 result = n
5 for i, num in enumerate(nums):
6 result ^= i ^ num
7 return result
8
9 # Alternative: Sum formula
10 # return n * (n + 1) // 2 - sum(nums)
371. Sum of Two Integers (Medium)
1def getSum(a: int, b: int) -> int:
2 # Bit manipulation - O(1) time, O(1) space
3 # Handle Python's arbitrary precision integers
4 MASK = 0xFFFFFFFF
5 MAX_INT = 0x7FFFFFFF
6
7 while b != 0:
8 carry = ((a & b) << 1) & MASK
9 a = (a ^ b) & MASK
10 b = carry
11
12 # Handle negative numbers
13 return a if a <= MAX_INT else ~(a ^ MASK)
Summary
| Difficulty | Count |
|---|---|
| Easy | 35 |
| Medium | 65 |
| Total | 100 |
Good luck with your interview preparation!