Introduction
This is Docs about LeetCode Solutions which are written in Python(other programming languages, maybe)
- Github page : www.jimmieluo.com/leetcode-docs
- Source page : github.com/Ross249/leetcode-docs
Plan
Stats
Array And String
Merge Sorted Array
Problem page:https://leetcode.com/problems/merge-sorted-array
Solution
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i = m - 1
j = n - 1
k = m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
Complexity
- time: O(m+n)
- space: O(1)
Remove Element
Problem page:https://leetcode.com/problems/remove-element
Solution
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
length = 0
for i in range(len(nums)):
if nums[i] != val:
nums[length] = nums[i]
length += 1
return length
Complexity
- time: O(n)
- space: O(1)
Remove Duplicates from Sorted Array
Problem page:https://leetcode.com/problems/remove-duplicates-from-sorted-array
Solution
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
res = 1
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
nums[res] = nums[i]
res += 1
return res
Complexity
- time: O(n)
- space: O(1)
Remove Duplicates from Sorted Array II
Problem page:https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
Solution
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
length = len(nums)
if length <= 2:
return length
start = 2
for i in range(2,length):
if nums[i] != nums[start - 2]:
nums[start] = nums[i]
start += 1
return start
Complexity
- time: O(n)
- space: O(1)
Majority Element
Problem page:https://leetcode.com/problems/majority-element
Solution
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = 0
res = 0
for num in nums:
if count == 0 and res != num:
res = num
count += 1
elif res == num:
count += 1
else:
count -= 1
return res
Complexity
- time: O(n)
- space: O(1)
Rotate Array
Problem page:https://leetcode.com/problems/rotate-array
Solution
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
return nums
Complexity
- time: O(n)
- space: O(n)
Best Time to Buy and Sell Stock
Problem page:https://leetcode.com/problems/best-time-to-buy-and-sell-stock
Solution
class Solution:
def maxProfit(self, prices: List[int]) -> int:
buy = prices[0]
profit = 0
for i in range(1, len(prices)):
if prices[i] < buy:
buy = prices[i]
elif prices[i] - buy > profit:
profit = prices[i] - buy
return profit
Complexity
- time: O(n)
- space: O(1)
Best Time to Buy and Sell Stock II
Problem page:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
Solution
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max = 0
start = prices[0]
len1 = len(prices)
for i in range(0 , len1):
if start < prices[i]:
max += prices[i] - start
start = prices[i]
return max
Complexity
- time: O(n)
- space: O(1)
Jump Game
Problem page:https://leetcode.com/problems/jump-game
Solution
class Solution:
def canJump(self, nums: List[int]) -> bool:
value = 0
for n in nums:
if value < 0:
return False
elif n > value:
value = n
value -= 1
return True
Complexity
- time: O(n)
- space: O(1)
Jump Game II
Problem page:https://leetcode.com/problems/jump-game-ii
Solution
class Solution:
def jump(self, nums: List[int]) -> int:
step, end, dp = 0, 0, 0
for i in range(len(nums)-1):
dp = max(dp,i+nums[i])
if i == end: # try to reach
step += 1
end = dp
return step
Complexity
- time: O(n)
- space: O(1)
H-Index
Problem page:https://leetcode.com/problems/h-index
Solution
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
tmp = [0 for _ in range(n + 1)]
for i,v in enumerate(citations):
if v > n:
tmp[n] += 1
else:
tmp[v] += 1
total = 0
for i in range(n, -1, -1):
total += tmp[i]
if total >= i:
return i
Complexity
- time: O(n)
- space: O(n)
Trapping Rain Water
Problem page:https://leetcode.com/problems/trapping-rain-water
Solution
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
res = 0
while left < right:
if left_max < right_max:
left += 1
left_max = max(left_max, height[left])
res += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
res += right_max - height[right]
return res
Complexity
- time: O(n)
- space: O(1)
Gas Station
Problem page:https://leetcode.com/problems/gas-station
Solution
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
s_cost, s_gas = sum(cost), sum(gas)
if s_cost > s_gas:
return -1
c_gas, idx = 0, 0
for i in range(len(gas)):
c_gas += gas[i] - cost[i]
if c_gas < 0:
c_gas = 0
idx = i + 1
return idx
Complexity
- time: O(n)
- space: O(1)
Two Pointers
Valid Palindrome
Problem page:https://leetcode.com/problems/valid-palindrome
Solution
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s)-1
while l < r:
if not s[l].isalnum():
l += 1
elif not s[r].isalnum():
r -= 1
elif s[l].lower() == s[r].lower():
l += 1
r -= 1
else:
return False
return True
Complexity
- time: O(n)
- space: O(1)
Is Subsequence
Problem page:https://leetcode.com/problems/is-subsequence
Solution
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(t) < len(s):
return False
l1,l2 = 0, 0
while l2 < len(t) and l1 < len(s):
if s[l1] == t[l2]:
l1 += 1
l2 += 1
return l1 == len(s)
Complexity
- time: O(n)
- space: O(1)
Two Sum II - Input Array Is Sorted
Problem page:https://leetcode.com/problems/two-sum-ii-input-array-is-sorted
Solution
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l < r:
temp = numbers[l] + numbers[r]
if temp < target:
l += 1
elif temp > target:
r -= 1
else:
return [l + 1, r + 1]
Complexity
- time: O(n)
- space: O(1)
Container With Most Water
Problem page:https://leetcode.com/problems/container-with-most-water
Solution
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r, area = 0, len(height) - 1, 0
while l < r:
temp_area = (r - l) * min(height[l], height[r])
area = max(temp_area,area)
if height[l] < height[r]:
l += 1
else:
r -= 1
return area
Complexity
- time: O(n)
- space: O(1)
3Sum
Problem page:https://leetcode.com/problems/3sum
Solution
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
j = i + 1
k = len(nums) - 1
while j < k:
total = nums[i] + nums[j] + nums[k]
if total > 0:
k -= 1
elif total < 0:
j += 1
else:
res.append([nums[i], nums[j], nums[k]])
j += 1
while nums[j] == nums[j-1] and j < k:
j += 1
return res
Complexity
- time: O(n^2)
- space: O(1)
Sliding Window
Minimum Size Subarray Sum
Problem page:https://leetcode.com/problems/minimum-size-subarray-sum
Solution
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if sum(nums) < target: return 0
sums, l, res = 0, 0, len(nums)
for r, val in enumerate(nums):
sums += val
while sums >= target:
sums -= nums[l]
res = min(res, r - l + 1)
l += 1
return res
Complexity
- time: O(n)
- space: O(1)
Longest Substring Without Repeating Characters
Problem page:https://leetcode.com/problems/longest-substring-without-repeating-characters
Solution
def lengthOfLongestSubstring(self, s: str) -> int:
n, res, left = len(s), 0, 0
filter_set = set()
for r in range(n):
if s[r] not in filter_set:
filter_set.add(s[r])
res = max(res, r - left + 1)
else:
while s[r] in filter_set:
filter_set.remove(s[left])
left += 1
filter_set.add(s[r])
return res
Complexity
- time: O(n)
- space: O(min(m, n)) m is the length of substring
Substring with Concatenation of All Words
Problem page:https://leetcode.com/problems/substring-with-concatenation-of-all-words
Solution
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
word_len, num_words = len(words[0]), len(words)
word_count = Counter(words)
res = []
for i in range(word_len):
l, r, count = i, i, 0
seen = defaultdict(int)
while r + word_len <= len(s):
word = s[r:r+word_len]
r += word_len
if word in word_count:
seen[word] += 1
count += 1
while seen[word] > word_count[word]:
l_word = s[l:l + word_len]
seen[l_word] -= 1
count -= 1
l += word_len
if count == num_words:
res.append(l)
else:
seen.clear()
count = 0
l = r
return res
Complexity
- time: O(n * m), where n is the length of s and m is the length of each word
- space: O(k), where k is the number of unique words in the words list
Minimum Window Substring
Problem page:https://leetcode.com/problems/minimum-window-substring
Solution
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t) > len(s) or not s or not t:
return ""
map = [0] * 128
count, l, r, s_idx = len(t), 0, 0, 0
min_len = float('inf')
for c in t:
map[ord(c)] += 1
while r < len(s):
if map[ord(s[r])] > 0:
count -= 1
map[ord(s[r])] -= 1
r += 1
while count == 0:
if r - l < min_len:
min_len = r - l
s_idx = l
if map[ord(s[l])] == 0:
count += 1
map[ord(s[l])] += 1
l += 1
return "" if min_len == float('inf') else s[s_idx:s_idx + min_len]
Complexity
- time: O(n)
- space: O(1)
Matrix
Spiral Matrix
Problem page:https://leetcode.com/problems/spiral-matrix
Solution
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
rows, cols = len(matrix), len(matrix[0])
row, col = 0, -1
direction = 1
res = []
while rows > 0 and cols > 0:
for _ in range(cols):
col += direction
res.append(matrix[row][col])
rows -= 1
for _ in range(rows):
row += direction
res.append(matrix[row][col])
cols -= 1
direction *= -1
return res
Complexity
- time: O(m * n)
- space: O(m * n)
Spiral Matrix II
Problem page:https://leetcode.com/problems/spiral-matrix-ii
Solution
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
if n == 1:
return [[1]]
rows, cols = n, n
res = [[0 for _ in range(n)] for i in range(n)]
direction, start = 1, 1
row, col = 0, -1
while rows > 0 and cols > 0:
for _ in range(cols):
col += direction
res[row][col] = start
start += 1
rows -= 1
for _ in range(rows):
row += direction
res[row][col] = start
start += 1
cols -= 1
direction *= -1
return res
Complexity
- time: O(n^2)
- space: O(n^2)
Rotate Image
Problem page:https://leetcode.com/problems/rotate-image
Solution
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
top, bottom = 0, n - 1
while top < bottom:
for col in range(n):
temp = matrix[top][col]
matrix[top][col] = matrix[bottom][col]
matrix[bottom][col] = temp
top += 1
bottom -= 1
for r in range(n):
for c in range(r + 1, n):
temp = matrix[r][c]
matrix[r][c] = matrix[c][r]
matrix[c][r] = temp
return matrix
Complexity
- time: O(n^2)
- space: O(1)
Set Matrix Zeroes
Problem page:https://leetcode.com/problems/set-matrix-zeroes
Solution
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
rows, cols = len(matrix), len(matrix[0])
bucket_r, bucket_c = [False] * rows, [False] * cols
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 0:
bucket_r[r] = True
bucket_c[c] = True
for i, r in enumerate(bucket_r):
if r:
for c in range(cols):
matrix[i][c] = 0
for j, c in enumerate(bucket_c):
if c:
for r in range(rows):
matrix[r][j] = 0
Complexity
- time: O(n * m)
- space: O(n + m)
Hashmap
Two Sum
Problem page:https://leetcode.com/problems/two-sum
Solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
collect = {}
n = len(nums)
for i in range(n):
left = target - nums[i]
if left in collect:
return [collect[left],i]
collect[nums[i]] = i
return []
Complexity
- time: O(n)
- space: O(n)
Group Anagrams
Problem page:https://leetcode.com/problems/group-anagrams
Solution
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list)
for word in strs:
s_word = ''.join(sorted(word))
res[s_word].append(word)
return list(res.values())
Complexity
- time: O(n * k log k), where n is the number of strings and k is the maximum length of a string
- space: O(n * k)
Longest Consecutive Sequence
Problem page:https://leetcode.com/problems/longest-consecutive-sequence
Solution
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
bucket = set(nums)
res = 0
table = {}
for num in bucket:
x = table.get(num - 1, 0)
y = table.get(num + 1, 0)
val = x + y + 1
table[num - x] = val
table[num + y] = val
res = max(res, val)
return res
Complexity
- time: O(n)
- space: O(n)
Intervals
Summary Ranges
Problem page:https://leetcode.com/problems/summary-ranges
Solution
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
res = []
if not nums:
return res
start = nums[0]
for i in range(1, len(nums)):
if nums[i] != nums[i-1] + 1:
if start == nums[i - 1]:
res.append(str(start))
else:
res.append(f"{start}->{nums[i-1]}")
start = nums[i]
if start == nums[-1]:
res.append(str(start))
else:
res.append(f"{start}->{nums[-1]}")
return res
Complexity
- time: O(n)
- space: O(n)
Merge Intervals
Problem page:https://leetcode.com/problems/merge-intervals
Solution
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for interval in intervals:
if res[-1][1] < interval[0]:
res.append(interval)
else:
res[-1][1] = max(res[-1][1],interval[1])
return res
Complexity
- time: O(n * log n)
- space: O(n)
Insert Interval
Problem page:https://leetcode.com/problems/insert-interval
Solution
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
i = 0
while i < len(intervals) and intervals[i][1] < newInterval[0]:
res.append(intervals[i])
i += 1
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0],intervals[i][0])
newInterval[1] = max(newInterval[1],intervals[i][1])
i += 1
res.append(newInterval)
while i < len(intervals):
res.append(intervals[i])
i+=1
return res
Complexity
- time: O(n)
- space: O(n)
Minimum Number of Arrows to Burst Balloons
Problem page:https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons
Solution
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key= lambda x : x[0])
res, end = 1, points[0][1]
for balloon in points[1:]:
if balloon[0] > end:
res += 1
end = balloon[1]
else:
end = min(end, balloon[1])
return res
Complexity
- time: O(n)
- space: O(1)
Stack
Valid Parentheses
Problem page:https://leetcode.com/problems/valid-parentheses
Solution
def isValid(self, s: str) -> bool:
stack = []
matching = {")":"(", "}":"{", "]":"["}
for char in s:
if char in matching.values():
stack.append(char)
elif char in matching.keys():
if not stack or matching[char] != stack.pop():
return False
return not stack
Complexity
- time: O(n)
- space: O(n)
Simplify Path
Problem page:https://leetcode.com/problems/simplify-path
Solution
def simplifyPath(self, path: str) -> str:
stack = []
array = path.split('/')
for dir in array:
if dir == '.' or not dir:
continue
elif dir == '..':
if stack:
stack.pop()
else:
stack.append(dir)
return '/' + '/'.join(stack)
Complexity
- time: O(n)
- space: O(n)
Min Stack
Problem page:https://leetcode.com/problems/min-stack
Solution
class MinStack:
def __init__(self):
self.data = []
self.min_stack = []
def push(self, val: int) -> None:
self.data.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.data:
popped = self.data.pop()
if self.min_stack and self.min_stack[-1] == popped:
self.min_stack.pop()
def top(self) -> int:
if self.data:
return self.data[-1]
return -1
def getMin(self) -> int:
if self.min_stack:
return self.min_stack[-1]
return -1
Complexity
- time: O(1)
- space: O(n)
Evaluate Reverse Polish Notation
Problem page:https://leetcode.com/problems/evaluate-reverse-polish-notation
Solution
def evalRPN(self, tokens: List[str]) -> int:
res = []
for c in tokens:
if c == "+":
res.append(int(res.pop()) + int(res.pop()))
elif c == "-":
second, first = res.pop(), res.pop()
res.append(first - second)
elif c == "*":
res.append(int(res.pop()) * int(res.pop()))
elif c == "/":
second, first = res.pop(),res.pop()
res.append(int(int(first) / int(second)))
else:
res.append(int(c))
return res[0]
Complexity
- time: O(n)
- space: O(n)
Linked List
Linked List Cycle
Problem page:https://leetcode.com/problems/linked-list-cycle
Solution
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
Complexity
- time: O(n)
- space: O(1)
Add Two Numbers
Problem page:https://leetcode.com/problems/add-two-numbers
Solution
class Solution(object):
def addTwoNumbers(self, l1, l2):
nHead = ListNode(0)
tail = nHead
carry = 0
while l1 is not None or l2 is not None or carry != 0:
d1 = l1.val if l1 is not None else 0
d2 = l2.val if l2 is not None else 0
sum = d1 + d2 + carry
d = sum % 10
carry = sum // 10
nNode = ListNode(d)
tail.next = nNode
tail = tail.next
l1 = l1.next if l1 is not None else None
l2 = l2.next if l2 is not None else None
res = nHead.next
nHead.next = None
return res
Complexity
- time: O(max(m,n))
- space: O(max(m,n))
Merge Two Sorted Lists
Problem page:https://leetcode.com/problems/merge-two-sorted-lists
Solution
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
sentinel = ListNode()
cur = sentinel
while list1 and list2:
if list1.val > list2.val:
cur.next = list2
list2 = list2.next
else:
cur.next = list1
list1 = list1.next
cur = cur.next
if list1:
cur.next = list1
else:
cur.next = list2
return sentinel.next
Complexity
- time: O(m + n)
- space: O(1)
Copy List with Random Pointer
Problem page:https://leetcode.com/problems/copy-list-with-random-pointer
Solution
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
res = {}
cur = head
while cur:
res[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
res[cur].next = res.get(cur.next)
res[cur].random = res.get(cur.random)
cur = cur.next
return res[head]
Complexity
- time: O(n)
- space: O(1)
LRU Cache
Problem page:https://leetcode.com/problems/lru-cache
Solution
class LRUCache:
_flag = ('data','capacity')
def __init__(self, capacity: int):
self.data: Dict[int,int] = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
return -1 if key not in self.data else self.data.setdefault(key, self.data.pop(key))
def put(self, key: int, value: int) -> None:
try:
self.data.move_to_end(key)
self.data[key] = value
except KeyError:
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)
Complexity
- time: O(1)
- space: O(n)
Reverse Linked List II
Problem page:https://leetcode.com/problems/reverse-linked-list-ii
Solution
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if not head or left == right:
return head
sentinel = ListNode(0,head)
pre = sentinel
for _ in range(left - 1):
pre = pre.next
cur = pre.next
for _ in range(right - left):
temp = cur.next
cur.next = temp.next
temp.next = pre.next
pre.next = temp
return sentinel.next
Complexity
- time: O(n)
- space: O(1)
Remove Duplicates from Sorted List II
Problem page:https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii
Solution
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
sentinel = ListNode(0)
sentinel.next = head
pre,cur = sentinel,head
while cur:
while cur.next and cur.val == cur.next.val:
cur = cur.next
if pre.next == cur:
pre = pre.next
cur = cur.next
else:
pre.next = cur.next
cur = pre.next
return sentinel.next
Complexity
- time: O(n)
- space: O(1)
Partition List
Problem page:https://leetcode.com/problems/partition-list
Solution
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
sHead,lHead = ListNode(0), ListNode(0)
s, l = sHead, lHead
while head is not None:
if head.val < x:
s.next = head
s = s.next
else:
l.next = head
l = l.next
head = head.next
s.next = lHead.next
l.next = None
return sHead.next
Complexity
- time: O(n)
- space: O(1)
Binary Tree
General
Symmetric Tree
Problem page:https://leetcode.com/problems/symmetric-tree
Solution
class Solution:
def helper(self, left: TreeNode, right:TreeNode)->bool:
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val) and self.helper(left.left, right.right) and self.helper(left.right, right.left)
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.helper(root,root)
Complexity
- time: O(n)
- space: O(h)
Construct Binary Tree from Preorder and Inorder Traversal
Problem page:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
Solution
class Solution:
def __init__(self):
self.p = 0
self.i = 0
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def helper(stop):
if self.i < len(inorder) and inorder[self.i] != stop:
root = TreeNode(preorder[self.p])
self.p += 1
root.left = helper(root.val)
self.i += 1
root.right = helper(stop)
return root
return None
return helper(None)
Complexity
- time: O(n)
- space: O(n)
Sum Root to Leaf Numbers
Problem page:https://leetcode.com/problems/sum-root-to-leaf-numbers
Solution
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def helper(node,num):
if not node:
return 0
num = 10 * num + node.val
if not node.left and not node.right:
return num
return helper(node.left,num) + helper(node.right, num)
return helper(root, 0)
Complexity
- time: O(n)
- space: O(h)
Binary Tree Maximum Path Sum
Problem page:https://leetcode.com/problems/binary-tree-maximum-path-sum
Solution
class Solution:
def _max(self, root):
if not root: return -sys.maxsize
l = max(0, self._max(root.left))
r = max(0, self._max(root.right))
self.res = max(self.res, root.val + l + r)
return root.val + max(l, r)
def maxPathSum(self, root):
self.res = -sys.maxsize
self._max(root)
return self.res
Complexity
- time: O(n)
- space: O(h)
BFS
Binary Tree Right Side View
Problem page:https://leetcode.com/problems/binary-tree-right-side-view
Solution
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res = []
if not root:
return res
queue = deque([root])
while queue:
length = len(queue)
for i in range(length):
node = queue.popleft()
if i == length - 1:
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
Complexity
- time: O(n)
- space: O(d)
Binary Tree Level Order Traversal
Problem page:https://leetcode.com/problems/binary-tree-level-order-traversal
Solution
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = deque([root])
res = []
while queue:
length = len(queue)
temp = []
for i in range(length):
node = queue.popleft()
temp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(temp)
return res
Complexity
- time: O(n)
- space: O(d)
Binary Tree Zigzag Level Order Traversal
Problem page:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal
Solution
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = deque([root])
res = []
flag = False
while queue:
length = len(queue)
temp = []
for i in range(length):
node = queue.popleft()
temp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if flag:
temp = temp[::-1]
res.append(temp)
flag = not flag
return res
Complexity
- time: O(n)
- space: O(d)
BST
Minimum Absolute Difference in BST
Problem page:https://leetcode.com/problems/minimum-absolute-difference-in-bst
Solution
class Solution:
def helper(self, node:Optional[TreeNode], values:List[int]):
if node is None:
return
self.helper(node.left,values)
values.append(node.val)
self.helper(node.right,values)
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
values = []
self.helper(root,values)
res = sys.maxsize
for i in range(1, len(values)):
res = min(res, values[i]-values[i-1])
return res
Complexity
- time: O(n)
- space: O(n)
Minimum Absolute Difference in BST
Problem page:https://leetcode.com/problems/minimum-absolute-difference-in-bst
Solution
class Solution:
def helper(self, node:Optional[TreeNode], values:List[int]):
if node is None:
return
self.helper(node.left,values)
values.append(node.val)
self.helper(node.right,values)
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
values = []
self.helper(root,values)
res = sys.maxsize
for i in range(1, len(values)):
res = min(res, values[i]-values[i-1])
return res
Complexity
- time: O(n)
- space: O(n)
Validate Binary Search Tree
Problem page:https://leetcode.com/problems/validate-binary-search-tree
Solution
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def helper(node,min_val, max_val):
if not node:
return True
if (min_val is not None and node.val <= min_val) or (max_val is not None and node.val >= max_val):
return False
return helper(node.left, min_val, node.val) and helper(node.right, node.val, max_val)
return helper(root,-sys.maxsize,sys.maxsize)
Complexity
- time: O(n)
- space: O(1)
Graph
General
Number of Islands
Problem page:https://leetcode.com/problems/number-of-islands
Solution
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
def dfs(i,j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '0'
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
res += 1
dfs(i,j)
return res
Complexity
- time: O(m * n)
- space: O(m * n)
Surrounded Regions
Problem page:https://leetcode.com/problems/surrounded-regions
Solution
class Solution:
def solve(self, board: List[List[str]]) -> None:
rows, cols = len(board), len(board[0])
def capture(r, c):
if r < 0 or c < 0 or r == rows or c == cols or board[r][c] != "O":
return
board[r][c] = "T"
capture(r + 1, c)
capture(r - 1, c)
capture(r, c + 1)
capture(r, c - 1)
for r in range(rows):
for c in range(cols):
if board[r][c] == "O" and (r in [0, rows - 1] or c in [0, cols - 1]):
capture(r, c)
for r in range(rows):
for c in range(cols):
if board[r][c] == "O":
board[r][c] = "X"
for r in range(rows):
for c in range(cols):
if board[r][c] == "T":
board[r][c] = "O"
Complexity
- time: O(m * n)
- space: O(1)
Course Schedule
Problem page:https://leetcode.com/problems/course-schedule
Solution
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
ans = []
for pair in prerequisites:
course = pair[0]
prerequisite = pair[1]
adj[prerequisite].append(course)
indegree[course] += 1
queue = deque()
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
while queue:
current = queue.popleft()
ans.append(current)
for next_course in adj[current]:
indegree[next_course] -= 1
if indegree[next_course] == 0:
queue.append(next_course)
return len(ans) == numCourses
Complexity
- time: O(V + E) vertices edges
- space: O(V + E)
Course Schedule II
Problem page:https://leetcode.com/problems/course-schedule-ii
Solution
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
ans = []
for pair in prerequisites:
course = pair[0]
prerequisite = pair[1]
adj[prerequisite].append(course)
indegree[course] += 1
queue = deque()
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
while queue:
current = queue.popleft()
ans.append(current)
for next_course in adj[current]:
indegree[next_course] -= 1
if indegree[next_course] == 0:
queue.append(next_course)
if len(ans) < numCourses:
return []
return ans
Complexity
- time: O(V + E)
- space: O(V + E)
BFS
Snakes and Ladders
Problem page:https://leetcode.com/problems/snakes-and-ladders
Solution
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
def helper(label):
r, c = divmod(label-1, n)
if r % 2 == 0:
return n - 1 - r, c
else:
return n - 1 - r, n - 1 - c
tmp = set()
queue = deque()
queue.append((1,0))
while queue:
label, step = queue.popleft()
r, c = helper(label)
if board[r][c] != -1:
label = board[r][c]
if label == n ** 2:
return step
for x in range(1, 7):
n_label = label + x
if n_label <= n ** 2 and n_label not in tmp:
tmp.add(n_label)
queue.append((n_label,step + 1))
return -1
Complexity
- time: O(n*n)
- space: O(n*n)
Word Ladder
Problem page:https://leetcode.com/problems/word-ladder
Solution
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
n = len(beginWord)
dicts = defaultdict(list)
for word in wordList:
for i in range(n):
dicts[word[:i] + '*' + word[i+1:]].append(word)
queue = deque([(beginWord, 1)])
visited = set()
visited.add(beginWord)
while queue:
cur, level = queue.popleft()
for i in range(n):
mediate = cur[:i] + '*' + cur[i+1:]
for word in dicts[mediate]:
if word == endWord:
return level + 1
if word not in visited:
visited.add(word)
queue.append((word,level+1))
return 0
Complexity
- time: O(N * M^2) N is the number of words in wordList, and M is the length of each word.
- space: O(N * M^2)
Trie
Implement Trie (Prefix Tree)
Problem page:https://leetcode.com/problems/implement-trie-prefix-tree
Solution
class Trie:
def __init__(self):
self.data = set()
self.pref = set()
def insert(self, word: str) -> None:
cur = ''
for letter in word:
cur += letter
self.pref.add(cur)
self.data.add(word)
def search(self, word: str) -> bool:
return word in self.data
def startsWith(self, prefix: str) -> bool:
return prefix in self.pref
Complexity
- time: O(n) O(1)
- space: O(n * m) n is the number of words, m is the length of words
Word Search II
Problem page:https://leetcode.com/problems/word-search-ii
Solution
class TreeNode:
def __init__(self):
self.children = {}
self.isWord = False
self.refs = 0
def addWord(self, word):
cur = self
cur.refs += 1
for letter in word:
if letter not in cur.children:
cur.children[letter] = TreeNode()
cur = cur.children[letter]
cur.refs += 1
cur.isWord = True
def removeWord(self, word):
cur = self
cur.refs -= 1
for letter in word:
if letter in cur.children:
cur = cur.children[letter]
cur.refs -= 1
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TreeNode()
for w in words:
root.addWord(w)
r,c = len(board), len(board[0])
res, visit = set(), set()
def dfs(row, col, node, word):
if row not in range(r) or col not in range(c) or board[row][col] not in node.children or node.children[board[row][col]].refs < 1 or (row,col) in visit:
return
visit.add((row,col))
node = node.children[board[row][col]]
word += board[row][col]
if node.isWord:
node.isWord = False
res.add(word)
root.removeWord(word)
dfs(row + 1, col, node, word)
dfs(row - 1, col, node, word)
dfs(row , col + 1, node, word)
dfs(row , col - 1, node, word)
visit.remove((row,col))
for row in range(r):
for col in range(c):
dfs(row,col,root,"")
return list(res)
Complexity
- time: O( m+n.(4^k) ) m is the number of letters in words, n is the number of letters on board, k is the max length of words or the depth of tree, 4 is the 4 directions
- space: O(n * m)
Backtracking
Letter Combinations of a Phone Number
Problem page:https://leetcode.com/problems/letter-combinations-of-a-phone-number
Solution
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
dictionary = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
res = []
def helper(index,strs):
if index == len(digits):
res.append(strs[:])
return
for letter in dictionary[digits[index]]:
helper(index + 1, strs + letter)
helper(0,"")
return res
Complexity
- time: O(4^n * n)
- space: O(4^n * n)
Combination Sum
Problem page:https://leetcode.com/problems/combination-sum
Solution
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def helper(index,strs,total):
if total == target:
res.append(strs[:])
return
if total > target or index >= len(candidates):
return
strs.append(candidates[index])
helper(index,strs,total + candidates[index])
strs.pop()
helper(index+1,strs,total)
return res
return helper(0,[],0)
Complexity
- time: O(2^n)
- space: O(n)
Word Search
Problem page:https://leetcode.com/problems/word-search
Solution
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def helper(i, j, k):
if k == len(word):
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
return False
tmp = board[i][j]
board[i][j] = ""
if helper(i+1,j,k+1) or helper(i-1,j,k+1) or helper(i,j-1,k+1) or helper(i,j+1,k+1):
return True
board[i][j] = tmp
return False
for i in range(len(board)):
for j in range(len(board[0])):
if helper(i,j,0):
return True
return False
Complexity
- time: O(n* m * 4^l) l is the depth of search tree
- space: O(l)
Divide & Conquer
Sort List
Problem page:https://leetcode.com/problems/sort-list
Solution
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
left = self.sortList(head)
right = self.sortList(mid)
sentinel = ListNode(0)
cur = sentinel
while left and right:
if left.val < right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
cur.next = left or right
return sentinel.next
Complexity
- time: O(n * log n)
- space: O(log n)
Merge k Sorted Lists
Problem page:https://leetcode.com/problems/merge-k-sorted-lists
Solution
class Solution:
def helper(self, l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
if len(lists) == 1:
return lists[0]
mid = len(lists) // 2
left = self.mergeKLists(lists[:mid])
right = self.mergeKLists(lists[mid:])
return self.helper(left,right)
Complexity
- time: O(n * log m) n is the number of nodes, m is the number of lists
- space: O(log m)
Maximum Subarray
Problem page:https://leetcode.com/problems/maximum-subarray
Solution
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res,cur = nums[0], nums[0]
for num in nums[1:]:
cur = max(num, cur + num)
res = max(res, cur)
return res
Complexity
- time: O(n)
- space: O(1)
Maximum Sum Circular Subarray
Problem page:https://leetcode.com/problems/maximum-sum-circular-subarray
Solution
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total,cur_max,cur_min = 0,0,0
max_sum, min_sum = -sys.maxsize-1,sys.maxsize
for num in nums:
total += num
cur_max = max(cur_max + num,num)
cur_min = min(cur_min + num, num)
max_sum = max(max_sum,cur_max)
min_sum = min(cur_min, min_sum)
return max_sum if max_sum < 0 else max(max_sum, total - min_sum)
Complexity
- time: O(n)
- space: O(1)
Binary Search
Search a 2D Matrix
Problem page:https://leetcode.com/problems/search-a-2d-matrix
Solution
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
mid_row, mid_col = divmod(mid, n)
if matrix[mid_row][mid_col] == target:
return True
elif matrix[mid_row][mid_col] < target:
left = mid + 1
else:
right = mid - 1
return False
Complexity
- time: O(log(m*n))
- space: O(1)
Search in Rotated Sorted Array
Problem page:https://leetcode.com/problems/search-in-rotated-sorted-array
Solution
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Complexity
- time: O(log n)
- space: O(1)
Median of Two Sorted Arrays
Problem page:https://leetcode.com/problems/median-of-two-sorted-arrays
Solution
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m,n = len(nums1), len(nums2)
low, high = 0, m
while low <= high:
position_x = (low + high) // 2
position_y = (m + n + 1) // 2 - position_x
max_x = -sys.maxsize if position_x == 0 else nums1[position_x - 1]
max_y = -sys.maxsize if position_y == 0 else nums2[position_y - 1]
min_x = sys.maxsize if position_x == m else nums1[position_x]
min_y = sys.maxsize if position_y == n else nums2[position_y]
if max_x <= min_y and max_y <= min_x:
if (m + n) % 2 == 0:
return (max(max_x,max_y) + min(min_x, min_y)) / 2
else:
return max(max_x,max_y)
elif max_x > min_y:
high = position_x - 1
else:
low = position_x + 1
Complexity
- time: O(log(min(m, n)))
- space: O(1)
Search Insert Position
Problem page:https://leetcode.com/problems/search-insert-position
Solution
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return left
Complexity
- time: O(log n)
- space: O(1)
Heap
Kth Largest Element in an Array
Problem page:https://leetcode.com/problems/kth-largest-element-in-an-array
Solution
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# Initialize an empty list
k_numbers_min_heap = []
# Add first k elements to the list
for i in range(k):
k_numbers_min_heap.append(nums[i])
# Convert the list into a min-heap
heapq.heapify(k_numbers_min_heap)
# Loop through the remaining elements in the 'nums' array
for i in range(k, len(nums)):
# Compare the current element with the minimum
# element (root) of the min-heap
if nums[i] > k_numbers_min_heap[0]:
# Remove the smallest element
heapq.heappop(k_numbers_min_heap)
# Add the current element
heapq.heappush(k_numbers_min_heap, nums[i])
# The root of the heap has the Kth largest element
return k_numbers_min_heap[0]
Complexity
- time: O(n + k log k)
- space: O(k)
Find Median from Data Stream
Problem page:https://leetcode.com/problems/find-median-from-data-stream
Solution
class MedianFinder:
def __init__(self):
self.min_heap = []
self.max_heap = []
def addNum(self, num: int) -> None:
heapq.heappush(self.max_heap, -1 * num)
if (self.max_heap and self.min_heap) and -1 * self.max_heap[0] > self.min_heap[0]:
val = -1 * heapq.heappop(self.max_heap)
heapq.heappush(self.min_heap,val)
if len(self.max_heap) > len(self.min_heap) + 1:
val = -1 * heapq.heappop(self.max_heap)
heapq.heappush(self.min_heap, val)
elif len(self.min_heap) > len(self.max_heap) + 1:
val = heapq.heappop(self.min_heap)
heapq.heappush(self.max_heap, -1 * val)
def findMedian(self) -> float:
if len(self.max_heap) > len(self.min_heap):
return -1 * self.max_heap[0]
elif len(self.max_heap) < len(self.min_heap):
return self.min_heap[0]
else:
return (-1 * self.max_heap[0] + self.min_heap[0]) / 2
Complexity
- time: O(log n)
- space: O(n)
Find K Pairs with Smallest Sums
Problem page:https://leetcode.com/problems/find-k-pairs-with-smallest-sums
Solution
class Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
res = []
pq = []
for num in nums1:
heapq.heappush(pq,[num + nums2[0], 0])
print(pq)
while k > 0 and pq:
pair = heapq.heappop(pq)
small, pos = pair[0], pair[1]
res.append([small - nums2[pos],nums2[pos]])
if pos + 1 < len(nums2):
heapq.heappush(pq,[small - nums2[pos] + nums2[pos + 1], pos + 1])
k -= 1
return res
Complexity
- time: O(k * log(n1))
- space: O(n1 + k)
Bit Manipulation
Single Number
Problem page:https://leetcode.com/problems/single-number
Solution
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for num in nums:
res ^= num
return res
Complexity
- time: O(n)
- space: O(1)
Single Number II
Problem page:https://leetcode.com/problems/single-number-ii
Solution
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones, twos = 0, 0
for num in nums:
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
print(str(ones)+",")
print(str(twos)+"\n")
return ones
Complexity
- time: O(n)
- space: O(1)
Math
Factorial Trailing Zeroes
Problem page:https://leetcode.com/problems/factorial-trailing-zeroes
Solution
class Solution:
def trailingZeroes(self, n: int) -> int:
res = 0
i = 5
while n / i:
count = n // i
res += count
i = i * 5
return res
Complexity
- time: O(log n)
- space: O(1)
Pow(x, n)
Problem page:https://leetcode.com/problems/powx-n
Solution
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
x **= -1
n *= -1
if n % 2 == 1:
return x * self.myPow(x, n - 1)
else:
num = self.myPow(x, n // 2)
return num * num
Complexity
- time: O(log n)
- space: O(log n)
Dynamic Programming
1 Dimension
House Robber
Problem page:https://leetcode.com/problems/house-robber
Solution
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
return dp[-1]
Complexity
- time: O(n)
- space: O(n)
Coin Change
Problem page:https://leetcode.com/problems/coin-change
Solution
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
min_coins = [amount + 1] * (amount + 1)
min_coins[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i - c >= 0:
min_coins[i] = min(min_coins[i], 1 + min_coins[i - c])
return min_coins[-1] if min_coins[-1] != amount + 1 else -1
Complexity
- time: O(n * m) n is the length of coins, m is amount
- space: O(m)
Word Break
Problem page:https://leetcode.com/problems/word-break
Solution
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
for w in wordDict:
start = i - len(w)
if start >= 0 and dp[start] and s[start:i] == w:
dp[i] = True
break
return dp[-1]
Complexity
- time: O(n * m * k) n is length of input string, m is number of words in wordDict, k is average size of substrings
- space: O(n)
Longest Increasing Subsequence
Problem page:https://leetcode.com/problems/longest-increasing-subsequence
Solution
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# DP solution is easy but slow
# if not nums:
# return 0
# n = len(nums)
# dp = [1] * n
# for i in range(1, n):
# for j in range(i):
# if nums[i] > nums[j]:
# dp[i] = max(dp[i], dp[j] + 1)
# return max(dp)
res = []
def helper(res, n):
left, right = 0, len(res) - 1
while left <= right:
mid = (left + right) // 2
if res[mid] == n:
return mid
elif res[mid] > n:
right = mid - 1
else:
left = mid + 1
return left
for n in nums:
if not res or res[-1] < n:
res.append(n)
else:
index = helper(res,n)
res[index] = n
return len(res)
Complexity
- time: O(n * log n)
- space: O(n)
Climbing Stairs
Problem page:https://leetcode.com/problems/climbing-stairs
Solution
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 3: return n
prev1 = 3
prev2 = 2
cur = 0
for _ in range(3, n):
cur = prev1 + prev2
prev2 = prev1
prev1 = cur
return cur
Complexity
- time: O(n)
- space: O(1)
Multi Ds
Minimum Path Sum
Problem page:https://leetcode.com/problems/minimum-path-sum
Solution
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for i in range(1, m):
grid[i][0] += grid[i-1][0]
for i in range(1, n):
grid[0][i] += grid[0][i-1]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]
Complexity
- time: O(n * m)
- space: O(1)
Longest Palindromic Substring
Problem page:https://leetcode.com/problems/longest-palindromic-substring
Solution
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[-1]*n for _ in range(n)]
def helper(i, j):
if dp[i][j] != -1:
return dp[i][j] == 1
if i >= j:
dp[i][j] = 1
return True
if s[i] == s[j]:
dp[i][j] = helper(i + 1, j - 1)
return dp[i][j] == 1
dp[i][j] = 0
return False
max_len = 0
start = 0
for i in range(n):
for j in range(i, n):
if helper(i,j):
if j - i + 1 > max_len:
max_len = j - i + 1
start = i
return s[start: start + max_len]
Complexity
- time: O(n * n)
- space: O(n * n)
Interleaving String
Problem page:https://leetcode.com/problems/interleaving-string
Solution
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n, l = len(s1), len(s2), len(s3)
if m + n != l:
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i-1] == s3[i-1]
for i in range(1, n + 1):
dp[0][i] = dp[0][i - 1] and s2[i-1] == s3[i-1]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])
return dp[m][n]
Complexity
- time: O(n * m)
- space: O(n * m)
Best Time to Buy and Sell Stock III
Problem page:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii
Solution
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
buy1, buy2 = sys.maxsize, sys.maxsize
sell1, sell2 = 0, 0
for price in prices:
buy1 = min(price, buy1)
sell1 = max(sell1, price - buy1)
buy2 = min(buy2,price - sell1)
sell2 = max(sell2, price - buy2)
return sell2
Complexity
- time: O(n)
- space: O(1)
Edit Distance
Problem page:https://leetcode.com/problems/edit-distance
Solution
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
dp[i][0] = i
for i in range(1, n + 1):
dp[0][i] = i
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j - 1], dp[i-1][j - 1]) + 1
return dp[m][n]
Complexity
- time: O(n * m)
- space: O(n * m)
Best Time to Buy and Sell Stock IV
Problem page:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv
Solution
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if k == 0: return 0
dp=[[1000,0]for _ in range(k + 1)]
for price in prices:
for i in range(1, k + 1):
dp[i][0] = min(dp[i][0],price - dp[i - 1][1])
dp[i][1] = max(dp[i][1], price - dp[i][0])
return dp[k][1]
Complexity
- time: O(n * k)
- space: O(k)
Triangle
Problem page:https://leetcode.com/problems/triangle
Solution
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
for i in range(n - 2, -1, -1):
for j in range(len(triangle[i])):
min_sum = min(triangle[i + 1][j], triangle[i + 1][j + 1])
cur = triangle[i][j]
triangle[i][j] = cur + min_sum
return triangle[0][0]
Complexity
- time: O(n * n)
- space: O(1)
Unique Paths II
Problem page:https://leetcode.com/problems/unique-paths-ii
Solution
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if not obstacleGrid or not obstacleGrid[0] or obstacleGrid[0][0] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
pre = [0] * n
cur = [0] * n
pre[0] = 1
for i in range(m):
cur[0] = 0 if obstacleGrid[i][0] == 1 else pre[0]
for j in range(1,n):
cur[j] = 0 if obstacleGrid[i][j] == 1 else cur[j - 1] + pre[j]
pre[:] = cur
return pre[n - 1]
Complexity
- time: O(m * n)
- space: O(n)
Maximal Square
Problem page:https://leetcode.com/problems/maximal-square
Solution
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
res = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
res = max(res, dp[i][j])
return res * res
Complexity
- time: O(m * n)
- space: O(m * n)