LeetCode Revision Flashcards
📝 300. Longest Increasing Subsequence
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], so the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Answer (O(n²) Approach):
1️⃣ Iterate over nums in reverse order.
2️⃣ For each index i, check all elements after it (i+1 to n).
3️⃣ If nums[i] > num, update maxdp = max(maxdp, dp[i]).
4️⃣ Store the LIS length at dp[i] = maxdp + 1.
5️⃣ Return max(dp).
—————————————————————
Answer (O(n log n) Approach):
1️⃣ Use a dynamic array dp to track the smallest possible increasing subsequence.
2️⃣ Iterate through nums and check:
If nums[i] is greater than the last element in dp, append it (extends LIS).
Else, find the correct position using binary search (bisect_left) and replace the element.
3️⃣ The length of dp gives the LIS length.
—————————————————————
n = len(nums)
dp = [nums[0]]
count = 1
for i in range(1, n):
if dp[-1]<nums[i]:
dp.append(nums[i])
count+=1
continue
idx = bisect_left(dp, nums[i])
dp[idx] = nums[i]
return count
📝 109. Convert Sorted List to Binary Search Tree
Example 1:
Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible BST is:
markdown
Copy
Edit
0
/ \
-3 9
/ /
-10 5
This tree is height-balanced.
Example 2:
Input: head = []
Output: []
Answer (O(n log n) Approach):
1️⃣ Find the middle node: Use slow and fast pointers to find the middle of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer is at the middle.
2️⃣ Break the list into two halves: The left half (before the middle) forms the left subtree, and the right half (after the middle) forms the right subtree. Disconnect the left half by setting prev.next = None.
3️⃣ Recursively build the BST: The middle element becomes the root node. Recursively apply the same process to the left and right halves to construct the left and right subtrees.
4️⃣ Return the root: The base case is when the linked list is empty (None), in which case we return None. If there is only one node left, it becomes a leaf node.
—————————————————————
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
if not head:
return None
if not head.next:
return TreeNode(head.val)
mid = head
tail = head
prev = None
while tail and tail.next:
prev = mid
mid = mid.next
tail = tail.next.next
if prev:
prev.next = None
root = TreeNode(mid.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(mid.next)
return root
📝 211. Design Add and Search Words Data Structure
Example:
Input:
[“WordDictionary”,”addWord”,”addWord”,”addWord”,”search”,”search”,”search”,”search”]
[[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b..”]]
Output:
[null,null,null,null,false,true,true,true]
obj = WordDictionary()
Answer (O(N) for add, O(N) worst-case for search using DFS):
1️⃣ Use a Trie (Prefix Tree): Create a TrieNode class with a dictionary to store children nodes and a boolean word to mark the end of a word.
2️⃣ Add words efficiently: Iterate through each character of the word and insert it into the Trie if not already present. Mark the last node as the end of a word.
3️⃣ Search with recursion (DFS):
If the character is a letter, check if it exists in the Trie and continue.
If the character is a dot (‘.’), it can match any letter, so recursively check all possible children nodes.
4️⃣ Return the result: If the word is found in the Trie, return True, otherwise return False.
—————————————————————
class TrieNode:
def __init__(self):
self.children = {}
self.word = False
class WordDictionary:
def \_\_init\_\_(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.word = True
def search(self, word: str) -> bool:
def dfs(j, root):
cur = root
for i in range(j, len(word)):
c = word[i]
if c==".":
for child in cur.children.values():
if dfs(i+1, child):
return True
return False
else:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.word
return dfs(0, self.root)
📝 417. Pacific Atlantic Water Flow
Example:
Input:
heights = [[1,2,2,3,5],
[3,2,3,4,4],
[2,4,5,3,1],
[6,7,1,4,5],
[5,1,1,2,4]]
Output:
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation:
The following cells can flow to both the Pacific and Atlantic oceans.
For example:
(0,4) flows to both oceans directly.
(1,3) reaches Pacific via (0,3) and Atlantic via (1,4).
(3,0) reaches Pacific directly and Atlantic via (4,0).
Answer (O(m × n) DFS Approach):
1️⃣ Use Depth-First Search (DFS) to determine which cells can reach the Pacific and Atlantic oceans.
2️⃣ Start DFS from the ocean boundaries:
The Pacific Ocean is connected to the top and left edges.
The Atlantic Ocean is connected to the bottom and right edges.
3️⃣ Perform DFS from each boundary cell and mark reachable cells for each ocean.
4️⃣ Find the intersection of the two sets of reachable cells—these are the cells where water can flow to both oceans.
—————————————————————
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
pac, atl = set(), set()
res = []
def dfs(r, c, visit, prev):
if r<0 or c<0 or r==m or c==n or (r,c) in visit or heights[r][c]<prev:
return
visit.add((r,c))
dfs(r+1, c, visit, heights[r][c])
dfs(r-1, c, visit, heights[r][c])
dfs(r, c+1, visit, heights[r][c])
dfs(r, c-1, visit, heights[r][c])
for i in range(m):
dfs(i, 0, pac, heights[i][0])
dfs(i, n-1, atl, heights[i][n-1])
for j in range(n):
dfs(0, j, pac, heights[0][j])
dfs(m-1, j, atl, heights[m-1][j])
for i in range(m):
for j in range(n):
if (i,j) in pac and (i,j) in atl:
res.append([i,j])
return res
📝 1. Two Sum
Example 1:
🔹 Input: nums = [2,7,11,15], target = 9
🔹 Output: [0,1]
🔹 Explanation: Because nums[0] + nums[1] == 9, we return [0,1].
Answer (O(n²) Brute Force Approach):
1️⃣ Use two nested loops to check all possible pairs.
2️⃣ For each pair (i, j), check if nums[i] + nums[j] == target.
3️⃣ If a match is found, return [i, j].
4️⃣ Else, continue checking until a match is found.
✅ Time Complexity: O(n²) (double loop iterating through nums).
✅ Space Complexity: O(1) (no extra space used).
————————————————————-
Answer (O(n) HashMap Approach):
1️⃣ Initialize a HashMap (hmap) to store seen numbers and their indices.
2️⃣ Iterate through the array while computing diff = target - num.
3️⃣ Check if diff exists in hmap, meaning we’ve seen a number that sums to target.
4️⃣ Return indices [i, hmap[diff]] when a match is found. Otherwise, store num in hmap.
✅ Time Complexity: O(n) (single pass through nums).
✅ Space Complexity: O(n) (extra space for storing indices).
—————————————————————
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hmap = {}
for i, num in enumerate(nums):
diff = target - num
if diff in hmap:
return [i, hmap[diff]]
hmap[num] = i
return []
📝 529. Minesweeper
Example 1:
Input:
board = [[“E”,”E”,”E”,”E”,”E”],
[“E”,”E”,”M”,”E”,”E”],
[“E”,”E”,”E”,”E”,”E”],
[“E”,”E”,”E”,”E”,”E”]]
click = [3,0]
Output:
[[“B”,”1”,”E”,”1”,”B”],
[“B”,”1”,”M”,”1”,”B”],
[“B”,”1”,”1”,”1”,”B”],
[“B”,”B”,”B”,”B”,”B”]]
Example 2:
Input:
board = [[“B”,”1”,”E”,”1”,”B”],
[“B”,”1”,”M”,”1”,”B”],
[“B”,”1”,”1”,”1”,”B”],
[“B”,”B”,”B”,”B”,”B”]]
click = [1,2]
Output:
[[“B”,”1”,”E”,”1”,”B”],
[“B”,”1”,”X”,”1”,”B”],
[“B”,”1”,”1”,”1”,”B”],
[“B”,”B”,”B”,”B”,”B”]]
Answer (O(m × n) DFS Approach):
1️⃣ Check the Clicked Cell:
If it contains a mine (‘M’), change it to ‘X’ (game over).
2️⃣ Define a Helper Function (countMines)
Count adjacent mines by checking all 8 possible directions.
3️⃣ Use DFS for Revealing Empty Squares (dfs)
If the clicked cell is ‘E’:
Count adjacent mines.
If no adjacent mines (count == 0), mark as ‘B’ and reveal surrounding cells recursively.
If there are adjacent mines (count > 0), mark with the count (‘1’ to ‘8’).
4️⃣ Process the Click and Return the Updated Board
If it’s an empty square, start the DFS.
Return the modified board.
—————————————————————
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
m, n = len(board), len(board[0])
directions = [[1,0], [0,1], [1,1], [-1,0], [0,-1], [-1,-1], [-1, 1], [1, -1]]
def countMines(r, c):
count = 0
for dr, dc in directions:
row, col = r+dr, c+dc
if 0<=row<m and 0<=col<n and board[row][col]==”M”:
count += 1
return count
def dfs(r, c):
if board[r][c]!="E":
return
count = countMines(r,c)
if count==0:
board[r][c]="B"
for dr, dc in directions:
row, col = r+dr, c+dc
if 0<=row<m and 0<=col<n:
dfs(row, col)
else:
board[r][c] = str(count)
return
r, c = click
if board[r][c]=="M":
board[r][c]="X"
else:
dfs(r,c)
return board
📝 79. Word Search
You are given an m x n board of characters and a string word. Return true if word can be formed by sequentially adjacent cells (horizontally or vertically). The same letter cell cannot be used more than once.
Example 1:
Input:
board = [[“A”,”B”,”C”,”E”],
[“S”,”F”,”C”,”S”],
[“A”,”D”,”E”,”E”]]
word = “ABCCED”
Output: true
Example 2:
Input:
board = [[“A”,”B”,”C”,”E”],
[“S”,”F”,”C”,”S”],
[“A”,”D”,”E”,”E”]]
word = “SEE”
Output: true
Example 3:
board = [[“A”,”B”,”C”,”E”],
[“S”,”F”,”C”,”S”],
[“A”,”D”,”E”,”E”]]
word = “ABCB”
Output: false
Answer (O(m × n × 4^k) Backtracking Approach):
1️⃣ Define a DFS Helper Function (dfs)
Base case: If we match all letters of word, return True.
If the cell is out of bounds, already visited, or doesn’t match the next letter, return False.
2️⃣ Use a Set (path) to Track Visited Cells
Prevent reusing the same cell in a single word path.
3️⃣ Explore All Four Directions (Up, Down, Left, Right)
Move to adjacent cells recursively to find the next letter.
4️⃣ Backtrack After Exploration
Remove the current cell from path after recursion to allow new paths.
5️⃣ Check Every Cell as a Possible Starting Point
Iterate through the grid to find potential starting positions for the word.
—————————————————————
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
path = set()
def dfs(i, j, c):
if c==len(word):
return True
if (i<0 or j<0 or i>=m or j>=n or (i,j) in path or board[i][j]!=word[c]):
return False
path.add((i,j))
res = (dfs(i+1, j, c+1) or
dfs(i-1, j, c+1) or
dfs(i, j+1, c+1) or
dfs(i, j-1, c+1))
path.remove((i,j))
return res
for i in range(m):
for j in range(n):
if dfs(i, j, 0): return True
return False
📝 212. Word Search II
You are given an m x n board of characters and a list of strings words. Return all words that can be formed by sequentially adjacent cells (horizontally or vertically). The same cell cannot be used more than once in a word.
Example 1:
Input:
board = [[“o”,”a”,”a”,”n”],
[“e”,”t”,”a”,”e”],
[“i”,”h”,”k”,”r”],
[“i”,”f”,”l”,”v”]]
words = [“oath”,”pea”,”eat”,”rain”]
Output: [“eat”,”oath”]
Example 2:
Input:
board = [[“a”,”b”],
[“c”,”d”]]
words = [“abcb”]
Output: []
Answer (O(m × n × 4^k) Backtracking + Trie Approach):
1️⃣ Build a Trie:
Each word from words is inserted into a Trie for fast lookups.
2️⃣ Depth-First Search (DFS) to Find Words:
Start from every cell in the board.
If the current letter is in the Trie, explore all 4 possible directions (up, down, left, right).
Use a visit set to track visited cells to avoid reuse.
3️⃣ Backtrack After DFS:
If a word is found (node.word == True), add it to the result.
Remove the cell from visit to allow other paths to explore it.
4️⃣ Return the Collected Words:
Convert the res set to a list and return it.ell is a potential starting point for DFS.
—————————————————————
class TrieNode:
def __init__(self):
self.children = {}
self.word = False
def addWord(self, word):
cur = self
for w in word:
if not w in cur.children:
cur.children[w] = TrieNode()
cur = cur.children[w]
cur.word = True
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m, n = len(board), len(board[0])
visit, res = set(), set()
root = TrieNode()
for w in words:
root.addWord(w)
def dfs(r, c, node, word):
if r<0 or c<0 or r==m or c==n or (r,c) in visit or board[r][c] not in node.children:
return
visit.add((r,c))
node = node.children[board[r][c]]
word += board[r][c]
if node.word:
res.add(word)
dfs(r+1, c, node, word)
dfs(r, c+1, node, word)
dfs(r-1, c, node, word)
dfs(r, c-1, node, word)
visit.remove((r,c))
for i in range(m):
for j in range(n):
dfs(i, j, root, “”)
return list(res)
📝 289. Game of Life
Example 1:
🔹 Input:
board = [[0,1,0], [0,0,1], [1,1,1], [0,0,0]]
🔹 Output:
[[0,0,0], [1,0,1], [0,1,1], [0,1,0]]
🔹 Explanation:
Each cell follows four rules based on its neighbors. Cells with too few or too many live neighbors die, and dead cells with exactly three live neighbors become alive.
Example 2:
🔹 Input:
board = [[1,1], [1,0]]
🔹 Output: [[1,1], [1,1]]
Answer (O(m * n) Approach)
1️⃣ Make a copy of the board → copy_board = [row[:] for row in board]
2️⃣ Iterate over each cell using (i, j)
Count live neighbors by checking all 8 directions using a directions array.
3️⃣ Apply transition rules:
If live and (live_neighbors < 2 or live_neighbors > 3) → dies.
If dead and live_neighbors == 3 → becomes live.
4️⃣ Update board in place once all cells have been checked.
—————————————————————
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
m, n = len(board), len(board[0])
copy_board = [row[:] for row in board]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
for i in range(m):
for j in range(n):
live_neighbors = 0
for dr, dc in directions:
row, col = i + dr, j + dc
if 0 <= row < m and 0 <= col < n and copy_board[row][col] == 1:
live_neighbors += 1
if copy_board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
board[i][j] = 0
elif copy_board[i][j] == 0 and live_neighbors == 3:
board[i][j] = 1
📝 273. Integer to English Words
Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123
Output: “One Hundred Twenty Three”
Example 2:
Input: num = 12345
Output: “Twelve Thousand Three Hundred Forty Five”
Example 3:
Input: num = 1234567
Output: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”
Answer (O(log n) Approach):
1️⃣ Handle Edge Case:
If num == 0, return “Zero” immediately.
2️⃣ Define Number Groups:
Store words for numbers less than 20, tens (20, 30, …), and place values (Thousand, Million, Billion).
3️⃣ Process Each 3-Digit Chunk:
Extract the last three digits (num % 1000).
Convert them to English using a helper function (getString).
4️⃣ Construct the Final String:
Attach the corresponding place value (Thousand, Million, Billion) to each processed chunk.
Combine results in reverse order for correct placement.
—————————————————————
class Solution:
def numberToWords(self, num: int) -> str:
if num == 0:
return “Zero”
less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
thousands = ["", "Thousand", "Million", "Billion"]
def getString(n):
if n == 0:
return ""
res = []
hundreds = n // 100
if hundreds:
res.append(less_than_20[hundreds] + " Hundred")
last2 = n % 100
if last2 >= 20:
ten, one = last2 // 10, last2 % 10
res.append(tens[ten])
if one:
res.append(less_than_20[one])
elif last2:
res.append(less_than_20[last2])
return " ".join(res)
i = 0
res = []
while num:
digits = num % 1000
s = getString(digits)
if s:
res.append(s + " " + thousands[i])
i += 1
num //= 1000
res.reverse()
return " ".join(res).strip()
📝 295. Find Median from Data Stream
Design a data structure that efficiently finds the median of a growing list of numbers.
If the list has an odd number of elements, return the middle value.
If the list has an even number of elements, return the mean of the two middle values.
Example 1:
Input:
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
Output:
[null, null, null, 1.5, null, 2.0]
Answer (O(log n) for addNum, O(1) for findMedian Approach):
1️⃣ Use Two Heaps:
A max-heap (small) stores the smaller half of numbers (negative values for easy max extraction).
A min-heap (large) stores the larger half of numbers.
2️⃣ Balance the Heaps:
Insert into small, then move the max element from small to large if necessary.
Ensure the size difference between heaps is at most 1.
3️⃣ Find Median Efficiently:
If small has more elements, return the max of small.
If large has more elements, return the min of large.
If both heaps are equal, return the mean of their top elements.
—————————————————————
class MedianFinder:
def __init__(self):
self.small, self.large = [], []
def addNum(self, num: int) -> None:
heapq.heappush(self.small, num*-1)
# check if smallest of large>largest of small
if self.small and self.large and (-1*self.small[0]>self.large[0]):
val = -1* heapq.heappop(self.small)
heapq.heappush(self.large, val)
# check len diff
if len(self.small)>len(self.large)+1:
val = -1* heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large)>len(self.small)+1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -1*val)
def findMedian(self) -> float:
if len(self.small)>len(self.large):
return self.small[0]*-1
if len(self.large)>len(self.small):
return self.large[0]
return (self.large[0]+(-1*self.small[0]))/2
📝 127. Word Ladder
Find the shortest transformation sequence from beginWord to endWord by changing one letter at a time, ensuring each intermediate word exists in wordList.
Each transformed word must differ by one letter.
Return the number of words in the shortest transformation sequence.
If no sequence exists, return 0.
Example 1:
Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: 5
Explanation: “hit” -> “hot” -> “dot” -> “dog” -> “cog”
Example 2:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: 0
Explanation: “cog” is not in wordList, so no valid sequence exists.
Answer (⏱ Time Complexity: O(N * L²), where N = number of words, L = length of each word; Space Complexity: O(N * L)) – BFS Approach:
1️⃣ Check for endWord in wordList
If endWord is not in wordList, return 0 immediately.
if endWord not in wordList: return 0
2️⃣ Build pattern-to-word mapping
For each word in wordList, create intermediate patterns like h*t, it, etc., and map those patterns to the corresponding words.
wordMap[word[:i] + “” + word[i+1:]].append(word)
3️⃣ Breadth-First Search (BFS)
Use BFS starting from beginWord to find the shortest path. Track visited words to avoid cycles.
For each word, generate patterns and traverse all connected words (neighbors).
Continue BFS level-by-level while increasing the path length counter res.
4️⃣ Return Result
Return res when endWord is found during BFS; otherwise, return 0 if the queue gets exhausted.
🔹 Why BFS?
Finds the shortest transformation sequence efficiently.
Avoids unnecessary backtracking.
—————————————————————
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
n = len(beginWord)
wordMap = collections.defaultdict(list)
for word in wordList:
for i in range(n):
pattern = word[:i]+”“+word[i+1:]
wordMap[pattern].append(word)
visited = set([beginWord])
q = collections.deque([beginWord])
res = 1
while q:
for _ in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for i in range(n):
pattern = word[:i]+”“+word[i+1:]
for neighbor in wordMap[pattern]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
res += 1
return 0
📝 126. Word Ladder II
Example 1:
🔹 Input:
beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
🔹 Output:
[[“hit”,”hot”,”dot”,”dog”,”cog”],[“hit”,”hot”,”lot”,”log”,”cog”]]
🔹 Explanation:
There are 2 shortest transformation sequences:
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”
Example 2:
🔹 Input:
beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
🔹 Output: []
🔹 Explanation:
Since “cog” is not in wordList, no transformation sequence exists.
Answer (🔵 BFS + DFS | Time Complexity: O(N * M²)):
1️⃣ Preprocess Patterns:
Convert wordList into a set for quick lookup.
Store wildcard patterns (ht, ot, etc.) in a dictionary for adjacency mapping.
2️⃣ BFS for Shortest Paths:
Use a queue to perform level-wise traversal.
Store distances of each word from beginWord to ensure minimal transformation.
Maintain a parent tracking dictionary for each word.
3️⃣ Track Parent Paths:
If a word can be reached in the shortest possible way, update its parent list.
Stop BFS once endWord is found.
4️⃣ DFS to Retrieve Paths:
Backtrack from endWord to beginWord using parent mappings to construct valid sequences.
—————————————————————
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordSet = set(wordList)
if endWord not in wordSet:
return []
# Add beginWord to the set if not already present
wordSet.add(beginWord)
L = len(beginWord)
# Precompute the pattern mapping
pattern_dict = defaultdict(list)
for word in wordSet:
for i in range(L):
pattern = word[:i] + “” + word[i+1:]
pattern_dict[pattern].append(word)
# Dictionaries for BFS: distances and parents mapping for DFS
distances = {word: float(‘inf’) for word in wordSet}
distances[beginWord] = 0
parents = defaultdict(list)
# BFS to build the tree of shortest paths
queue = deque([beginWord])
found = False
while queue and not found:
# We use a temporary set to record nodes visited at the current level,
# so that we don’t interfere with the ongoing level.
current_level = set()
for _ in range(len(queue)):
word = queue.popleft()
current_distance = distances[word]
for i in range(L):
pattern = word[:i] + “” + word[i+1:]
for neighbor in pattern_dict[pattern]:
# Only proceed if this neighbor is reached at the same minimal distance.
if distances[neighbor] >= current_distance + 1:
# If this is the first time reaching this neighbor at a new shorter distance
if distances[neighbor] > current_distance + 1:
distances[neighbor] = current_distance + 1
queue.append(neighbor)
# Record the parent for reconstruction later.
parents[neighbor].append(word)
if neighbor == endWord:
found = True
# No need to mark visited here because distances hold the minimum level.
# DFS to reconstruct all paths from endWord to beginWord using the parents map
results = []
def dfs(word, path):
if word == beginWord:
results.append(path[::-1])
return
for parent in parents[word]:
dfs(parent, path + [parent])
if found:
dfs(endWord, [endWord])
return results
📝 133. Clone Graph
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation:
The graph consists of 4 nodes.
Node 1 is connected to Nodes 2 and 4.
Node 2 is connected to Nodes 1 and 3.
Node 3 is connected to Nodes 2 and 4.
Node 4 is connected to Nodes 1 and 3.
Example 2:
Input: adjList = [[]]
Output: [[]]
Explanation: The graph has one node with no neighbors.
Answer (O(N) DFS Approach):
1️⃣ Base Case: If the input node is None, return None.
2️⃣ Use a HashMap: Create a dictionary oldNew to map original nodes to their cloned versions.
3️⃣ DFS Traversal: Recursively traverse the graph, creating new nodes and adding them to oldNew.
4️⃣ Clone Neighbors: For each node, add cloned neighbors to its adjacency list.
—————————————————————
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional[‘Node’]) -> Optional[‘Node’]:
if not node:
return None
oldNew = {}
def dfs(node):
if node in oldNew:
return oldNew[node]
copy = Node(node.val)
oldNew[node] = copy
for nei in node.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node)
📝 198. House Robber
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation:
Rob house 1 (money = 1) and house 3 (money = 3).
Total amount robbed = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation:
Rob house 1 (money = 2), house 3 (money = 9), and house 5 (money = 1).
Total amount robbed = 2 + 9 + 1 = 12.
Answer (O(2ⁿ) Brute Force Recursion Approach):
1️⃣ Define a recursive function dfs(i) to explore all possibilities.
2️⃣ At each house i, decide to either:
Rob it (nums[i] + dfs(i + 2)) → Skip the next house.
Skip it (dfs(i + 1)) → Move to the next house.
3️⃣ Return the maximum of the two choices.
4️⃣ Base case: If i >= len(nums), return 0.
————————————————————-
Answer (O(N) Dynamic Programming Approach - Optimized Iterative Solution):
1️⃣ Initialize two variables rob1 and rob2 to keep track of max money.
2️⃣ Iterate through nums and compute:
tmp = max(rob1 + n, rob2) → Choose between robbing or skipping.
Update rob1 = rob2 and rob2 = tmp.
3️⃣ rob2 contains the final max money that can be robbed.
————————————————————-
class Solution:
def rob(self, nums: List[int]) -> int:
rob1, rob2 = 0, 0
for n in nums:
tmp = max(rob1+n, rob2)
print(rob1, rob2)
rob1 = rob2
rob2 = tmp
return rob2
📝 213. House Robber II
You are given an array nums representing the money in each house, arranged in a circle. You cannot rob two adjacent houses. Return the maximum amount you can rob without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and house 3 (money = 2) since they are adjacent. The best option is robbing house 2.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (1) and house 3 (3), totaling 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3]
Output: 3
Answer (O(n) Dynamic Programming Approach):
Since the houses are in a circle, we need to handle the first and last house carefully:
1️⃣ If we rob the first house, we cannot rob the last house.
2️⃣ If we rob the last house, we cannot rob the first house.
3️⃣ Thus, we run the House Robber DP solution twice:
Case 1: Exclude the last house (nums[:-1]).
Case 2: Exclude the first house (nums[1:]).
4️⃣ The answer is the maximum of the two cases.
————————————————————-
class Solution:
def rob(self, nums: List[int]) -> int:
def dp(nums):
prev2, prev = 0, 0
for num in nums:
temp = max(prev2+num, prev)
prev2 = prev
prev = temp
return prev
return max(nums[0], dp(nums[:-1]), dp(nums[1:]))
📝 322. Coin Change
You are given an array coins representing different denominations and an integer amount.
Find the fewest number of coins needed to make up that amount.
If it’s not possible, return -1.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1 (3 coins).
Example 2:
Input: coins = [2], amount = 3
Output: -1
Explanation: Cannot form 3 using only coin 2.
Example 3:
Input: coins = [1], amount = 0
Output: 0
Explanation: No coins needed for amount 0.
Answer (O(n × m) Dynamic Programming Approach):
We use Dynamic Programming (DP) with Bottom-Up Approach:
1️⃣ Define dp[i] as the minimum coins required to make amount i.
2️⃣ Initialize dp array:
dp[0] = 0 (0 coins needed for 0 amount).
Fill rest of dp with ∞ (unreachable states).
3️⃣ Iterate through amounts 1 → amount:
For each coin, check if i - coin is reachable.
Update dp[i] = min(dp[i], 1 + dp[i - coin]).
4️⃣ If dp[amount] is still ∞, return -1.
5️⃣ Otherwise, return dp[amount].
————————————————————-
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float(‘inf’)]*(amount+1)
dp[0] = 0
for i in range(1, amount+1):
for c in coins:
if i-c>=0:
dp[i] = min(dp[i], 1+dp[i-c])
return dp[amount] if dp[amount]!=float(‘inf’) else -1
📝 152. Maximum Product Subarray
Given an integer array nums, find a subarray with the largest product and return the product.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: The subarray [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2 because [-2,-1] is not a contiguous subarray.
Answer (O(n) Dynamic Tracking Approach):
We use a single-pass dynamic approach to keep track of the current min and max products:
1️⃣ Why track both min & max?
A negative number flips min ↔ max when multiplied.
Example: Multiplying -2 with min -3 becomes 6.
2️⃣ Iterate through nums:
Store curMax (max product ending at i).
Store curMin (min product ending at i for negative cases).
Update res = max(res, curMax).
3️⃣ Final answer is res, the largest product found.
————————————————————-
class Solution:
def maxProduct(self, nums: List[int]) -> int:
curMin, curMax = 1, 1
res = max(nums)
for n in nums:
tmp = curMaxn
curMax = max(tmp, curMinn, n)
curMin = min(tmp, curMin*n, n)
res = max(res, curMax)
return res
📝 Problem 4: Median of Two Sorted Arrays
Example 1: Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: Merged array = [1,2,3], and the median is 2.
Example 2: Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: Merged array = [1,2,3,4], and the median is (2 + 3)/2 = 2.5.
Answer (O(log(min(m, n))) Approach):
1️⃣ Ensure binary search on the smaller array:
To keep time complexity optimal, always perform binary search on the shorter array.
if m > n: nums1, nums2 = nums2, nums1
2️⃣ Apply Binary Search on Partition:
We perform binary search to find the correct partition where:
max(left partition of nums1) <= min(right partition of nums2)
max(left partition of nums2) <= min(right partition of nums1)
3️⃣ Calculate Partition Indices:
mid1 and mid2 represent partitions in nums1 and nums2 respectively such that left side has half the elements.
mid1 = (low + high) // 2
mid2 = left - mid1
4️⃣ Check Partition Validity and Compute Median:
If partition is valid:
Odd total: return max(l1, l2)
Even total: return (max(l1, l2) + min(r1, r2)) / 2.0
Adjust binary search bounds otherwise.
if l1 <= r2 and l2 <= r1:
return (max(l1, l2) + min(r1, r2)) / 2.0
————————————————————-
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
if m>n:
m,n = n,m
nums1,nums2 = nums2,nums1
total = m+n
left = (total+1)//2
def median(a, b):
low, high = 0, a
while low<=high:
mid1 = (low+high)//2
mid2 = left-mid1
l1 = nums1[mid1-1] if mid1>0 else float(‘-inf’)
l2 = nums2[mid2-1] if mid2>0 else float(‘-inf’)
r1 = nums1[mid1] if mid1<a else float(‘inf’)
r2 = nums2[mid2] if mid2<b else float(‘inf’)
if l1<=r2 and l2<=r1:
if total%2==1:
return max(l1, l2)
else:
return (max(l1,l2)+min(r1,r2))/2.0
elif l1>r2:
high = mid1-1
else:
low = mid1+1
return 0
return median(m,n)
📝 Problem 5: Longest Palindromic Substring
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid palindrome of the same length. Either is correct.
Example 2:
Input: s = “cbbd”
Output: “bb”
Explanation: The longest palindromic substring is “bb”.
Answer (O(n²) Expand Around Center Approach):
1️⃣ Use the “Expand Around Center” concept:
A palindrome mirrors around its center.
Each character (and pair of characters) in the string can be a potential center.
2️⃣ Define a helper function lps(l, r) to expand around center:
Expand as long as characters at both ends match.
If the length of the current palindrome is greater than previous, update result.
3️⃣ Check for both odd and even length palindromes:
Odd length: center at i
Even length: center between i and i+1
4️⃣ Return the longest palindrome found:
After all centers are processed, the longest palindromic substring is stored in res.
————————————————————-
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
res, resLen = “”, 0
def lps(l, r): #expand around center
nonlocal res, resLen
while l>=0 and r<n and s[l]==s[r]:
if r-l+1 > resLen:
resLen = r-l+1
res = s[l:r+1]
l-=1
r+=1
for i in range(n):
lps(i,i)
lps(i, i+1)
return res
📝 Problem 8: String to Integer (atoi)
Example 1:
Input: s = “42”
Output: 42
Explanation: Direct conversion of digits, no sign or whitespace to handle.
Example 2:
Input: s = “ -042”
Output: -42
Explanation: Leading whitespace ignored, sign handled, and leading zero omitted in result.
Example 3:
Input: s = “1337c0d3”
Output: 1337
Explanation: Conversion stops after reading digits, ignoring subsequent characters.
Example 4:
Input: s = “0-1”
Output: 0
Explanation: Reading stops after 0 due to - being a non-digit.
Example 5:
Input: s = “words and 987”
Output: 0
Explanation: First character is non-digit; conversion stops immediately.
Answer (O(n) Linear Parsing Approach):
1️⃣ Trim leading whitespace:
Strip any initial spaces to start reading the actual content.
s = s.lstrip()
2️⃣ Handle optional sign (+ or -):
If + or - is encountered, set the sign accordingly and move pointer forward.
if s[i] == ‘+’: sign = 1
elif s[i] == ‘-‘: sign = -1
3️⃣ Read digits and form number:
Loop through each digit character and construct the number using base-10 multiplication.
num = num * 10 + int(s[i])
4️⃣ Apply sign and handle integer overflow:
Multiply final result with sign.
Clamp the result to the 32-bit signed integer range using bounds:
Minimum: -2^31
Maximum: 2^31 - 1
————————————————————-
class Solution:
def myAtoi(self, s: str) -> int:
s = s.lstrip()
if not s:
return 0
i = 0
num = 0
sign = 1
if s[i]==’+’:
sign = 1
i+=1
elif s[i]==’-‘:
sign = -1
i+=1
while i in range(len(s)):
if not s[i].isdigit():
break
else:
num = num*10 + int(s[i])
i+=1
num*=sign
if num<-2**31:
return -2**31
if num>2**31 - 1:
return 2**31 - 1
return num
📝 Problem 12: Integer to Roman
Example 1:
Input: num = 3749
Output: “MMMDCCXLIX”
Explanation:
3000 → MMM
700 → DCC
40 → XL
9 → IX
Example 2:
Input: num = 58
Output: “LVIII”
Explanation:
50 → L
8 → VIII
Example 3:
Input: num = 1994
Output: “MCMXCIV”
Explanation:
1000 → M
900 → CM
90 → XC
4 → IV
Answer (O(1) Greedy Conversion Approach):
1️⃣ Define Roman mappings using Greedy Order:
Create a list of tuples mapping values to Roman symbols in descending order.
roman_mappings = [(1000, “M”), (900, “CM”), …, (1, “I”)]
2️⃣ Iterate through each mapping:
For each value-symbol pair, check how many times it fits in num using integer division.
count = num // value
3️⃣ Append corresponding symbols to result string:
Append the Roman symbol count times and reduce the number accordingly.
roman += rom * count
num = num % value
4️⃣ Return the final Roman numeral string:
After processing all mappings, roman holds the final answer.
————————————————————-
class Solution:
def intToRoman(self, num: int) -> str:
roman_mappings = [
(1000, “M”), (900, “CM”), (500, “D”), (400, “CD”),
(100, “C”), (90, “XC”), (50, “L”), (40, “XL”),
(10, “X”), (9, “IX”), (5, “V”), (4, “IV”), (1, “I”)
]
roman = “”
for value, rom in roman_mappings:
if num//value:
count = num//value
roman += rom*count
num = num % value
return roman
📝 Problem 13: Roman to Integer
Example 1:
Input: s = “III”
Output: 3
Explanation: I + I + I = 3
Example 2:
Input: s = “LVIII”
Output: 58
Explanation: L (50) + V (5) + III (3) = 58
Example 3:
Input: s = “MCMXCIV”
Output: 1994
Explanation:
M = 1000
CM = 900
XC = 90
IV = 4
Total = 1000 + 900 + 90 + 4 = 1994
Answer (O(n) Linear Scan Approach):
1️⃣ Create a symbol-to-value mapping dictionary:
Store Roman numeral values for quick lookup.
hmap = {“I”:1, “V”:5, “X”:10, “L”:50, “C”:100, “D”:500, “M”:1000}
2️⃣ Iterate through the string from left to right:
At each index, compare the current value with the next symbol (if any).
3️⃣ Apply subtraction rule for special pairs:
If the current symbol is smaller than the next, subtract it.
Otherwise, add it to the total.
if hmap[s[i]] < hmap[s[i+1]]:
total -= hmap[s[i]]
else:
total += hmap[s[i]]
4️⃣ Return the final computed integer:
All subtractive cases are handled naturally during traversal.
————————————————————-
class Solution:
def romanToInt(self, s: str) -> int:
total, i = 0, 0
hmap = {“I”:1, “V”:5, “X”:10, “L”:50, “C”:100, “D”:500, “M”:1000}
for i in range(len(s)):
if i<len(s)-1 and hmap[s[i]]<hmap[s[i+1]]:
total -= hmap[s[i]]
else:
total += hmap[s[i]]
return total
📝 Problem 20: Valid Parentheses
Example 1:
Input: s = “()”
Output: true
Explanation: Opening and closing brackets match correctly.
Example 2:
Input: s = “()[]{}”
Output: true
Explanation: Each bracket is closed in the correct order and type.
Example 3:
Input: s = “(]”
Output: false
Explanation: ( is not correctly closed by ].
Example 4:
Input: s = “([])”
Output: true
Explanation: Nested brackets are closed in the right order.
Answer (O(n) Stack-Based Approach):
1️⃣ Initialize a stack to track open brackets:
Use a list to keep track of brackets that need closing.
2️⃣ Create a mapping of closing to opening brackets:
Helps in quickly validating pairs.
pDict = {“)”: “(“, “]”: “[”, “}”: “{“}
3️⃣ Iterate through the string and validate brackets:
If current character is a closing bracket, pop from the stack and verify match.
If it’s an opening bracket, push it to the stack.
if i in pDict:
if stack and pDict[i] == stack[-1]:
stack.pop()
else:
return False
else:
stack.append(i)
4️⃣ Check if stack is empty at the end:
All brackets must be matched and closed.
return not stack
————————————————————-
class Solution:
def isValid(self, s: str) -> bool:
stack = []
pDict = {“)”:”(“, “]”:”[”, “}”:”{“}
for i in s:
if i in pDict:
if stack:
top = stack.pop()
if pDict[i] != top:
return False
else:
return False
else:
stack.append(i)
return not stack
📝 Problem 23: Merge k Sorted Lists
Example 1:
Input: lists = [[1,4,5], [1,3,4], [2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: Merging all sorted linked lists results in one sorted list: 1→1→2→3→4→4→5→6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
class ListNode:
Answer (O(N log k) Divide and Conquer Approach):
1️⃣ Define a helper function to merge two sorted linked lists:
Use a dummy node and tail pointer to build a new merged list.
2️⃣ Merge lists in pairs using divide and conquer:
Reduce the problem size by merging two lists at a time in rounds
Repeat this process until one list remains.
3️⃣ Return the final merged list:
After successive merging, the remaining list is fully sorted.
————————————————————-
Definition for singly-linked list.
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists or len(lists)==0:
return None
def merge2(l1, l2):
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
if l1:
tail.next = l1
elif l2:
tail.next = l2
return dummy.next
while len(lists)>1:
merged = []
for i in range(0, len(lists), 2):
list1 = lists[i]
list2 = lists[i+1] if i+1<len(lists) else None
merged.append(merge2(list1, list2))
lists = merged
return lists[0]
📝 Problem 36: Valid Sudoku
Example 1:
Input:
board = [
[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],
[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],
[”.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],
[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],
[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],
[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],
[”.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],
[”.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],
[”.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]
]
Output: True
Explanation: All rows, columns, and 3x3 sub-boxes contain unique digits (ignoring dots).
Example 2:
Input: Same as Example 1 but top-left “5” is replaced with “8” → duplicate 8 in a sub-box.
Output: False
Explanation: Two 8’s in the same 3x3 sub-box violate Sudoku rules.
Answer (O(1) Constant Space + O(81) Iteration Approach):
1️⃣ Initialize tracking sets for rows, columns, and boxes:
Use defaultdict(set) to track seen digits in each row, column, and 3x3 box.
cols = defaultdict(set)
rows = defaultdict(set)
squares = defaultdict(set) # key = (i//3, j//3)
2️⃣ Loop through each cell on the board:
Ignore empty cells (denoted by ‘.’).
For each filled digit, check if it already exists in:
The same row
The same column
The corresponding 3x3 sub-box
3️⃣ If duplicate found, return False:
Any violation of Sudoku rules (duplicate in row/column/box) leads to immediate invalidation.
4️⃣ If all checks pass, return True:
No duplicates found, board is valid.
if (board[i][j] in rows[i] or
board[i][j] in cols[j] or
board[i][j] in squares[(i//3, j//3)]):
return False
————————————————————-
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
cols = collections.defaultdict(set)
rows = collections.defaultdict(set)
squares = collections.defaultdict(set)
for i in range(9):
for j in range(9):
if board[i][j]==’.’:
continue
if (board[i][j] in rows[i]
or board[i][j] in cols[j]
or board[i][j] in squares[(i//3, j//3)]):
return False
rows[i].add(board[i][j])
cols[j].add(board[i][j])
squares[(i//3, j//3)].add(board[i][j])
return True
📝 Problem 39: Combination Sum
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 + 2 + 3 = 7
7 = 7
Both are valid combinations using unlimited usage of numbers.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Explanation: No combination adds up to 1 using only 2.
Answer (O(2^T) Backtracking/DFS Approach):
1️⃣ Use Depth-First Search (DFS) for exploring combinations:
Try each candidate number starting from a given index and explore all paths where sum ≤ target.
2️⃣ Add a valid combination when rem == 0:
If the remaining target becomes 0, the current combination is valid. Append a copy of it to the result list.
if rem == 0:
ans.append(arr.copy())
return
3️⃣ Allow repeated elements by calling dfs(j, …) (not j+1):
Since same number can be reused, stay on the same index during recursion.
4️⃣ Backtrack after each recursive call:
Remove last appended number to explore new paths.
arr.pop()
————————————————————-
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
# iterate use, i,arr and do not move i
def dfs(i, arr, rem):
if rem == 0:
ans.append(arr.copy())
return
for j in range(i, len(candidates)):
if rem<0 or i==len(candidates):
return
arr.append(candidates[j])
dfs(j, arr, rem-candidates[j])
arr.pop()
dfs(0, [], target)
return ans
📝 Problem 46: Permutations
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Explanation: All possible arrangements of the three elements.
Example 2:
Input: nums = [0,1]
Output: [[0,1], [1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Answer (O(n × n!) Backtracking Approach):
1️⃣ Use backtracking to explore all arrangements:
At each recursive step, fix one element at the current index and permute the rest.
2️⃣ Base case: When index i == n, store the current permutation:
Once we’ve fixed all positions, add the permutation to the result.
if i == n:
ans.append(nums[:])
3️⃣ Swap elements to fix one at a time and explore possibilities:
Swap nums[i] with nums[j] for j in range i to n-1.
Recursively call for next index (i+1).
4️⃣ Backtrack after recursive call to restore the original order:
Swap back to explore a new path from previous state.
nums[i], nums[j] = nums[j], nums[i] # Backtrack
————————————————————-
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
n = len(nums)
def backtrack(i):
if i == n:
ans.append(nums[:])
return
for j in range(i, n):
nums[i], nums[j] = nums[j], nums[i]
backtrack(i+1)
nums[j], nums[i] = nums[i], nums[j]
backtrack(0)
return ans
📝 Problem 56: Merge Intervals
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Intervals [1,3] and [2,6] overlap → merged into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] are overlapping at boundary → merged into [1,5].
Answer (O(n log n) Greedy + Sorting Approach):
1️⃣ Sort the intervals by start time:
This helps ensure overlapping intervals are adjacent and easier to merge.
intervals.sort(key=lambda i: i[0])
2️⃣ Initialize the result list with the first interval:
Start comparison from the second interval onward.
res = [intervals[0]]
3️⃣ Iterate through each interval and check for overlaps:
If the current interval starts before or at the end of the last interval in res, merge them.
if prevEnd >= start:
res[-1][1] = max(prevEnd, end)
4️⃣ If no overlap, append the interval to result as-is:
It starts after previous interval ends → no conflict.
else:
res.append([start, end])
————————————————————-
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# sort it first based on start
intervals.sort(key = lambda i : i[0])
res = [intervals[0]]
for start, end in intervals[1:]:
prevEnd = res[-1][1]
if prevEnd>=start:
res[-1][1] = max(prevEnd, end)
else:
res.append([start, end])
return res
📝 Problem 61: Rotate List
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Explanation: Rotate list to the right by 2 places → last 2 nodes move to the front.
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Explanation: 4 rotations → effective rotation is 4 % 3 = 1, so move last 1 node to the front.
Answer (O(n) One-Pass After Preprocessing Approach):
1️⃣ Count the total number of nodes (count) and get the tail node:
Traverse the list to determine length and reference to the last node.
count, tail = 1, head
while tail.next:
tail = tail.next
count += 1
2️⃣ Reduce unnecessary rotations by taking k % count:
Rotating by list length has no effect.
k = k % count
if k == 0: return head
3️⃣ Find the new tail (node before the new head):
Traverse to the (count - k - 1)-th node.
cur = head
for _ in range(count - k - 1):
cur = cur.next
4️⃣ Rearrange pointers to rotate the list:
newHead = cur.next, break the link at cur.next, and connect tail to original head.
newHead = cur.next
cur.next = None
tail.next = head
————————————————————-
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return head
count, tail = 1, head
while tail.next:
tail = tail.next
count+=1
k = k%count
print(count)
print(k)
if k==0:
return head
cur = head
for i in range(count-k-1):
cur = cur.next
print(i)
newHead = cur.next
cur.next = None
tail.next = head
return newHead
📝 64. Minimum Path Sum
Given an m x n grid filled with non-negative numbers, find a path from the top-left to the bottom-right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The minimum path is 1 → 3 → 1 → 1 → 1, giving a sum of 7.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: The path 1 → 2 → 3 → 6 gives the minimum sum of 12.
Answer (O(m × n) Dynamic Programming Approach):
1️⃣ Initialize a DP table:
Create a 2D array dp of the same size as the grid to store the minimum path sum at each cell.
2️⃣ Base Case (Top-left corner):
The value at dp[0][0] is the same as grid[0][0] because it’s the starting point.
➝ dp[0][0] = grid[0][0]
3️⃣ First Row and First Column Filling:
For the first row, you can only come from the left:
➝ dp[0][j] = dp[0][j-1] + grid[0][j]
For the first column, you can only come from the top:
➝ dp[i][0] = dp[i-1][0] + grid[i][0]
4️⃣ Fill the rest of the DP table:
For each cell dp[i][j], take the minimum of top or left cell plus current grid value:
➝ dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
5️⃣ Final Step - Return the result:
Return dp[m-1][n-1] which contains the minimum path sum from top-left to bottom-right.
————————————————————-
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0 for _ in range(n)] for row in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j==0:
dp[i][j] = grid[i][j]
elif i == 0:
dp[i][j] = dp[i][j-1]+grid[i][j]
elif j == 0:
dp[i][j] = dp[i-1][j]+grid[i][j]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1])+grid[i][j]
return dp[m-1][n-1]
📝 98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
✅ A valid BST satisfies the following:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both subtrees must also be valid BSTs.
Example 1:
Input: root = [2,1,3]
Output: true
Explanation: Both left and right children follow BST rules.
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The right child of node 5 has a value 4, which violates the BST property (4 < 5).
Answer (O(n) DFS Approach):
1️⃣ Use Depth-First Search (DFS):
Traverse the tree using DFS, keeping track of valid value bounds for each node.
2️⃣ Set Initial Boundaries:
Start with (-∞, ∞) as the valid range for the root node’s value.
3️⃣ Validate Each Node:
For each node:
Check if node.val is strictly greater than left and less than right.
If not, return False.
4️⃣ Recurse on Children:
For the left child, update the upper bound (right) to node.val.
For the right child, update the lower bound (left) to node.val.
🧠 Code Snippet:
if not (node.val > left and node.val < right):
return False
5️⃣ Final Step - Return Result:
If all nodes satisfy BST conditions, return True.
📝 100. Same Tree
Given the roots of two binary trees p and q, write a function to check whether they are the same tree.
✅ Two binary trees are considered the same if they are structurally identical and nodes have the same value at each position.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Explanation: Both trees have the same structure and node values.
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Explanation: The structure is different — q has right child where p has left child.
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Explanation: Node values differ at corresponding positions.
Answer (O(n) DFS Approach):
1️⃣ Handle Base Case:
If both nodes are None, return True — both trees are empty at that spot.
2️⃣ Recursive DFS Function:
Create a recursive helper dfs(root1, root2) to compare two nodes:
If only one is None, trees are not the same.
If values differ, trees are not the same.
3️⃣ Compare Subtrees Recursively:
Return the AND of left and right subtree comparisons: ➝ dfs(root1.left, root2.left) and dfs(root1.right, root2.right)
4️⃣ Final Step - Start the DFS:
Call dfs(p, q) and return the result.
————————————————————-
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
def dfs(root1, root2):
if not root1 or not root2:
return root1==root2
if root1.val != root2.val:
return False
return dfs(root1.left, root2.left) and dfs(root1.right, root2.right)
return dfs(p, q)
📝 101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself, i.e., symmetric around its center.
✅ A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Explanation: Left and right subtrees are mirror images of each other.
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Explanation: The left and right subtrees differ in structure and values — not symmetric.
Answer (O(n) DFS Approach):
1️⃣ Handle Base Case:
If the root is None, the tree is symmetric by default — return True.
2️⃣ Create Mirror Comparison Function:
Define a helper function dfs(root1, root2) to compare:
Left subtree of one side with right subtree of the other.
Right subtree of one side with left subtree of the other.
3️⃣ Base Conditions for Mirror Check:
If both nodes are None, return True.
If only one is None, return False.
If values don’t match, return False.
4️⃣ Recursive Mirror Validation:
Recursively compare: ➝ dfs(root1.left, root2.right) AND dfs(root1.right, root2.left)
————————————————————-
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def dfs(root1, root2):
if not root1 or not root2:
return root1 == root2
if root1.val != root2.val:
return False
return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
return dfs(root.left, root.right)
📝 102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes’ values — i.e., from left to right, level by level.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Explanation: Traverse each level from left to right.
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Answer (O(n) BFS Approach):
1️⃣ Handle Empty Tree Case:
If root is None, return an empty list [].
2️⃣ Use a Queue (BFS Traversal):
Initialize a queue (e.g., collections.deque) to store nodes level-by-level.
3️⃣ Iterate While Queue is Not Empty:
For each level, determine the number of nodes (len(queue)).
Use a loop to process all nodes at the current level.
4️⃣ Process Each Node at Current Level:
Pop node from queue.
Add its value to current level list.
Add its left and right children (if any) to the queue for the next level.
5️⃣ Append Each Level’s Values to Result:
After processing each level, append the level’s node values to res.
————————————————————-
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
q = collections.deque()
q.append(root)
while q:
arr = []
for i in range(len(q)):
node = q.popleft()
if node:
q.append(node.left) if node.left else None
q.append(node.right) if node.right else None
arr.append(node.val)
res.append(arr)
return res
📝 116. Populating Next Right Pointers in Each Node
You are given a perfect binary tree (all internal nodes have two children and all leaves are at the same level).
Your task is to populate each node’s next pointer to point to its next right node.
If there is no next right node, set next = NULL.
Example 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation:
Each node is connected to its immediate right neighbor, and the last node in each level points to NULL.
Example 2:
Input: root = []
Output: []
Answer (O(n) DFS Approach for Perfect Binary Tree):
1️⃣ Handle Edge Case:
If the root is None, return None.
2️⃣ Use DFS Recursion:
For each node, set:
node.left.next = node.right
If node.next exists, connect:
➝ node.right.next = node.next.left
3️⃣ Recursive Traversal:
Recursively call DFS on:
node.left
node.right
4️⃣ Perfect Tree Property Optimization:
Since the tree is perfect, you can confidently access left, right, and next.left without null checks inside DFS.
🧠 Code Snippet:
if node.next:
node.right.next = node.next.left
node.left.next = node.right
————————————————————-
class Solution:
def connect(self, root: ‘Optional[Node]’) -> ‘Optional[Node]’:
if not root:
return root
def dfs(node):
if not node.left and not node.right:
return
if node.next:
node.right.next = node.next.left
node.left.next = node.right
dfs(node.left)
dfs(node.right)
dfs(root)
return root
📝 121. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a stock on the i-th day.
Your task is to choose one day to buy and a future day to sell to maximize your profit.
If no profit is possible, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy at 1 (day 2), sell at 6 (day 5), profit = 6 - 1 = 5.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No opportunity to make profit — prices keep falling.
Answer (O(n) Two-Pointer Sliding Window Approach):
1️⃣ Initialize Two Pointers:
l (left) = day to buy stock
r (right) = day to sell stock
➝ Start with l=0, r=1
2️⃣ Traverse the Array:
If prices[r] < prices[l]:
➝ Better buying opportunity, move l to r
3️⃣ Calculate and Track Max Profit:
If prices[r] > prices[l]:
➝ Calculate profit: prices[r] - prices[l]
➝ Update max_profit (stored in diff)
4️⃣ Move Right Pointer Forward:
Continue sliding the window with r += 1 until end of array.
🧠 Code Snippet:
diff = max(diff, prices[r] - prices[l])
————————————————————-
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, 1
n = len(prices)
diff = 0
while r<n:
if prices[r]<prices[l]:
l = r
r = l+1
else:
diff = max(diff, (prices[r]-prices[l]))
r+=1
return diff
📝 146. LRU Cache
Design a data structure that behaves like a Least Recently Used (LRU) cache.
✅ Requirements:
LRUCache(capacity) → Initialize with a positive size.
get(key) → Return value if key exists, else -1.
put(key, value) → Insert or update key-value.
If capacity exceeds, evict the least recently used item.
Goal: Both get() and put() must run in O(1) average time.
Example 1:
Input:
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation:
put(1,1) → cache={1=1}
put(2,2) → cache={1=1,2=2}
get(1) → returns 1, now 1 is most recently used
put(3,3) → evicts LRU key=2 → cache={1=1,3=3}
get(2) → returns -1
put(4,4) → evicts LRU key=1 → cache={3=3,4=4}
get(1) → returns -1
get(3) → returns 3
get(4) → returns 4
Answer (O(1) Time using HashMap + Doubly Linked List):
1️⃣ HashMap for Quick Lookup:
Store key → node mapping for O(1) access to nodes.
2️⃣ Doubly Linked List for LRU Tracking:
Maintain order from Least Recently Used → Most Recently Used using dummy left (LRU) and right (MRU) nodes.
3️⃣ On get(key) Call:
If key exists:
➝ Move node to most recently used (MRU) position.
➝ Return node’s value.
Else return -1.
4️⃣ On put(key, value) Call:
If key exists:
➝ Remove old node.
Create a new node and insert at MRU end.
If size exceeds capacity:
➝ Remove LRU node (next to dummy left) and delete from map.
————————————————————-
class ListNode:
def __init__(self, key, val):
self.key, self.val = key, val
self.next = self.prev = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.right, self.left = ListNode(0, 0), ListNode(0, 0)
self.right.prev, self.left.next = self.left, self.right
def get(self, key: int) -> int:
if key in self.cache:
self.remove(self.cache[key])
self.insert(self.cache[key])
return self.cache[key].val
return -1
def insert(self, node):
prev, nxt = self.right.prev, self.right
prev.next = nxt.prev = node
node.next, node.prev = nxt, prev
def remove(self, node):
prev, nxt = node.prev, node.next
prev.next, nxt.prev = nxt, prev
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.remove(self.cache[key])
self.cache[key] = ListNode(key, value)
self.insert(self.cache[key])
if len(self.cache)>self.cap:
lru = self.left.next
self.remove(lru)
del self.cache[lru.key]
📝 155. Min Stack
Design a stack that supports the following operations in O(1) time:
push(val) → Push element onto stack
pop() → Remove the top element
top() → Get the top element
getMin() → Retrieve the minimum element in the stack
Example 1:
Input:
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Answer (O(1) Two-Stack Approach):
1️⃣ Use Two Stacks:
stack: stores all elements
minStack: stores current minimum values
2️⃣ On push(val) Call:
Push to stack.
If val <= minStack[-1] or minStack is empty, push to minStack.
3️⃣ On pop() Call:
Pop from stack.
If the popped value equals minStack[-1], pop from minStack too.
4️⃣ On top() Call:
Return the top of stack.
5️⃣ On getMin() Call:
Return the top of minStack — which always holds the current minimum.
🧠 Code Snippet:
if not self.minStack or val <= self.minStack[-1]:
self.minStack.append(val)
————————————————————-
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
if not self.minStack or val<=self.minStack[-1]:
self.minStack.append(val)
self.stack.append(val)
def pop(self) -> None:
popped = self.stack.pop()
if self.minStack and popped == self.minStack[-1]:
self.minStack.pop()
def top(self) -> int:
return self.stack[-1] if self.stack else None
def getMin(self) -> int:
return self.minStack[-1] if self.minStack else None
📝 200. Number of Islands
Given an m x n 2D binary grid representing a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is formed by connecting adjacent lands horizontally or vertically, and surrounded by water.
Example 1:
Input:
grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
Output: 1
Explanation: One big connected island of 1s.
Example 2:
Input:
grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
Output: 3
Explanation: Three separate land masses.
Answer (O(m × n) BFS Approach):
1️⃣ Track Visited Cells:
Use a visited set to track already explored land cells.
2️⃣ Traverse Each Cell:
Iterate over each cell in the grid. If a ‘1’ (land) is found and not visited, trigger a BFS traversal from that cell.
3️⃣ BFS Traversal:
Use a queue to explore all connected ‘1’s from the current cell.
Mark each visited land cell.
Move in 4 directions: up, down, left, right.
4️⃣ Count Islands:
Each BFS call from a new unvisited land cell represents one island — increment the island count.
🧠 Code Snippet:
if grid[r][c] == ‘1’ and (r, c) not in visited:
bfs(r, c)
count += 1
————————————————————-
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows = len(grid)
cols = len(grid[0])
count = 0
visited = set()
def bfs(r, c):
q = collections.deque()
q.append((r,c))
visited.add((r,c))
directions = [[1,0], [-1,0], [0,1], [0,-1]]
while q:
row, col = q.popleft()
for dr, dc in directions:
r, c = row+dr, col+dc
if (r in range(rows) and
c in range(cols) and
(r,c) not in visited and
grid[r][c] == ‘1’):
q.append((r,c))
visited.add((r,c))
for r in range(rows):
for c in range(cols):
if grid[r][c]==’1’ and (r,c) not in visited:
bfs(r,c)
count+=1
return count
📝 207. Course Schedule
You are given numCourses total courses labeled from 0 to numCourses - 1, and a list of prerequisites, where prerequisites[i] = [a, b] means you must take course b before course a.
Your task is to determine whether it is possible to finish all courses, i.e., whether the prerequisite graph has no cycles.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take course 0, then course 1.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Circular dependency: you need course 0 to take 1 and 1 to take 0 → cycle detected.
Answer (O(V + E) DFS Cycle Detection in Directed Graph):
1️⃣ Build Adjacency List:
Use a dictionary cMap where cMap[course] contains its prerequisites.
➝ cMap = {i: [] for i in range(numCourses)} ➝ Fill it from the prerequisites list.
2️⃣ Detect Cycles with DFS:
Use a visitedSet to track nodes in the current path.
If a node is already in the visitedSet, a cycle exists → return False.
3️⃣ Base Case for DFS:
If a course has no prerequisites (cMap[c] == []), it’s safe → return True.
4️⃣ Recursive DFS Traversal:
Recurse on all prerequisites for a course.
After a node is safely processed, clear its list (cMap[c] = []) to mark it as completed without cycle (memoization).
🧠 Code Snippet:
if c in vSet:
return False # cycle detected
5️⃣ Final Step:
Run DFS on all numCourses. If any course triggers a cycle, return False. Else, return True.
————————————————————-
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
cMap = {i:[] for i in range(numCourses)}
vSet = set()
for c,p in prerequisites:
cMap[c].append(p)
def dfs(c):
if c in vSet:
return False
if cMap[c]==[]:
return True
vSet.add(c)
for p in cMap[c]:
if not dfs(p): return False
vSet.remove(c)
cMap[c] = []
return True
for i in range(numCourses):
if not dfs(i): return False
return True
📝 210. Course Schedule II
You are given numCourses total courses labeled from 0 to numCourses - 1, and a list of prerequisites where prerequisites[i] = [a, b] means you must take course b before course a.
Return a valid order of courses to finish all.
If not possible (i.e., a cycle exists), return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: Course 0 → Course 1
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3] or [0,1,2,3]
Explanation: Multiple valid topological orders possible.
Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]
Answer (O(V + E) Topological Sort using DFS):
1️⃣ Build Adjacency List:
Use a dictionary cMap[course] = list of prerequisites.
2️⃣ Track Visited and Cycle Sets:
visit: courses already processed
cycle: courses in the current DFS path (for cycle detection)
3️⃣ DFS Traversal for Topological Sort:
If a course is in cycle, a cycle is detected → return False
If already in visit, skip it (already added to result)
4️⃣ Post-Order Append:
After all prerequisites of a course are valid, add course to res.
5️⃣ Return Result:
Final result should be reversed post-order. But in this code, prerequisites are stored in reverse; hence res already forms a valid order.
🧠 Code Snippet:
if not dfs(i): return []
If any course returns False during DFS → cycle exists → no valid ordering
————————————————————-
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
visit, cycle = set(), set()
res = []
cMap = {i:[] for i in range(numCourses)}
for c, p in prerequisites:
cMap[c].append(p)
def dfs(c):
if c in visit: return True
if c in cycle: return False
cycle.add(c)
for p in cMap[c]:
if not dfs(p): return False
cycle.remove(c)
visit.add(c)
res.append(c)
return True
for i in range(numCourses):
if not dfs(i): return []
return res
📝 543. Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter is the longest path between any two nodes, measured in number of edges, not nodes.
➡ The path may or may not pass through the root.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: Longest path is [4,2,1,3] or [5,2,1,3], which includes 3 edges.
Example 2:
Input: root = [1,2]
Output: 1
Explanation: Only one edge between two nodes.
Answer (O(n) DFS Approach):
1️⃣ Define a Recursive DFS Function:
Traverse each node and compute the height (max depth) of its left and right subtrees.
2️⃣ Calculate Diameter at Each Node:
At every node, calculate potential diameter: ➝ l + r = total edges in the path that goes through this node.
3️⃣ Track the Maximum Diameter:
Use a nonlocal dia variable to keep updating the maximum diameter found so far.
4️⃣ Return Height to Parent Call:
Each dfs(node) returns 1 + max(l, r) → height of current subtree.
🧠 Code Snippet:
dia = max(dia, l + r)
5️⃣ Final Step:
Start DFS from root and return the dia after full traversal.
————————————————————-
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
dia = 0
def dfs(node):
nonlocal dia
if not node:
return 0
l = dfs(node.left)
r = dfs(node.right)
dia = max(dia, l+r)
return 1 + max(l, r)
dfs(root)
return dia
📝 767. Reorganize String
Given a string s, rearrange the characters so that no two adjacent characters are the same.
Return any valid rearrangement, or return “” if it’s not possible.
Example 1:
Input: s = “aab”
Output: “aba”
Explanation: ‘a’ and ‘a’ are separated by ‘b’, so it’s valid.
Example 2:
Input: s = “aaab”
Output: “”
Explanation: Too many ‘a’s — impossible to avoid adjacent duplicates.
Answer (O(n log k) Greedy + Max Heap Approach):
1️⃣ Count Character Frequencies:
Use a hash map hMap to count frequencies (note: stored as negative values for max-heap behavior with heapq).
2️⃣ Build a Max Heap:
Create a max heap maxHeap = [[freq, char], …] from hMap.items().
3️⃣ Greedy Rearrangement with Heap:
Always pop the most frequent character (highest freq = most negative).
Append it to result string.
Decrease its count (f += 1 since we use negative freq).
Hold the previous character (if it still has remaining freq) and push it back on the next iteration to avoid adjacent duplicates.
4️⃣ Handle Infeasibility Case:
If prev still has remaining frequency but heap is empty, it means there’s no way to place it without creating adjacent duplicates → return “”.
🧠 Code Snippet:
if prev and not maxHeap:
return “”
5️⃣ Final Step:
Build the string and return the result if successful.
————————————————————-
class Solution:
def reorganizeString(self, s: str) -> str:
res = “”
hMap = {}
for c in s:
hMap[c] = hMap.get(c, 0) - 1
maxHeap = [[f, c] for c,f in hMap.items()]
heapq.heapify(maxHeap)
prev = None
while maxHeap or prev:
if prev and not maxHeap:
return “”
f, c = heapq.heappop(maxHeap)
res += c
f += 1
if prev:
heapq.heappush(maxHeap, prev)
prev = None
if f!=0:
prev = [f, c]
return res
📝 15. 3Sum
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
We find distinct triplets that sum up to 0:
-1 + -1 + 2 = 0
-1 + 0 + 1 = 0
Duplicates are skipped during iteration.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation:
No combination of three numbers adds up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation:
Only one valid triplet exists, all elements are zero.
Answer (O(n²) Approach):
1️⃣ Sort the array:
Start by sorting nums so that we can use two-pointer technique effectively.
📌 nums.sort()
2️⃣ Iterate through the array:
Use a loop for index i and consider nums[i] as the first number in the triplet. Skip duplicate nums[i] values to avoid duplicate triplets.
3️⃣ Apply two-pointer technique:
For each i, set two pointers:
l = i + 1 (left pointer)
r = len(nums) - 1 (right pointer)
Move the pointers inward based on the sum:
If the sum is less than 0 → l += 1
If the sum is greater than 0 → r -= 1
If sum equals 0 → valid triplet, add to result and skip duplicates.
4️⃣ Skip duplicate pairs:
After finding a valid triplet, move the pointers and skip any duplicate values to ensure uniqueness.
if total == 0:
res.append([n, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
————————————————————-
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, n in enumerate(nums):
if n>0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
total = n + nums[l] + nums[r]
if total > 0:
r -= 1
elif total < 0:
l += 1
else:
res.append([n, nums[l], nums[r]])
l += 1
r -= 1
while nums[l]==nums[l-1] and l<r:
l += 1
return res
📝 863. All Nodes Distance K in Binary Tree
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes at a distance 2 from node 5 are 7 and 4 (from subtree), and 1 (via parent 3).
Example 2:
Input: root = [1], target = 1, k = 3
Output: []
Explanation: The tree has only one node. No nodes exist at distance 3.
Answer (O(N) Time & Space using Adjacency List + BFS):
1️⃣ Build an Undirected Graph:
Use DFS to connect each node bidirectionally with its parent and children in an adjacency list.
➡ graph[node.val].append(parent.val) and vice versa.
2️⃣ Start BFS from the Target Node:
Initialize a queue with (target.val, 0) and a visited set.
3️⃣ Level Order Traversal with BFS:
Traverse the graph level by level. Add neighbors of the current node if they haven’t been visited.
➡ When distance == k, collect the node in the result list.
4️⃣ Return Result List:
All nodes in the queue at distance k are part of the final result.
💡 Code Snippet: q.append((target.val, 0))
————————————————————-
Answer (O(N) Time using Pure DFS Traversal):
1️⃣ Recursive DFS from Target Node:
Traverse downward from the target node to collect all nodes at distance k in the subtree.
➡ dfs(node, dist) if dist == k, add node to result.
2️⃣ Backtrack to Parent Nodes:
If target is found in left/right subtree, backtrack to parent. Track distance from target to parent.
3️⃣ Explore Opposite Subtree of Ancestors:
When backtracking, for every ancestor node, explore its opposite child subtree at remaining distance: k - (distance from target to ancestor + 1).
4️⃣ Collect and Return All Nodes at Distance K:
During traversal, if ancestor is at distance k from target, include it. Otherwise, explore its other child subtree.
💡 Code Snippet:
if left + 1 == k:
res.append(node.val)
else:
dfs(node.right, left + 2)
————————————————————-
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
graph = collections.defaultdict(list)
def buildGraph(node, parent):
if not node:
return
if parent:
graph[parent.val].append(node.val)
graph[node.val].append(parent.val)
buildGraph(node.left, node)
buildGraph(node.right, node)
buildGraph(root, None)
visited = set()
q = collections.deque()
q.append((target.val, 0))
res = []
while q:
nodeVal, dist = q.popleft()
if nodeVal in visited:
continue
visited.add(nodeVal)
if dist == k:
res.append(nodeVal)
elif dist < k:
for neighbor in graph[nodeVal]:
if neighbor not in visited:
q.append((neighbor, dist+1))
return res
# res = []
# def dfs(node, dist):
# if not node:
# return
# if dist == k:
# res.append(node.val)
# return 0
# dfs(node.left, dist+1)
# dfs(node.right, dist+1)
# def findTarget(node):
# if not node:
# return -1
# if node == target:
# dfs(node, 0)
# return 0
# left = findTarget(node.left)
# if left != -1:
# if left + 1 == k:
# res.append(node.val)
# else:
# dfs(node.right, left+2)
# return left+1
# right = findTarget(node.right)
# if right != -1:
# if right + 1 == k:
# res.append(node.val)
# else:
# dfs(node.left, right+2)
# return right+1
# return -1
# findTarget(root)
# return res
📝 124. Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes connected by edges, and a node can appear at most once in a path. The path does not need to go through the root. The goal is to find the maximum path sum of any such path in the binary tree.
Example 1:
Input: root = [1, 2, 3]
Output: 6
Explanation: The optimal path is 2 → 1 → 3, and the sum is 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 → 20 → 7, and the sum is 15 + 20 + 7 = 42.
Answer (O(n) Approach — DFS traversal):
1️⃣ Use DFS to traverse the tree:
We use a recursive function dfs(node) to compute the maximum gain from each subtree rooted at node.
2️⃣ Ignore negative path sums:
At each node, we calculate the maximum gain from the left and right children, but ignore them if they’re negative, i.e.,
left = max(0, dfs(node.left))
3️⃣ Update the global result with max split path sum:
At each node, consider a “split path” — path that passes through left → node → right.
We update the result as:
res[0] = max(res[0], node.val + left + right)
4️⃣ Return max gain to parent:
Only one side (left or right) can be chosen when returning to parent — no split allowed.
Return: node.val + max(left, right)
➡️ Code snippet:
res[0] = max(res[0], node.val + left + right)
return node.val + max(left, right)
————————————————————-
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
res = [root.val]
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
left = max(0, left)
right = max(0, right)
res[0] = max(res[0], node.val + left + right) # Split at node
return node.val + max(left, right) # No split.
dfs(root)
return res[0]
📝 297. Serialize and Deserialize Binary Tree
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Explanation:
The binary tree is:
1
/ \
2 3
/ \
4 5
Serialization converts this tree to a string format (e.g., “1,2,N,N,3,4,N,N,5,N,N”), where “N” represents null. Deserialization reconstructs the tree from this string using the same traversal order.
Example 2:
Input: root = []
Output: []
Explanation:
An empty tree serializes to just “N” and deserializes back to an empty tree.
Answer (O(n) DFS Approach):
1️⃣ Serialization using Preorder Traversal (DFS)
Traverse the tree in preorder: root ➝ left ➝ right.
Append each node’s value to a list; append “N” for None nodes.
Example snippet:
if not node:
res.append(“N”)
2️⃣ Join the Serialized List into a String
After DFS traversal, convert the list into a string with commas to represent the serialized tree.
Example: “1,2,N,N,3,4,N,N,5,N,N”.
3️⃣ Deserialization by Recursively Reading Values (DFS)
Use a pointer/index (self.i) to iterate through the serialized data list.
For each value, create a TreeNode or return None for “N”.
Recursively assign left and right children.
4️⃣ Tree Rebuilding Matches DFS Order
Since serialization was preorder, deserialization must also follow preorder logic.
The recursive structure naturally rebuilds the original tree.
————————————————————-
class Codec:
def serialize(self, root):
res = []
def dfs(node):
if not node:
res.append(“N”)
return
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return “,”.join(res)
def deserialize(self, data):
self.i = 0
arr = data.split(",")
def dfs():
if arr[self.i] == "N":
self.i += 1
return None
node = TreeNode(int(arr[self.i]))
self.i += 1
node.left = dfs()
node.right = dfs()
return node
return dfs()
📝 139. Word Break
Example 1:
Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:
Input: s = “applepenapple”, wordDict = [“apple”,”pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Note: Dictionary words can be reused.
Example 3:
Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: false
Answer (🕐 Time Complexity: O(n * m), where n = length of s, m = average length of words in wordDict):
1️⃣ Initialize DP array:
Create a boolean array dp of size len(s)+1 where dp[i] indicates if the substring s[0:i] can be segmented using the dictionary.
dp = [False] * (len(s) + 1)
dp[0] = True
2️⃣ Iterate over the string:
Loop through i = 1 to len(s) to check for each possible position whether it can be segmented.
3️⃣ Check each dictionary word:
For each index i, check if there is a word in wordDict that ends at position i and if dp[i - len(word)] is True (which means substring up to that point is segmentable).
if s[i - len(word):i] == word and dp[i - len(word)]:
dp[i] = True
4️⃣ Return final result:
If dp[len(s)] is True, it means the string can be fully segmented using the words in the dictionary.
return dp[len(s)]
————————————————————-
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s)+1)
dp[0] = True
for i in range(1, len(s)+1):
for word in wordDict:
if i - len(word) >= 0 and dp[i -len(word)]:
if s[i - len(word): i] == word:
dp[i] = True
break
return dp[len(s)]
