Blind 75 Leetcode problems are a very popular list of Leetcode problems summarized by Yangshun Tay. These include common interviewing topics like Array, Binary, Dynamic Programming, Graph, Interval, Linked List, Matrix, String, and Heap. If you have a short period of time to prepare for interviews, this list is a good start to help you quickly learn patterns so that you can apply and solve similar problems.
Recently, Yangshun created an updated version of Blind 75 called Grind 75. You can check it out at www.grind75.com.
Below are the Blind 75 Leetcode problems organized by topic as well as my solutions to them.
• Array & Map
https://leetcode.com/problems/two-sum/
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
lookup = {}
for i in range(len(nums)):
otherNum = target - nums[i]
if otherNum in lookup:
return [i, lookup[otherNum]]
lookup[nums[i]] = i
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
class Solution:
def maxProfit(self, prices: List[int]) -> int:
minP = prices[0]
ans = 0
k = len(prices)
for i in range(1, k):
ans = max(ans, prices[i] - minP)
minP = min(minP, prices[i])
return ans
https://leetcode.com/problems/contains-duplicate/
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
lookup = {}
for num in nums:
if num in lookup:
return True
lookup[num] = lookup.get(num, 0) + 1
return False
https://leetcode.com/problems/product-of-array-except-self/
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans, l, r = [None] * n, [None] * n, [None] * n
l[0] = 1
r[n - 1] = 1
for i in range(1, n):
l[i] = l[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
r[i] = r[i + 1] * nums[i + 1]
for i in range(n):
ans[i] = l[i] * r[i]
return ans
https://leetcode.com/problems/maximum-subarray/
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = float('-inf')
running_sum = 0
for num in nums:
if running_sum < 0:
running_sum = num
else:
running_sum = running_sum + num
ans = max(ans, running_sum)
return ans
https://leetcode.com/problems/maximum-product-subarray/
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
maxN, minN, ans = nums[0], nums[0], nums[0]
for i in range(1, n):
mx = maxN
mn = minN
ans = max(ans, max(nums[i], max(nums[i] * maxN, nums[i] * minN)))
maxN = max(nums[i], max(nums[i] * mx, nums[i] * mn))
minN = min(nums[i], min(nums[i] * mx, nums[i] * mn))
return ans
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
class Solution:
def findMin(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] <= nums[r]:
r = mid
else:
l = mid + 1
return nums[l]
https://leetcode.com/problems/search-in-rotated-sorted-array/
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]:
if nums[l] <= target and target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target and target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1
https://leetcode.com/problems/3sum/
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
nums = sorted(nums)
n = len(nums)
for i in range(0, n - 2):
j = i + 1
k = n - 1
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
while j < k:
total = nums[i] + nums[j] + nums[k]
if total > 0:
k -= 1
elif total < 0:
j += 1
else:
ans.append([nums[i], nums[j], nums[k]])
j += 1
k -= 1
while j < k and nums[j] == nums[j - 1]:
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
return ans
https://leetcode.com/problems/container-with-most-water/
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = 0
l = 0
r = len(height) - 1
while l < r:
area = (r - l) * min(height[l], height[r])
max_area = max(area, max_area)
if height[l] <= height[r]:
l += 1
else:
r -= 1
return max_area
• Binary
https://leetcode.com/problems/sum-of-two-integers/
class Solution:
def getSum(self, a: int, b: int) -> int:
MASK = 0xFFF
INT_MAX = 0x7FF
sumVal = (a ^ b) & MASK
carry = ((a & b) << 1) & MASK
while carry:
return self.getSum(sumVal, carry)
return sumVal if sumVal <= INT_MAX else ~ (sumVal ^ MASK)
https://leetcode.com/problems/number-of-1-bits/
class Solution:
def hammingWeight(self, n: int) -> int:
cnt = 0
while n:
if n & 1 > 0:
cnt += 1
n = n >> 1
return cnt
https://leetcode.com/problems/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
https://leetcode.com/problems/missing-number/
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
k = 0
for i in range(1, n + 1):
k ^= i
k ^= nums[i - 1]
return k
https://leetcode.com/problems/reverse-bits/
class Solution:
def reverseBits(self, n: int) -> int:
ans = 0
for _ in range(32):
ans <<= 1
ans |= n & 1
n >>= 1
return ans
• Dynamic Programming
https://leetcode.com/problems/climbing-stairs/
class Solution:
def climbStairs(self, n: int) -> int:
dp = [None] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
dp[i] = dp[i - 2] + dp[i - 1]
return dp[n]
https://leetcode.com/problems/coin-change/
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:
dp[i] = min(dp[i], dp[i - c] + 1)
return -1 if dp[amount] == float('inf') else dp[amount]
https://leetcode.com/problems/longest-increasing-subsequence/
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
ans = [1] * len(nums)
for i in range(len(nums) - 1, -1, -1):
for j in range(i + 1, len(nums)):
if nums[i] < nums[j]:
ans[i] = max(ans[i], ans[j] + 1)
return max(ans)
https://leetcode.com/problems/longest-common-subsequence/
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
dp = [[ 0 for j in range(n + 1) ] for i in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
https://leetcode.com/problems/word-break/
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
w = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(0, i):
if dp[j] and s[j:i] in w:
dp[i] = True
break
return dp[n]
https://leetcode.com/problems/combination-sum-iv/
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for x in nums:
if i - x >= 0:
dp[i] += dp[i - x]
return dp[target]
https://leetcode.com/problems/house-robber/
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * (n + 1)
dp[1] = nums[0]
if n == 1:
return nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2])
return dp[n]
https://leetcode.com/problems/house-robber-ii/
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
n -= 1
dp1 = [0] * (n + 1)
dp2 = [0] * (n + 1)
dp1[1] = nums[0]
dp2[1] = nums[1]
for i in range(2, n + 1):
dp1[i] = max(dp1[i - 1], nums[i - 1] + dp1[i - 2])
dp2[i] = max(dp2[i - 1], nums[i] + dp2[i - 2])
return max(dp1[n], dp2[n])
https://leetcode.com/problems/decode-ways/
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(0, n):
if s[i] > '0':
dp[i + 1] = dp[i]
if (i > 0 and (s[i - 1] == '1' or (s[i - 1] == '2' and s[i] <= '6'))):
dp[i + 1] += dp[i - 1]
return dp[n]
https://leetcode.com/problems/unique-paths/
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[ 0 for j in range(n + 1) ] for i in range(m + 1)]
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
d = {}
def helper(i , j):
if i > m or j > n:
return 0
if i == m - 1 and j == n - 1:
return 1
if (i, j) in d:
return d[(i, j)]
d[(i, j)] = helper(i + 1, j) + helper(i, j + 1)
return d[(i, j)]
return helper(0, 0)
https://leetcode.com/problems/jump-game/
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
step = nums[0]
for i in range(n):
if i + nums[i] >= n - 1:
return True
if step <= 0:
return False
step = max(step - 1, nums[i + 1])
return False
https://leetcode.com/problems/longest-palindromic-substring/
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
max = 0
L, R = 0, 0
dp = [[ 0 for j in range(n + 1) ] for i in range(n + 1)]
for i in range(n):
for j in range(i, -1, -1):
if s[j] == s[i] and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
if (i - j + 1) > max:
max = i - j + 1
L = j
R = i
return s[L:R + 1]
https://leetcode.com/problems/palindromic-substrings/
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
ans = 0
dp = [[ 0 for j in range(n) ] for i in range(n)]
for i in range(n):
for j in range(i, -1, -1):
if s[j] == s[i] and (i - j <= 2 or dp[j + 1][i - 1]):
ans += 1
dp[j][i] = True
return ans
• Interval
https://leetcode.com/problems/insert-interval/
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
arr = []
ans = []
flag = False
for x in intervals:
arr.append(x)
for i in range(len(arr)):
if arr[i][0] >= newInterval[0]:
arr.insert(i, newInterval)
flag = True
break
if not flag:
arr.append(newInterval)
for x in arr:
if len(ans) == 0 or ans[-1][1] < x[0]:
ans.append(x)
else:
ans[-1][1] = max(ans[-1][1], x[1])
return ans
https://leetcode.com/problems/merge-intervals/
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
ans = []
intervals.sort()
for x in intervals:
if len(ans) == 0 or ans[-1][1] < x[0]:
ans.append(x)
else:
ans[-1][1] = max(ans[-1][1], x[1])
return ans
https://leetcode.com/problems/non-overlapping-intervals/
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
r = float('-inf')
ans = 0
intervals.sort()
for x in intervals:
if r > x[0]:
r = min(r, x[1])
ans += 1
else:
r = x[1]
return ans
https://leetcode.com/problems/meeting-rooms/
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
if len(intervals) <= 1:
return True
intervals.sort()
r = -1
for x in intervals:
if x[0] < r:
return False
r = x[1]
return True
https://leetcode.com/problems/meeting-rooms-ii/
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
start = sorted([i[0] for i in intervals])
end = sorted([i[1] for i in intervals])
ans, cnt = 0, 0
s, e = 0, 0
while s < len(intervals):
if start[s] < end[e]:
s += 1
cnt += 1
else:
e += 1
cnt -= 1
ans = max(ans, cnt)
return ans
• String
https://leetcode.com/problems/longest-substring-without-repeating-characters/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
unique = set()
l = 0
ans = 0
for r in range(len(s)):
while s[r] in unique:
unique.remove(s[l])
l += 1
unique.add(s[r])
ans = max(ans, r - l + 1)
return ans
https://leetcode.com/problems/valid-anagram/
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
tracker = defaultdict(int)
for c in s:
tracker[c] += 1
for c in t:
tracker[c] -= 1
for x in tracker.values():
if x != 0:
return False
return True
https://leetcode.com/problems/group-anagrams/
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dct = defaultdict(list)
for s in strs:
tracker = [0] * 26
for c in s:
tracker[ord(c) - ord('a')] += 1
k = tuple(tracker)
dct[k].append(s)
return dct.values()
https://leetcode.com/problems/valid-parentheses/
class Solution:
def isValid(self, s: str) -> bool:
lookup = {")": "(",
"}": "{",
"]": "["}
stack = []
for i in range(len(s)):
if s[i] not in lookup:
stack.append(s[i])
else:
if len(stack) == 0 or stack[-1] != lookup[s[i]]:
return False
stack.pop()
return len(stack) == 0
https://leetcode.com/problems/valid-palindrome/
class Solution:
def isPalindrome(self, s: str) -> bool:
l = 0
r = len(s) - 1
s = s.lower()
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
https://leetcode.com/problems/encode-and-decode-strings/
class Codec:
def encode(self, strs: List[str]) -> str:
encoded = ''
for s in strs:
for c in s:
encoded += str(ord(c)) + ';'
encoded += '#'
return encoded
def decode(self, s: str) -> List[str]:
decoded = []
for st in s.split('#')[:-1]:
word = ''
for char in st.split(';')[:-1]:
word += chr(int(char))
decoded.append(word)
return decoded
https://leetcode.com/problems/minimum-window-substring/
class Solution:
def minWindow(self, s: str, t: str) -> str:
ans = ''
cnt = 0
mnLen = float('inf')
cur = {}
tDict = {}
for c in t:
tDict[c] = tDict.get(c, 0) + 1
i = 0
for j in range(len(s)):
if s[j] in tDict:
cur[s[j]] = cur.get(s[j], 0) + 1
if cur[s[j]] == tDict[s[j]]:
cnt += 1
while cnt == len(tDict):
if j - i + 1 < mnLen:
ans = s[i : j + 1]
mnLen = j - i + 1
if s[i] in tDict:
cur[s[i]] = cur.get(s[i], 0) - 1
if cur[s[i]] == tDict[s[i]] - 1:
cnt -= 1
i += 1
return ans
https://leetcode.com/problems/longest-repeating-character-replacement/
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
cnt = [0] * 26
ans, maxNm = 0, 0
l = 0
for i in range(len(s)):
cnt[ord(s[i]) - ord('A')] += 1
maxNm = max(maxNm, cnt[ord(s[i]) - ord('A')])
if (i - l + 1 - maxNm) > k:
cnt[ord(s[l]) - ord('A')] -= 1
l += 1
ans = max(ans, i - l + 1)
return ans
• Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
https://leetcode.com/problems/same-tree/
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
https://leetcode.com/problems/invert-binary-tree/
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
temp = self.invertTree(root.right)
root.right = self.invertTree(root.left)
root.left = temp
return root
https://leetcode.com/problems/binary-tree-maximum-path-sum/
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.ans = float('-inf')
def dfs(node):
if node == None:
return 0
l, r = dfs(node.left), dfs(node.right)
self.ans = max(self.ans, l + r + node.val)
return max(0, max(l, r) + node.val)
dfs(root)
return self.ans
https://leetcode.com/problems/binary-tree-level-order-traversal/
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
return ans
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
class Codec:
def serialize(self, root):
ans = []
def dfs(node):
if not node:
ans.append("#")
return
ans.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(ans)
def deserialize(self, data):
vals = deque(data.split(","))
self.i = 0
def dfs():
if vals[self.i] == '#':
self.i += 1
return None
node = TreeNode(int(vals[self.i]))
self.i += 1
node.left = dfs()
node.right = dfs()
return node
return dfs()
https://leetcode.com/problems/subtree-of-another-tree/
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if self.sameTree(root, subRoot):
return True
return (root.left != None and self.isSubtree(root.left, subRoot)) or (root.right != None and self.isSubtree(root.right, subRoot))
def sameTree(self, a, b):
if a == None and b == None:
return True
return a != None and b != None and a.val == b.val and self.sameTree(a.left, b.left) and self.sameTree(a.right, b.right)
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1 : mid + 1], inorder[ : mid])
root.right = self.buildTree(preorder[mid + 1: ], inorder[mid + 1: ])
return root
https://leetcode.com/problems/validate-binary-search-tree/
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def validate(node, low, high):
if not node:
return True
if node.val <= low or node.val >= high:
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root, -float("inf"), float("inf"))
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.ans = None
self.k = k
def dfs(node):
if node is None:
return
dfs(node.left)
self.k -= 1
if self.k == 0:
self.ans = node.val
return
dfs(node.right)
dfs(root)
return self.ans
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
elif p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return root
https://leetcode.com/problems/implement-trie-prefix-tree/
class TrieNode:
def __init__(self):
self.children = {}
self.endOfWord = 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.endOfWord = 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.endOfWord
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.children[c]
return True
https://leetcode.com/problems/design-add-and-search-words-data-structure/
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, node):
cur = node
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)
https://leetcode.com/problems/word-search-ii/
• Heap
https://leetcode.com/problems/top-k-frequent-elements/
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
lookup = {}
ans = []
freq = [[] for i in range(len(nums) + 1)]
for x in nums:
lookup[x] = lookup.get(x, 0) + 1
for key, value in lookup.items():
freq[value].append(key)
for i in range(len(freq) - 1, 0, -1):
for n in freq[i]:
ans.append(n)
if len(ans) == k:
return ans
https://leetcode.com/problems/find-median-from-data-stream/
class MedianFinder:
def __init__(self):
self.pqMin = []
self.pqMax = []
def addNum(self, num: int) -> None:
heapq.heappush(self.pqMin, -1 * num)
if self.pqMin and self.pqMax and (-1 * self.pqMin[0] > self.pqMax[0]):
val = -1 * heapq.heappop(self.pqMin)
heapq.heappush(self.pqMax, val)
if len(self.pqMin) > len(self.pqMax) + 1:
val = -1 * heapq.heappop(self.pqMin)
heapq.heappush(self.pqMax, val)
if len(self.pqMax) > len(self.pqMin) + 1:
val = heapq.heappop(self.pqMax)
heapq.heappush(self.pqMin, -1 * val)
def findMedian(self) -> float:
if len(self.pqMin) > len(self.pqMax):
return -1 * self.pqMin[0]
if len(self.pqMax) > len(self.pqMin):
return self.pqMax[0]
return (-1 * self.pqMin[0] + self.pqMax[0]) / 2
• Matrix
https://leetcode.com/problems/set-matrix-zeroes/
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
if not matrix:
return []
m = len(matrix)
n = len(matrix[0])
rowflag = [1] * m
colflag = [1] * n
for row in range(m):
for col in range(n):
if matrix[row][col] == 0:
rowflag[row] = 0
colflag[col] = 0
for row in range(m):
for col in range(n):
if rowflag[row] == 0 or colflag[col] == 0:
matrix[row][col] = 0
https://leetcode.com/problems/spiral-matrix/
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
ans = []
m = len(matrix)
n = len(matrix[0])
rBegin, rEnd = 0, m - 1
cBegin, cEnd = 0, n - 1
while True:
for i in range(cBegin, cEnd + 1):
ans.append(matrix[rBegin][i])
rBegin += 1
if rBegin > rEnd:
break
for i in range(rBegin, rEnd + 1):
ans.append(matrix[i][cEnd])
cEnd -= 1
if cEnd < cBegin:
break
for i in range(cEnd, cBegin - 1, -1):
ans.append(matrix[rEnd][i])
rEnd -= 1
if rEnd < rBegin:
break
for i in range(rEnd, rBegin - 1, -1):
ans.append(matrix[i][cBegin])
cBegin += 1
if cBegin > cEnd:
break
return ans
https://leetcode.com/problems/rotate-image/
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
i = 0
j = n - 1
while i < j:
for row in range(0, n):
temp = matrix[row][i]
matrix[row][i] = matrix[row][j]
matrix[row][j] = temp
i += 1
j -= 1
for i in range(0, n):
for j in range(0, n - i - 1):
temp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][n - i - 1]
matrix[n - j - 1][n - i - 1] = temp
https://leetcode.com/problems/word-search/
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
n = len(board)
m = len(board[0])
used = [[False for j in range(m)] for i in range(n)]
def dfs(board, word, x, y, idx):
if board[x][y] != word[idx]:
return False
if idx == len(word) - 1:
return True
used[x][y] = True
for d in directions:
nx = x + d[0]
ny = y + d[1]
if nx >= 0 and ny >= 0 and nx < len(board) and ny < len(board[0]) and not used[nx][ny]:
if dfs(board, word, nx, ny, idx + 1):
return True
used[x][y] = False
return False
for i in range(n):
for j in range(m):
if dfs(board, word, i, j, 0):
return True
return False
• Linked List
https://leetcode.com/problems/reverse-linked-list/
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None:
return head
pre = None
cur = head
nxt = None
while cur != None:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None:
return head
ans = self.reverseList(head.next)
head.next.next = head
head.next = None
return ans
https://leetcode.com/problems/linked-list-cycle/
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head == None or head.next == None:
return False
fast, slow = head, head
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
https://leetcode.com/problems/merge-two-sorted-lists/
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 == None or list2 == None:
return list2 if list1 == None else list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
https://leetcode.com/problems/merge-k-sorted-lists/
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
pq = []
for i in lists:
while i != None:
heapq.heappush(pq, i.val)
i = i.next
ans = ListNode(-1)
cur = ans
while pq:
t = ListNode(heapq.heappop(pq))
cur.next = t
cur = cur.next
return ans.next
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if head.next == None:
return None
f, s = head, head
while n:
f = f.next
n -= 1
if f == None:
return head.next
while f != None and f.next != None:
s = s.next
f = f.next
s.next = s.next.next
return head
https://leetcode.com/problems/reorder-list/
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if head == None or head.next == None:
return
pre = None
fast, slow = head, head
while fast != None and fast.next != None:
fast = fast.next.next
pre = slow
slow = slow.next
pre.next = None
cur = slow
pre = None
while cur != None:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
self.flag = False
def merge(a, b):
if a == None or b == None:
return b if a == None else a
self.flag = not self.flag
if self.flag:
a.next = merge(a.next, b)
return a
else:
b.next = merge(a, b.next)
return b
merge(head, pre)
• Graph
https://leetcode.com/problems/clone-graph/
class Solution:
def __init__(self):
self.vis = {}
def cloneGraph(self, node: 'Node') -> 'Node':
if node == None:
return None
if node in self.vis:
return self.vis[node]
cloneNode = Node(node.val, [])
self.vis[node] = cloneNode
for child in node.neighbors:
cloneNode.neighbors.append(self.cloneGraph(child))
return cloneNode
https://leetcode.com/problems/course-schedule/
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
ind = [0] * numCourses
for p in prerequisites:
ind[p[1]] += 1
q = deque()
for i in range(numCourses):
if ind[i] == 0:
q.append(i)
g = [0] * numCourses
for i in range(numCourses):
g[i] = []
for p in prerequisites:
g[p[0]].append(p[1])
while q:
numCourses -= 1
u = q.popleft()
for v in g[u]:
ind[v] -= 1
if ind[v] == 0:
q.append(v)
return numCourses == 0
https://leetcode.com/problems/number-of-islands/
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
m = len(grid)
n = len(grid[0])
def dfs(grid, i, j):
grid[i][j] = '0'
for d in directions:
ni = i + d[0]
nj = j + d[1]
if ni < 0 or nj < 0 or ni == len(grid) or nj == len(grid[0]) or grid[ni][nj] == '0':
continue
dfs(grid, ni, nj)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(grid, i, j)
ans += 1
return ans
https://leetcode.com/problems/longest-consecutive-sequence/
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
ans = 0
unique = set(nums)
for num in unique:
if (num - 1) in unique:
continue
i = 1
while num + i in unique:
i += 1
ans = max(ans, i)
return ans
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
ans = 0
vis = [False] * n
g = [0] * n
for i in range(n):
g[i] = []
for e in edges:
g[e[0]].append(e[1])
g[e[1]].append(e[0])
def dfs(u):
vis[u] = True
for v in g[u]:
if not vis[v]:
dfs(v)
for i in range(n):
if not vis[i]:
dfs(i)
ans += 1
return ans
https://leetcode.com/problems/graph-valid-tree/
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) == 0:
return n == 1
if n - len(edges) >= 2:
return False
d = [0] * n
for p in edges:
d[p[0]] += 1
d[p[1]] += 1
q = deque()
for i in range(n):
if d[i] == 1:
q.append(i)
g = [0] * n
for i in range(n):
g[i] = []
for p in edges:
g[p[0]].append(p[1])
g[p[1]].append(p[0])
while q:
n -= 1
u = q.popleft()
for v in g[u]:
d[v] -= 1
if d[v] == 1:
q.append(v)
return n == 0
https://leetcode.com/problems/pacific-atlantic-water-flow/
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
m = len(heights)
n = len(heights[0])
ans = []
g1 = [[0 for j in range(n + 1)] for i in range(m + 1)]
g2 = [[0 for j in range(n + 1)] for i in range(m + 1)]
def dfs(h, x, y, g):
g[x][y] = 1
for d in directions:
nx = x + d[0]
ny = y + d[1]
if nx >= 0 and ny >= 0 and nx < len(h) and ny < len(h[0]) and h[nx][ny] >= h[x][y] and g[nx][ny] != 1:
dfs(h, nx, ny, g)
for i in range(m):
for j in range(n):
if (i == 0 or j == 0):
dfs(heights, i, j, g1)
if (i == m - 1 or j == n - 1):
dfs(heights, i, j, g2)
for i in range(m):
for j in range(n):
if g1[i][j] == 1 and g2[i][j] == 1:
ans.append((i, j))
return ans
https://leetcode.com/problems/alien-dictionary/