LeetCode703
https://leetcode.com/problems/kth-largest-element-in-a-stream/description/
https://www.youtube.com/watch?v=hOjcdrqMoQ8
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.minHeap, self.k = nums, k
heapq.heapify(self.minHeap)
while len(self.minHeap) > k:
heapq.heappop(self.minHeap)
def add(self, val: int) -> int:
heapq.heappush(self.minHeap, val)
if len(self.minHeap) > self.k:
heapq.heappop(self.minHeap)
return self.minHeap[0]
---
LeetCode21
https://leetcode.com/problems/merge-two-sorted-lists/description/
https://www.youtube.com/watch?v=XIdigk956u0
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Iterative Solution
class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
dummy = node = ListNode()
while list1 and list2:
if list1.val < list2.val:
node.next = list1
list1 = list1.next
else:
node.next = list2
list2 = list2.next
node = node.next
node.next = list1 or list2
return dummy.next
# Recursive Solution
# class Solution:
# def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# if not list1:
# return list2
# if not list2:
# return list1
# lil, big = (list1, list2) if list1.val < list2.val else (list2, list1)
# lil.next = self.mergeTwoLists(lil.next, big)
# return lil
---
LeetCode746
https://leetcode.com/problems/min-cost-climbing-stairs/description/
https://www.youtube.com/watch?v=ktmzAZWkEZ0
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
for i in range(len(cost) - 3, -1, -1):
cost[i] += min(cost[i + 1], cost[i + 2])
return min(cost[0], cost[1])
---
LeetCode121
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
https://www.youtube.com/watch?v=1pkOgXD63yU
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
lowest = prices[0]
for price in prices:
if price < lowest:
lowest = price
res = max(res, price - lowest)
return res
---
LeetCode1046
https://leetcode.com/problems/last-stone-weight/description/
https://www.youtube.com/watch?v=B-QCq79-Vfw
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-s for s in stones]
heapq.heapify(stones)
while len(stones) > 1:
first = heapq.heappop(stones)
second = heapq.heappop(stones)
if second > first:
heapq.heappush(stones, first - second)
stones.append(0)
return abs(stones[0])
---
LeetCode66
https://leetcode.com/problems/plus-one/description/
https://www.youtube.com/watch?v=jIaA8boiG1s
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
one = 1
i = 0
digits = digits[::-1]
while one:
if i < len(digits):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
one = 0
else:
digits.append(one)
one = 0
i += 1
return digits[::-1]
---
LeetCode70
https://leetcode.com/problems/climbing-stairs/description/
https://www.youtube.com/watch?v=Y0lT9Fck7qI
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 3:
return n
n1, n2 = 2, 3
for i in range(4, n + 1):
temp = n1 + n2
n1 = n2
n2 = temp
return n2
---
LeetCode202
https://leetcode.com/problems/happy-number/description/
https://www.youtube.com/watch?v=ljz85bxOYJ0
class Solution:
def isHappy(self, n: int) -> bool:
slow, fast = n, self.sumSquareDigits(n)
while slow != fast:
fast = self.sumSquareDigits(fast)
fast = self.sumSquareDigits(fast)
slow = self.sumSquareDigits(slow)
return True if fast == 1 else False
def sumSquareDigits(self, n):
output = 0
while n:
output += (n % 10) ** 2
n = n // 10
return output
---
LeetCode191
https://leetcode.com/problems/number-of-1-bits/description/
https://www.youtube.com/watch?v=5Km3utixwZs
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
n &= n - 1
res += 1
return res
---
LeetCode190
https://leetcode.com/problems/reverse-bits/description/
https://www.youtube.com/watch?v=UcoN6UjAI64
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
bit = (n >> i) & 1
res += (bit << (31 - i))
return res
---
LeetCode242
https://leetcode.com/problems/valid-anagram/description/
https://www.youtube.com/watch?v=9UtInBqnCgA
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
countS, countT = {}, {}
for i in range(len(s)):
countS[s[i]] = 1 + countS.get(s[i], 0)
countT[t[i]] = 1 + countT.get(t[i], 0)
return countS == countT
---
LeetCode57
https://leetcode.com/problems/subtree-of-another-tree/description/
https://www.youtube.com/watch?v=E36O5SWp-LE
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not subRoot:
return True
if not root:
return False
if self.sameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def sameTree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root and not subRoot:
return True
if root and subRoot and root.val == subRoot.val:
return self.sameTree(root.left, subRoot.left) and self.sameTree(root.right, subRoot.right)
return False
---
LeetCode100
https://leetcode.com/problems/same-tree/description/
https://www.youtube.com/watch?v=vRbbcKXCxOw
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if p and q and p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False
---
LeetCode543
https://leetcode.com/problems/diameter-of-binary-tree/description/
https://www.youtube.com/watch?v=K81C31ytOZE
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = 0
def dfs(root):
nonlocal res
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
res = max(res, left + right)
return 1 + max(left, right)
dfs(root)
return res
---
LeetCode104
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
https://www.youtube.com/watch?v=hTM3phVI6YQ
# 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
# RECURSIVE DFS
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
# ITERATIVE DFS
# class Solution:
# def maxDepth(self, root: Optional[TreeNode]) -> int:
# stack = [[root, 1]]
# res = 0
# while stack:
# node, depth = stack.pop()
# if node:
# res = max(res, depth)
# stack.append([node.left, depth + 1])
# stack.append([node.right, depth + 1])
# return res
# BFS
# class Solution:
# def maxDepth(self, root: Optional[TreeNode]) -> int:
# q = deque()
# if root:
# q.append(root)
# level = 0
# while q:
# for i in range(len(q)):
# node = q.popleft()
# if node.left:
# q.append(node.left)
# if node.right:
# q.append(node.right)
# level += 1
# return level
---
LeetCode226
https://leetcode.com/problems/invert-binary-tree/description/
https://www.youtube.com/watch?v=OnSn2XEQ4MY
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
---
LeetCode206
https://leetcode.com/problems/reverse-linked-list/description/
https://www.youtube.com/watch?v=G0_I-ZF0S38
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev, curr = None, head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
---
LeetCode141
https://leetcode.com/problems/linked-list-cycle/description/
https://www.youtube.com/watch?v=gBTe7lFR3vc
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class 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 slow == fast:
return True
return False
---
LeetCode338
https://leetcode.com/problems/counting-bits/description/
https://www.youtube.com/watch?v=RyBM56RIWrM
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
offset = 1
for i in range(1, n + 1):
if offset * 2 == i:
offset = i
dp[i] = 1 + dp[i - offset]
return dp
---
LeetCode217
https://leetcode.com/problems/contains-duplicate/description/
https://www.youtube.com/watch?v=3OamzN90kPg
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
hashset = set()
for n in nums:
if n in hashset:
return True
hashset.add(n)
return False
---
LeetCode252
https://leetcode.com/problems/meeting-rooms/description/
https://www.youtube.com/watch?v=PaJxqZVPhbg
"""
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
intervals.sort(key=lambda i: i.start)
for i in range(1, len(intervals)):
i1 = intervals[i - 1]
i2 = intervals[i]
if i1.end > i2.start:
return False
return True
---
LeetCode704
https://leetcode.com/problems/binary-search/description/
https://www.youtube.com/watch?v=s4DPM8ct1pI
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = l + ((r - l) // 2) # (l + r) // 2 can lead to overflow
if nums[m] > target:
r = m - 1
elif nums[m] < target:
l = m + 1
else:
return m
return -1
---
LeetCode1
https://leetcode.com/problems/two-sum/description/
https://www.youtube.com/watch?v=KLlXCFG5TnA
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {} # val -> index
for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return [prevMap[diff], i]
prevMap[n] = i
---
LeetCode268
https://leetcode.com/problems/missing-number/description/
https://www.youtube.com/watch?v=WnPLSRLSANE
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i in range(len(nums)):
res += i - nums[i]
return res
---
LeetCode20
https://leetcode.com/problems/valid-parentheses/description/
https://www.youtube.com/watch?v=WTzjTskDFMg
class Solution:
def isValid(self, s: str) -> bool:
Map = {")": "(", "]": "[", "}": "{"}
stack = []
for c in s:
if c not in Map:
stack.append(c)
continue
if not stack or stack[-1] != Map[c]:
return False
stack.pop()
return not stack
---
LeetCode136
https://leetcode.com/problems/single-number/description/
https://www.youtube.com/watch?v=qMPX1AOa83k
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for n in nums:
res = n ^ res
return res
---
LeetCode110
https://leetcode.com/problems/balanced-binary-tree/description/
https://www.youtube.com/watch?v=QfJsau0ItOY
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
if not root:
return [True, 0]
left, right = dfs(root.left), dfs(root.right)
balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
return [balanced, 1 + max(left[1], right[1])]
return dfs(root)[0]
---
LeetCode125
https://leetcode.com/problems/valid-palindrome/description/
https://www.youtube.com/watch?v=jJXJ16kPFWg
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not self.alphaNum(s[l]):
l += 1
while r > l and not self.alphaNum(s[r]):
r -= 1
if s[l].lower() != s[r].lower():
return False
l, r = l + 1, r - 1
return True
def alphaNum(self, c):
return (ord('A') <= ord(c) <= ord('Z') or
ord('a') <= ord(c) <= ord('z') or
ord('0') <= ord(c) <= ord('9'))
---
LeetCode138
https://leetcode.com/problems/copy-list-with-random-pointer/description/
https://www.youtube.com/watch?v=5Y2EiZST97Y
"""
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
oldToCopy = {None: None}
cur = head
while cur:
copy = Node(cur.val)
oldToCopy[cur] = copy
cur = cur.next
cur = head
while cur:
copy = oldToCopy[cur]
copy.next = oldToCopy[cur.next]
copy.random = oldToCopy[cur.random]
cur = cur.next
return oldToCopy[head]