Array/String
-
#1768 Merge Strings Alternately
Method 1 runs faster than method 2, both are implemented in the same logic.
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
result, len1, len2 = "", len(word1), len(word2)
for i in range(max(len1, len2)):
if i < len1:
result += word1[i]
if i < len2:
result += word2[i]
return resultclass Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
return "".join(a + b for a, b in zip(word1, word2)) + word1[len(word2):] + word2[len(word1):] -
#1071 Greatest Common Divisor of Strings
steps:
- If both strings have common gcd string, then string1 = gcdm and string2 = gcdn, thus we have string1+string2 == gcd*(m+n), so do we have string2 + string1 == gcd*(m+n).
- Thus we have string1 + string2 == string2 + string1, if they have common gcd.
- If they have common gcd string, then gcd of the both lengths is also the length of common gcd string. The first gcd length of letters in str1 or str2 is the result.
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 == str2 + str1:
return str2[:(math.gcd(len(str1), len(str2)))]
return "" -
#1431 Kids With the Greatest Number of Candies
steps:
-
To faster the run time, we can store at least how many candies needed to make the kid having the most candies among them all
-
Then compare each kid's candies with
candies_neededtoo see if they can be the kid with most candies
class Solution:
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
candies_needed = max(candies) - extraCandies
return [c >= candies_needed for c in candies] -
-
#605 Can Place Flowers
steps:
- According to the rules, if a plot and its adjacent plots are empty, then the plot can be planted
- For the first and last plots in the flowerbed, if its next plot or previous plot is empty, then it can be planted
- To make the first and last plots use the same rule as other plots, simply adding an empty plot before the first plot and after the last plot
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if len(flowerbed) == 0:
return n == 0
flowerbed = [0] + flowerbed + [0]
for i in range(1, len(flowerbed)-1):
if flowerbed[i] == 0 and flowerbed[i-1] == 0 and flowerbed[i+1] == 0:
flowerbed[i] = 1
n -= 1
return n <= 0 -
345 Reverse Vowels of a String
steps:
- The problem can be solved by using two pointers
- Pointer A moves from left to right starting from index 0 and stops when it meets a vowel
- Pointer B moves from right to left starting from the last index and stops when it meets a vowel
- Exchange the vowels that pointer A and B points to
- Repeat steps 2-4 until the pointers meet
class Solution:
def reverseVowels(self, s: str) -> str:
s = list(s)
l, r = 0, len(s)-1
vowels = "aeiou"
while l < r:
if s[l].lower() not in vowels:
l += 1
continue
if s[r].lower() not in vowels:
r -= 1
continue
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
return "".join(s) -
#151 Reverse Words in a String
steps:
- If not using python's syntax sugar, two-pointers is a way to solve it efficiently.
class Solution:
def reverseWords(self, s: str) -> str:
# s = s.split()
# l, r = 0, len(s)-1
# while l < r:
# s[l], s[r] = s[r], s[l]
# l += 1
# r -= 1
# return " ".join(s)
return (" ".join(s.split()[::-1])) -
#238 Product of Array Except Self
steps:
-
There are some circumstances to consider when solving the prolem.
- There is no zero in the array
- There is only one zero in the array and the length of the array is greater than the number of zeros
- There is only one zero in the array and length of array is also one
- There are more than one zeros in the array
-
Calculate the product of all the non-zero elements in the array
-
Count the number of zeros in the array
-
For every element in the array, take the corresponding action
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
product = 1
zero = []
for i, n in enumerate(nums):
if n != 0:
product *= n
else:
zero.append(i)
if zero != []:
if len(zero) < len(nums) and len(zero) == 1:
return [0 if i not in zero else product for i, n in enumerate(nums)]
return [0]*len(nums)
else:
return [int(product/n) for n in nums] -
-
#334 Increasing Triplet Subsequence
steps:
- Use two variables to store the first two numbers of the triplet.
- If a third number meets the requirement, the program returns
True
from typing import List
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
if not nums or len(nums) < 3:
return False
first = float('inf')
second = float('inf')
for num in nums:
if num <= first:
first = num
elif num <= second:
second = num
else:
return True
return False -
#443 String Compression
steps:
- To solve the problem, we can use two-pointers.
- One pointer points to the character, the other pointer is used to count the repeating times of the character.
class Solution:
def compress(self, chars: List[str]) -> int:
l, r = 0, 0
s = len(chars)
while l < s:
n = 0
r = l
while r < s and chars[l] == chars[r]:
if chars[l] == chars[r]:
n += 1
r += 1
if n > 1:
for k in range(l + 1, r):
chars.pop(l + 1)
s -= 1
for k in range(len(str(n))):
l = l + 1
chars.insert(l, str(n)[k])
s += 1
l += 1
r = l
return len(chars)
Two pointers
-
#283 Move Zeroes
steps:
- One pointer A points to the number while iterating the array
- The other pointer B keeps track of the number of zeros that have encountered so so far
- When iterating the array, add one to B if A points to a new zero, and swaps numbers if A points to a non-zero element
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
len_nums = len(nums)
if len_nums == 1: return nums
cnt_zero = 0
for i in range(len_nums):
if nums[i] == 0: cnt_zero += 1
elif cnt_zero > 0:
nums[i-cnt_zero], nums[i] = nums[i], 0
return nums -
#392 Is Subsequence
steps:
- If s is the subsequence of t, then for every character in s, if the character is in t, the left characters in s should also be in t.
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
start = -1
for c in s:
start = t.find(c)
if start == -1:
return False
t = t[start+1:]
return True -
#11 Container With Most Water
steps:
- Using two pointers left and right and they moves in the opposite diretions.
- Keeping track of the max_area of the pairs that the program has been checked so far.
- Every time we need to move a pointer, moves the pointer that has a smaller value.
class Solution:
def maxArea(self, height: List[int]) -> int:
if len(height) == 1:
return height
l, r = 0, len(height) - 1
max_area = 0
while l <= r:
area = (r - l) * min(height[l], height[r])
max_area = max(area, max_area)
if height[l] >= height[r]:
r -= 1
else:
l += 1
return max_area -
#1679 Max Number of K-Sum Pairs
steps:
- sort the array from small to large
- use two pointers left and right that move in the opposite directions
- if the sum of two values equals k, add one to the variable
cnt_pairs, the move each pointer one location - if the sum is greater than k, we need to make the sum smaller, so the right pointer moves left one location
- if the sum is smaller than k, we need to make the sum bigger, so the left pointer moves right one locaiton
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
nums.sort()
left, right = 0, len(nums) - 1
cnt_pairs = 0
while left < right:
total = nums[left] + nums[right]
if total == k:
cnt_pairs += 1
left += 1
right -= 1
elif total < k:
left += 1
else:
right -= 1
return cnt_pairs
Sliding Window
-
#643 Maximum Average Subarray I
steps:
- every time move the pointer forward, the sum will subtract the first value and add the latest value
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
k_sum = sum(nums[:k])
window = k_sum
for i in range(1, len(nums)-k+1):
window = window - nums[i-1] + nums[i+k-1]
k_sum = max(k_sum, window)
return k_sum/k -
#1456 Maximum Number of Vowels in a Substring of Given Length
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = "aeiou"
vowels_sum = sum([1 for c in s[:k] if c.lower() in vowels])
window = vowels_sum
for i in range(1, len(s)-k+1):
if s[i-1] in vowels:
window -= 1
if s[i+k-1] in vowels:
window += 1
vowels_sum = max(vowels_sum, window)
return vowels_sum -
#1004 Max Consecutive Ones III
steps：
- calculate the first consecutive ones (along with turning k zeros into k ones), then move the window forward
- if the new element is one, simply adds it to the window
- if the new element is zero, move the left pointer forward one location
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
l=r=0
for r in range(len(nums)):
if nums[r] == 0:
k-=1
if k<0:
if nums[l] == 0:
k+=1
l+=1
return r-l+1 -
#1493 Longest Subarray of 1's After Deleting One Element
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
max_ones = 0
left = 0
zero_count = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > 1: # Shrink the window when more than one zero is present
if nums[left] == 0:
zero_count -= 1
left += 1
max_ones = max(max_ones, right - left)
return max_ones
Prefix Sum
-
#1732 Find the Highest Altitude
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
cur_alt = 0
max_alt = 0
for n in gain:
cur_alt += n
max_alt = max(cur_alt, max_alt)
return max_alt -
#724 Find Pivot Index
steps:
- store the sum of all nums first
- while iterate over the array
nums, sum all the values that has been visited, and calculate the sum of the left part by subtracting the current element's value and the sum of the visited elements' values - compare them to find out the pivot index
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
sum_nums = sum([n for n in nums])
if sum_nums == nums[0]:
return 0
sum_first = 0
for i in range(len(nums)-1):
sum_first += nums[i]
if sum_first == (sum_nums-nums[i+1])/2:
return i+1
return -1
Hash Map / Set
-
#2215 Find the Difference of Two Arrays
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
set_1 = set(nums1)
set_2 = set(nums2)
return [set_1-set_2, set_2-set_1] -
#1207 Unique Number of Occurrences
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
freq = {}
for n in arr:
if n in freq:
freq[n] += 1
else:
freq[n] = 1
return len(set(freq.values())) == len(freq.values()) -
#1657 Determine if Two Strings Are Close
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
return set(word1)==set(word2) and sorted(Counter(word1).values())==sorted(Counter(word2).values()) -
#2352 Equal Row and Column Pairs
steps:
-
one thing that should be noticed: if two rows and one col are the same, the return result should be two
-
check if the sum of a row and a col are the same, then check each element, remember to check every row and every col, so that there won't be any missed
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
sumrow=[]
sumcol=[]
n=len(grid)
for i in range(n):
sumrow.append(sum(grid[i]))
s=0
for j in range(n):
s+=grid[j][i]
sumcol.append(s)
res=0
for i in range(n):
for j in range(n):
if sumrow[i]==sumcol[j]:
test=True
for k in range(n):
if grid[i][k]!=grid[k][j]:
test=False
break
if test:
res+=1
return res -
Stack
-
#2390 Removing Stars From a String
steps:
-
iterate over the string and use a stack to store the elements
-
if a
*is met, pop the last element out from the stack -
if not a
*, push the element to the end of the stack
class Solution:
def removeStars(self, s: str) -> str:
stack_s = []
for c in s:
if c != "*":
stack_s.append(c)
else:
stack_s.pop()
return "".join(stack_s) -
-
#735 Asteroid Collision
- make sure that if the left part moves to the left and the right part moves to the right, then they will never collide
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
while stack and stack[-1] > 0 > a:
if stack[-1] < abs(a):
stack.pop()
continue
elif stack[-1] == abs(a):
stack.pop()
break # this means asteroid must be destroyed (not add to stack in else statement below)
else:
stack.append(a)
return stack -
#394 Decode String
steps:
- store the (string, num) in the stack if it occurs more than once
class Solution:
def decodeString(self, s: str) -> str:
stack = []
current_str = ""
current_num = 0
for char in s:
if char.isdigit():
// in case the number is over 9
current_num = current_num * 10 + int(char)
elif char == '[':
stack.append((current_str, current_num))
current_str, current_num = "", 0
elif char == ']':
last_str, num = stack.pop()
current_str = last_str + current_str * num
else:
current_str += char
return current_str
Queue
-
#933 Number of Recent Calls
steps:
- use a queue to store the requests that are in range every time add a new request to the queue (pop the earliest ones that are not in range in the queue)
from collections import deque
class RecentCounter:
def __init__(self):
self.queue = deque()
self.count = 0
def ping(self, t: int) -> int:
#first add the request to the queue and increment the counter
self.queue.append(t)
self.count += 1
#return the number of request in the range
while self.queue[0] < t -3000:
self.queue.popleft()
self.count -= 1
return self.count -
#649 Dota2 Senate
steps:
-
store each party's indices in its own queue
-
compare the elements from the start of the two queues
-
if the element value is smaller, adds it to the end of the queue
-
if the element value is larger, then it's being banned, delete the element from the queue
from collections import deque
class Solution:
def predictPartyVictory(self, senate: str) -> str:
radiant_queue, dire_queue = deque(), deque()
for i, party in enumerate(senate):
if party == 'R':
radiant_queue.append(i)
else:
dire_queue.append(i)
while radiant_queue and dire_queue:
radiant_index, dire_index = radiant_queue.popleft(), dire_queue.popleft()
# If Radiant bans Dire, add Dire to the end of the queue; vice versa
if radiant_index < dire_index:
radiant_queue.append(radiant_index + len(senate))
else:
dire_queue.append(dire_index + len(senate))
return "Radiant" if radiant_queue else "Dire" -
Linked List
-
#2095 Delete the Middle Node of a Linked List
steps:
-
use two pointers to traverse the linked list
-
one pointer moves forward one location each time while the other moves forward two locations
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
# Empty list or list with one node, no middle to delete
return head
slow = head
fast = head
prev = None
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
# At this point, 'slow' is at the middle, and 'prev' is its predecessor
if prev:
prev.next = slow.next
else:
# If there is no predecessor, it means we are deleting the head
head = head.next
return head -
-
#328 Odd Even Linked List
steps:
- while traversing the list, use two pointers to moves forward two locations each time, and change the previous node's next pointer to point to every other node
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
odd, even = head, head.next
even_head = even # Save the head of the even list
while even and even.next:
odd.next = even.next # Connect odd to the next odd node
odd = odd.next
even.next = odd.next # Connect even to the next even node
even = even.next
odd.next = even_head # Connect the end of the odd list to the head of the even list
return head -
#206 Reverse Linked List
steps:
- Traverse the linked list and use two pointers to remember the previous and current nodes
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev, current = None, head
while current:
tmp = current.next
current.next = prev
prev, current = current, tmp
return prev
-
#2130 Maximum Twin Sum of a Linked List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def pairSum(self, head: Optional[ListNode]) -> int:
values = []
cur = head
while cur:
values.append(cur.val)
cur = cur.next
length = len(values)
twin_sum = values[0] + values[-1]
for i in range(length//2):
twin_sum = max(twin_sum, values[i]+values[length-1-i])
return twin_sum
Binary Tree - DFS
-
#104 Maximum Depth of Binary Tree
steps:
- use dfs to do a bottom-up depth calculation for each node
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def helper(self, root):
if root == None:
return 0
left = self.helper(root.left)
right = self.helper(root.right)
return 1 + max(left, right)
def maxDepth(self, root: Optional[TreeNode]) -> int:
return self.helper(root) -
#872 Leaf-Similar Trees
steps:
- if a node has no left/right node, then it is a leaf
- use dfs to store all the leaves (remember to traverse the two trees in the same order) and then compare them
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def helper(self, root):
leaves = []
if not root.left and not root.right:
leaves.append(root.val)
if root.left:
leaves.extend(self.helper(root.left))
if root.right:
leaves.extend(self.helper(root.right))
return leaves
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if not root1 and not root2:
return True
if not root1 or not root2:
return False
return self.helper(root1) == self.helper(root2)
-
#1448 Count Good Nodes in Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def helper(self, root, val):
if root:
k = self.helper(root.left, max(val,root.val)) + self.helper(root.right, max(val,root.val))
if root.val >= val:
k+=1
return k
return 0
def goodNodes(self, root: TreeNode) -> int:
return self.helper(root, root.val) -
#437 Path Sum III
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def preorder(node: TreeNode, curr_sum) -> None:
nonlocal count
if not node:
return
curr_sum += node.val
if curr_sum == k:
count += 1
h[curr_sum] += 1
preorder(node.left, curr_sum)
preorder(node.right, curr_sum)
h[curr_sum] -= 1
count, k = 0, sum
h = defaultdict(int)
preorder(root, 0)
return count -
#1372 Longest ZigZag Path in a Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestZigZag(self, root: Optional[TreeNode]) -> int:
def helper(root, right, total):
if not root:
return total
l = helper(root.left, False, total+1 if right else 1)
r = helper(root.right, True, total+1 if not right else 1)
return max(l,r)
return helper(root, None, 0) - 1 -
#236 Lowest Common Ancestor of a Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None: return None
if root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p,q)
right = self.lowestCommonAncestor(root.right, p, q)
if left is not None and right is not None: return root
if left is not None and left == root.left: return left
if right is not None and right == root.right : return right
if left is not None: return left
if right is not None: return right
Binary Tree - BFS
-
#199 Binary Tree Right Side View
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node, depth):
if node:
if depth == len(ans):
ans.append(node.val)
dfs(node.right, depth+1)
dfs(node.left, depth+1)
ans = []
dfs(root, 0)
return ans -
#1161 Maximum Level Sum of a Binary Tree
steps：
- a level-order traversal can help
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
if not root:
return 0 # Return 0 or any default value when the tree is empty
q = [root]
level = 0
max_sum = root.val
max_level = 1 # Initialize max_level
while q:
level += 1
level_sum = 0
size = len(q)
for _ in range(size):
node = q.pop(0)
level_sum += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if level_sum > max_sum:
max_sum = level_sum
max_level = level
return max_level
Binary Search Tree
-
#700 Search in a Binary Search Tree
steps:
-
recursively check the node in the tree
-
if the node's val is larger than the target, then check its left child next, vice versa
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def helper(self, root, target):
if root is None: return None
if root.val == target: return root
if root.val < target:
return self.helper(root.right, target)
else:
return self.helper(root.left, target)
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
return self.helper(root, val) -
-
#450 Delete Node in a BST
steps:
- find the target node, switch the value with its right most child in the left side or its left most child in the right side
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root:
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else:
if (not root.left and not root.right): return None
if (not root.left or not root.right):
return root.left if root.left else root.right
temp = root.left
while temp.right:
temp = temp.right
root.val = temp.val
root.left = self.deleteNode(root.left, temp.val)
return root
Graphs - DFS
-
#841 Keys and Rooms
steps:
-
store the rooms that we are going to visit, remember to check duplicates
-
store the rooms that we are have keys, remember to check duplicates
-
compare the length of them
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
room_to_visit = [0]
keys = [0]
while room_to_visit:
temp = room_to_visit.pop(0)
for k in rooms[temp]:
if k not in keys:
room_to_visit.append(k)
keys.append(k)
return len(keys) == len(rooms) -
-
#547 Number of Provinces
steps:
-
the problem is to find the number of connected components in an undirected graph
-
use a list to track visited nodes
-
for each unvisited node, it starts a new DFS traversal, and each traversal identifies a new connected component in the graph
class Solution:
def findCircleNum(self, g: List[List[int]]) -> int:
v = [False] * len(g)
def dfs(i):
for j in range(len(g)):
// checks if there is an edge between node i and node j
if g[i][j] and not v[j]:
v[j] = True
dfs(j)
ans = 0
for i in range(len(g)):
if not v[i]:
dfs(i)
ans += 1
return ans -
-
#1466 Reorder Routes to Make All Paths Lead to the City Zero
class Solution:
def __init__(self):
self.res = 0
def minReorder(self, n: int, connections: List[List[int]]) -> int:
def dfs(child,parent):
for [c, s] in adj[child]:
if c != parent:
self.res += s
dfs(c,child)
adj=[]
for i in range(n):
adj.append([])
for i in connections:
adj[i[0]].append([i[1],1])
adj[i[1]].append([i[0],0])
dfs(0,-1)
return self.res -
##399 Evaluate Division
from typing import List
from collections import defaultdict
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = defaultdict(dict)
for (u, v), val in zip(equations, values):
graph[u][v] = val
graph[v][u] = 1 / val
graph[u][u] = graph[v][v] = 1.0
for k in graph:
for i in graph:
for j in graph:
if i != j and i in graph[k] and k in graph[j]:
graph[i][j] = graph[i][k] * graph[k][j]
result = [graph[u].get(v, -1) for u, v in queries]
return result
Graphs - BFS
-
#1926 Nearest Exit from Entrance in Maze
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
m = len(maze)
n = len(maze[0])
queue = collections.deque()
queue.append((entrance[0], entrance[1], 0))
visited = set()
visited.add((entrance[0], entrance[1]))
while queue:
for _ in range(len(queue)):
r, c, level = queue.popleft()
if [r, c] != entrance:
if r == 0 or r == m-1 or c == 0 or c == n-1:
return level
for nr, nc in [(r, c+1), (r, c-1), (r+1, c), (r-1, c)]:
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and maze[nr][nc] == '.':
queue.append((nr, nc, level + 1))
visited.add((nr, nc))
return -1 -
#994 Rotting Oranges
- remember to update the grid after finishing one round, do not update instantly while traversing each node
from typing import List
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
fresh_oranges = 0
rotten_oranges = deque()
# Count fresh oranges and add rotten oranges to the queue
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
fresh_oranges += 1
elif grid[i][j] == 2:
rotten_oranges.append((i, j, 0))
minutes = 0
# Define 4-directional movements
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while rotten_oranges:
i, j, minutes = rotten_oranges.popleft()
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2
fresh_oranges -= 1
rotten_oranges.append((ni, nj, minutes + 1))
return minutes if fresh_oranges == 0 else -1
Heap / Priority Queue
-
#215 Kth Largest Element in an Array
from heapq import heappush, heappop
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quickselect(nums, k):
left, mid, right = [], [], []
pivot = random.choice(nums)
for num in nums:
if num > pivot:
left.append(num)
elif num < pivot:
right.append(num)
else:
mid.append(num)
if len(left) >= k:
return quickselect(left, k)
if len(left) + len(mid) < k:
return quickselect(right, k - len(left)-len(mid))
return mid[0]
return quickselect(nums, k) -
#2336 Smallest Number in Infinite Set
class SmallestInfiniteSet:
def __init__(self):
self.curr = 1
self.set = set()
def popSmallest(self) -> int:
if self.set:
ans = min(self.set)
self.set.remove(ans)
return ans
else:
self.curr += 1
return self.curr -1
def addBack(self, num: int) -> None:
if self.curr > num:
self.set.add(num) -
#2542 Maximum Subsequence Score
class Solution:
def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
pairs = sorted([(n2, n1) for n1, n2 in zip(nums1, nums2)], reverse=True)
min_heap = []
res = 0
sum_n1 = 0
for n2, n1 in pairs:
sum_n1 += n1
heapq.heappush(min_heap, n1)
if len(min_heap) > k:
sum_n1 -= heapq.heappop(min_heap)
if len(min_heap) == k:
res = max(res, sum_n1 * n2)
return res -
#2462 Total Cost to Hire K Workers
class Solution:
def totalCost(self, costs, k, candidates):
i = 0
j = len(costs) - 1
pq1 = []
pq2 = []
ans = 0
while k > 0:
while len(pq1) < candidates and i <= j:
heapq.heappush(pq1, costs[i])
i += 1
while len(pq2) < candidates and i <= j:
heapq.heappush(pq2, costs[j])
j -= 1
t1 = pq1[0] if pq1 else float('inf')
t2 = pq2[0] if pq2 else float('inf')
if t1 <= t2:
ans += t1
heapq.heappop(pq1)
else:
ans += t2
heapq.heappop(pq2)
k -= 1
return ans
Binary Search
-
#374 Guess Number Higher or Lower
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
# 1 if num is lower than the picked number
# otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
l=1
r=n
while l <= r:
m = (l+r)//2
if guess(m) == 0:
return m
if guess(m) == -1:
r = m-1
if guess(m) == 1:
l = m+1 -
#2300 Successful Pairs of Spells and Potions
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort()
pointer = 0
trace = []
hashmap ={}
stack = []
length = len(potions)
lookup = []
for idx, num in enumerate(potions):
if num in hashmap:
continue
hashmap[num] = length - idx
trace.append(num)
for i in range(potions[-1] + 1):
Pnum = trace[pointer]
if i not in hashmap:
lookup.append(hashmap[Pnum])
continue
lookup.append(hashmap[Pnum])
pointer +=1
for spell in spells:
bar = math.ceil(success / spell)
if bar > len(lookup) - 1:
stack.append(0)
elif bar < 0:
stack.append(lookup[0])
else:
stack.append(lookup[bar])
return stack -
#162 Find Peak Element
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
low=0
high=len(nums)-1
while low<=high:
mid=low+(high-low)//2
if mid>0 and nums[mid]<nums[mid-1]:
high=mid-1
elif mid<len(nums)-1 and nums[mid]<nums[mid+1]:
low=mid+1
else:
return mid -
#875 Koko Eating Bananas
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def check_can_eat(k):
actual_h = 0
for pile in piles:
actual_h += (pile+k-1)//k
return actual_h <= h
l,r = 0,max(piles)
while r-l>1:
m=(l+r)//2
if check_can_eat(m):
r = m
else:
l = m
return r
Backtracking
-
#17 Letter Combinations of a Phone Number
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
DIGITS_TO_LETTERS = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
combinations = []
for d in digits:
temp = []
if combinations == []:
for c in DIGITS_TO_LETTERS[d]:
temp.append(c)
else:
for c in DIGITS_TO_LETTERS[d]:
for com in combinations:
new_com = com + c
temp.append(new_com)
combinations = temp
return combinations -
#216 Combination Sum III
class Solution:
def backtrack(self, ind, n, k, ds, res):
if len(ds) == k and sum(ds) == n:
res.append(ds[:])
return None
for i in range(ind, 10):
ds.append(i)
self.backtrack(i+1, n, k, ds, res)
ds.pop()
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
self.backtrack(1, n, k, [], res)
return res
DP - 1D
-
#1137 N-th Tribonacci Number
class Solution:
def tribonacci(self, n: int) -> int:
previous_three = [0, 1, 1]
if n < 3:
return previous_three[n]
for i in range(3, n+1):
a, b, c = previous_three
a, b, c = b, c, a+b+c
previous_three = [a, b, c]
return previous_three[-1] -
#746 Min Cost Climbing Stairs
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
cost.append(0)
for i in range(len(cost)-3,-1,-1):
cost[i]+=min(cost[i+1],cost[i+2])
return min(cost[0],cost[1]) -
#198 House Robber
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n >= 2:
nums[1] = max(nums[0], nums[1])
for i in range(2, n):
nums[i] = max(nums[i-1], nums[i-2]+nums[i])
return nums[n-1] if n>0 else 0 -
#790 Domino and Tromino Tiling
class Solution:
def numTilings(self, n: int) -> int:
if n <= 2: return n
if n==3: return 5
MD = 1000000007
dp = [1, 2, 5] + [0]*(n-3)
for i in range(3, n):
dp[i] = dp[i-1] * 2 % MD + dp[i-3] % MD
dp[i] = dp[i] % MD
return dp[n-1]
DP - multidimensional
-
#62 Unique Paths
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
row = [1]*n
for i in range(m-1):
new_row = [1]*n
for j in range(n-2, -1, -1):
new_row[j] = new_row[j+1] + row[j]
row = new_row
return row[0] -
#1143 Longest Common Subsequence
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# dp[i][j] = length of longest common subsequence
# between text1[:i] and text2[:j]
dp = [
[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)
]
for i in range(len(text1)):
for j in range(len(text2)):
dp[i + 1][j + 1] = (
(dp[i][j] + 1)
if text1[i] == text2[j]
else max(dp[i + 1][j], dp[i][j + 1])
)
return dp[-1][-1] -
#714 Best Time to Buy and Sell Stock with Transaction Fee
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
pos=-prices[0]
profit=0
for i in range(1,len(prices)):
pos=max(pos,profit-prices[i])
profit=max(profit,pos+prices[i]-fee)
return profit -
#72 Edit Distance
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
w1, w2 = len(word1), len(word2)
@lru_cache(None)
def dp(i, j):
# word1 used up, so all inserts
if i >= w1 : return w2-j
# word2 used up, so all deletes
if j >= w2 : return w1-i
# letters match, so no operation
if word1[i] == word2[j]: return dp(i+1, j+1)
# insert, delete, replace
return min(dp(i,j+1), dp(i+1,j), dp(i+1,j+1)) + 1
return dp(0,0)
Bit Manipulation
-
#338 Counting Bits
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ans -
#136 Single Number
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hashmap = {}
for n in nums:
if n in hashmap:
del hashmap[n]
else:
hashmap[n] = 1
return list(hashmap.keys())[0] -
#1318 Minimum Flips to Make a OR b Equal to c
class Solution:
def minFlips(self, a: int, b: int, c: int) -> int:
a = [int(n) for n in list(str(bin(a)))[2:]]
b = [int(n) for n in list(str(bin(b)))[2:]]
c = [int(n) for n in list(str(bin(c)))[2:]]
length = max(len(a), len(b), len(c))
a = [0] * (length - len(a)) + a
b = [0] * (length - len(b)) + b
c = [0] * (length - len(c)) + c
shift = 0
for i in range(len(c)-1, -1, -1):
if c[i] == 0:
if a[i] != 0:
shift += 1
if b[i] != 0:
shift += 1
if c[i] == 1:
if a[i] == 0 and b[i] == 0:
shift += 1
return shift
Trie
-
#208 Implement Trie (Prefix Tree)
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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.end = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.end -
#1268 Search Suggestions System
from sortedcontainers import SortedList
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
ans = []
for i in range(len(searchWord)):
while products and (i > len(products[0]) - 1 or searchWord[i] != products[0][i]):
products.pop(0)
while products and (i > len(products[-1]) - 1 or searchWord[i] != products[-1][i]):
products.pop()
ans.append(products[:3])
return ans
Intervals
-
#435 Non-overlapping Intervals
class Solution:
def eraseOverlapIntervals(self, points: List[List[int]]) -> int:
ans = 0
arrow = -math.inf
for point in sorted(points, key = lambda x:x[1]):
if(point[0] >= arrow):
arrow = point[1]
else:
ans+=1
return ans -
#452 Minimum Number of Arrows to Burst Balloons
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points = sorted(points, key=lambda x: x[1])
max_high = -float('inf')
cnt = 0
for p in points:
if p[0] > max_high:
cnt += 1
max_high = p[1]
return cnt
Monotonic Stack
-
#739 Daily Temperatures
steps:
-
iterate over the array
days -
create a stack, while iterating over the array, if no higher temp is met, push (temp, index) to the stack, if any day in the stack is lower than the temp, pop it out and calculate how manys days it has been waiting
class Solution:
def __init__(self):
self.stack = []
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
ans = [0]*len(temperatures)
for i, n in enumerate(temperatures):
while stack and self.stack[-1][0] < n:
_, old_i = self.stack.pop()
ans[old_i] = i - old_i
self.stack.append((n, i))
return ans -
-
#901 Online Stock Span
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
counter = 1
while self.stack and self.stack[-1][0] <= price:
counter += self.stack.pop()[1]
self.stack.append((price, counter))
return counter