LeetCode Revision Flashcards
(49 cards)
📝 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
-
Key Links
-
Subjects
-
Company
-
Find Us
-
