Introduction#
I have attended CodeWeekend and meet many interesting friends there. We have challenged ourselves to
- Solve one LeetCode problem per day.
- Read 50 pages per week of Cracking the Coding Interview and after finishing it, continue with the System Design Interview (volume 1 and 2) books.
So anyways, I am back to leetcode!
2023-09-10#
20. Valid Parentheses#
Python
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c == '(' or c == '{' or c == '[':
stack.append(c)
else:
if len(stack) == 0:
return False
if c == ')':
last = stack.pop()
if last != '(':
return False
if c == '}':
last = stack.pop()
if last != '{':
return False
if c == ']':
last = stack.pop()
if last != '[':
return False
if len(stack) > 0:
return False
return True21. Merge Two Sorted Lists#
Python
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
sentinel = ListNode()
head = sentinel
while list1 and list2:
if list1.val < list2.val:
head.next = list1
list1 = list1.next
else:
head.next = list2
list2 = list2.next
head = head.next
while list1:
head.next = list1
list1 = list1.next
head = head.next
while list2:
head.next = list2
list2 = list2.next
head = head.next
return sentinel.next2023-09-11#
121. Best Time to Buy and Sell Stock#
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# naive solution would require O(n^2)
# how we can do better? Likely a greedy algorithm would help
# if it is a greedy, how can we find the local optimal solution?
# a new optimal would either: a new higher, or a new lower
low = prices[0]
opt = 0
for p in prices:
# potiential new lowest
if p < low:
low = p
else:
# potiential new high
opt = max(p - low, opt)
return opt125. Valid Palindrome#
Python
class Solution:
def alphanumeric(self, c) -> bool:
return (ord(c) <= 57 and ord(c)>=48) or (ord(c) >= 65 and ord(c)<=90) or(ord(c) >= 97 and ord(c) <= 122)
def isPalindrome(self, s: str) -> bool:
s = s.lower()
ptr1=0
ptr2=len(s)-1
while ptr1<ptr2:
if not self.alphanumeric(s[ptr1]):
ptr1 += 1
continue
if not self.alphanumeric(s[ptr2]):
ptr2 -= 1
continue
if s[ptr1] != s[ptr2]:
return False
else:
ptr1 += 1
ptr2 -= 1
return True2023-09-12#
226. Invert Binary Tree#
Python
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
else:
right = self.invertTree(root.left)
left = self.invertTree(root.right)
root.left = left
root.right = right
return root242. Valid Anagram#
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count_table = [0]*26
for s_c in s:
count_table[ord(s_c)-97] += 1
for t_c in t:
if count_table[ord(t_c)-97] == 0:
return False
else:
count_table[ord(t_c)-97] -= 1
return True2023-09-13#
704. Binary Search#
Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
# two pointer binary search is cooler
left = 0
right = len(nums) - 1
while left <= right:
mid = math.floor((left + right) / 2)
if target > nums[mid]:
left = mid + 1
elif target < nums[mid]:
right = mid - 1
else:
return mid
return -1733. Flood Fill#
Python
# DFS implementation
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
visited = [[False for x in range(len(image[0]))] for y in range(len(image))]
stack = [(sr,sc)]
probe = image[sr][sc]
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while len(stack) > 0:
curr = stack.pop()
visited[curr[0]][curr[1]] = True
if image[curr[0]][curr[1]] == probe:
image[curr[0]][curr[1]] = color
# new tasks
for d in dirs:
sr = curr[0] + d[0]
sc = curr[1] + d[1]
if sr>=0 and sr<len(image) and sc>=0 and sc<len(image[0]):
if not visited[sr][sc]:
stack.append((sr,sc))
return image2023-09-14#
235. Lowest Common Ancestor of a Binary Search Tree#
Python
# 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':
# stop when p is on the left subtree, and q is on the right subtree
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
elif p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root110. Balanced Binary Tree#
Python
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
if self.heightBBT(root) != -1:
return True
return False
def heightBBT(self, root):
if root is None:
return 0
left = self.heightBBT(root.left)
right = self.heightBBT(root.right)
if left == -1 or right == -1:
return -1
if abs(left-right) > 1:
return -1
return max(left, right) + 12023-09-15#
141. Linked List Cycle#
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast = head
slow = head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False232. Implement Queue using Stacks#
Python
class MyQueue:
def __init__(self):
self.pop_stack = []
self.push_stack = []
def push(self, x: int) -> None:
self.push_stack.append(x)
def pop(self) -> int:
if len(self.pop_stack) > 0:
return self.pop_stack.pop()
while len(self.push_stack) > 0:
elem = self.push_stack.pop()
self.pop_stack.append(elem)
return self.pop_stack.pop()
def peek(self) -> int:
if len(self.pop_stack) > 0:
return self.pop_stack[-1]
else:
return self.push_stack[0]
def empty(self) -> bool:
return len(self.pop_stack) + len(self.push_stack) == 0
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()2023-09-18#
278. First Bad Version#
Python
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
left = 1
right = n
while left <= right:
mid = math.floor((left + right) / 2)
if isBadVersion(mid) == True:
if mid - 1 >= 1:
if isBadVersion(mid - 1) == False:
return mid
else:
right = mid - 1
else:
return mid
if mid - 1 >= 1 and isBadVersion(mid-1) == False:
return mid
else:
left = mid + 1
return -1383. Ransom Note#
Python
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
table = dict()
for m in magazine:
if m in table:
table[m] += 1
else:
table[m] = 1
for r in ransomNote:
if r in table:
if table[r] > 0:
table[r] -= 1
else:
return False
else:
return False
return True2023-09-19#
70. Climbing Stairs#
Python
class Solution:
def climbStairs(self, n: int) -> int:
db = [0 for i in range(n+1)]
db[-1] = 1
db[-2] = 1
for i in range(n-2, -1, -1):
db[i] = db[i+1]+db[i+2]
return db[0]409. Longest Palindrome#
Python
class Solution:
def longestPalindrome(self, s: str) -> int:
table = {}
for i in s:
if i in table:
table[i] += 1
else:
table[i] = 1
length = 00
for (_, v) in table.items():
length += math.floor(v/2) * 2
if length % 2 == 0 and v % 2 == 1:
length += 1
return lengthReverse Linked List#
Python
# 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]:
sentinel = ListNode()
curr = head
next = head
while curr:
next = curr.next
curr.next = sentinel.next
sentinel.next = curr
curr = next
return sentinel.next 2023-09-21#
169. Majority Element#
classical divide and conquer problem
Complexity:
O(nlgn)
Python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
left = self.majorityElement(nums[math.floor(len(nums)/2):])
right = self.majorityElement(nums[:math.floor(len(nums)/2)])
if nums[:math.floor(len(nums)/2)].count(left) > nums[math.floor(len(nums)/2):].count(right):
return left
else:
return rightLinear solution will be
Think of a situation, If an elephant have a fight with any other elephant, both will die. King A has 5 elephants, and King B has 4 elephants. If they're in a war, King A will win. Similarly, In this question it was given that a number is in majority, So if we have fight with numbers majority will always win.
Let me explain it very briefly In a war, if any King have more than the total count of elephant , so even if rest of the Kings will unite >and fight they can't win because at the end of the battle, there will be atleast one elephant left that will >belong to the King that has the majority. But we don't know who has the majority, and that is what we need to find.
How to fight At any iteration if any King has maximum alive elephants will get the Throne and the rest of the Kings will unite to de-throne him. So at the end of this continous war (list), the King that has throne will be the winner.
reference:✅ Python easy solution O(n) | O(1) | explained
Python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
curr, count = nums[0], 1
for i in range(1, len(nums)):
if count:
# fight elephant
if nums[i] != curr:
count -= 1
else:
count += 1
else:
curr = nums[i]
count = 1
return curr2023-09-22#
67 Add Binary#
Python
class Solution:
def addBinary(self, a: str, b: str) -> str:
if len(a) < len(b):
temp = a[::]
a = b
b = temp
a = a[::-1]
b = b[::-1]
res = ""
carry = False
for i in range(len(b)):
if carry:
if a[i] == '1':
x = '0'
else:
x = '1'
carry = False
else:
x = a[i]
if x == '1' and b[i] == '1':
res += '0'
carry = True
elif x == '1' and b[i] == '0':
res += '1'
elif x == '0' and b[i] == '1':
res += '1'
else:
res += '0'
for i in range(len(b), len(a)):
if carry:
if a[i] == '1':
res += '0'
else:
res += '1'
carry = False
else:
res += a[i]
if carry:
res += '1'
return res[::-1] cleaner solution
Python
class Solution:
def addBinary(self, a: str, b: str) -> str:
s = []
carry = 0
i = len(a) - 1
j = len(b) - 1
while i >= 0 or j >= 0 or carry:
if i >= 0:
carry += int(a[i])
i -= 1
if j >= 0:
carry += int(b[j])
j -= 1
s.append(str(carry % 2))
carry //= 2
return ''.join(reversed(s))2023-09-24#
543. Diameter of Binary Tree#
Python
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
return self.daemon(root)[1]
def daemon(self, root):
if root is None or root.left is None and root.right is None:
return [0, 0]
left = self.daemon(root.left)
right = self.daemon(root.right)
noThroughRoot = max(left[0], right[0]) + 1
goThroughRoot = left[0]+right[0]
if root.left:
goThroughRoot += 1
if root.right:
goThroughRoot += 1
longest = max([noThroughRoot, goThroughRoot, left[1], right[1]])
return [noThroughRoot, longest]
965. Univalued Binary Tree#
Python
# 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 isUnivalTree(self, root: Optional[TreeNode]) -> bool:
return self.daemon(root, root.val)
def daemon(self, root, val):
if root is None:
return True
if root.val == val:
return self.daemon(root.left, val) and self.daemon(root.right, val)
else:
return False494. Target Sum#
Python
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp = [[0]*(2001) for _ in range(len(nums))]
dp[0][1000+nums[0]] += 1
dp[0][1000-nums[0]] += 1
# state transition function
for i in range(1, len(nums)):
for j in range(2001):
t1 = dp[i-1][j-nums[i]] if j-nums[i] >= 0 else 0
t2 = dp[i-1][j+nums[i]] if j+nums[i] <= 2000 else 0
dp[i][j] = t1+t2
# result
return dp[-1][1000+target]
876. Middle of the Linked List#
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow2023-09-25#
104. Maximum Depth of Binary Tree#
Python
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return max(left, right) + 1217. Contains Duplicate#
Python
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
table = set()
for i in nums:
if i in table:
return True
else:
table.add(i)
return False53. Maximum Subarray#
Divide and Conquer
Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if not nums:
return 0
mid = len(nums)//2
left = self.maxSubArray(nums[:mid])
right = self.maxSubArray(nums[mid:])
continousLeft = float('-inf')
continousRight = float('-inf')
acc = 0
for i in range(mid-1, -1, -1):
acc += nums[i]
continousLeft = max(continousLeft, acc)
acc = 0
for i in range(mid, len(nums), 1):
acc += nums[i]
continousRight = max(continousRight, acc)
return max([left,right, continousLeft+continousRight])DP
Python
def maxSubArray(self, nums):
dp = [0]*len(nums)
for i,num in enumerate(nums):
dp[i] = max(dp[i-1] + num, num)
return max(dp)2023-09-26#
57. Insert Interval#
Python
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
left = [i for i in intervals if i[1] < newInterval[0]]
right = [i for i in intervals if i[0] > newInterval[1]]
if left + right != intervals:
newInterval[0] = min(newInterval[0], intervals[len(left)][0])
newInterval[1] = max(newInterval[1], intervals[-len(right)-1][1])
return left + [newInterval] + right2023-09-27#
542. 01 Matrix#
- BFS uses queue
- DFS uses stack
Python
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
Row, Col = len(mat), len(mat[0])
queue = []
directions = [[0, +1], [0, -1], [1, 0], [-1, 0]]
for i in range(Row):
for j in range(Col):
if mat[i][j] == 0:
queue.append((i, j))
else:
mat[i][j] = "*"
for r, c in queue:
for dr, dc in directions:
row = r + dr
col = c + dc
if 0 <= row < Row and 0 <= col < Col and mat[row][col] == "*":
mat[row][col] = mat[r][c] + 1
queue.append((row, col))
return mat2023-09-28#
973. K Closest Points to Origin#
sort solution, O(nlogn)
Python
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
points.sort(key = lambda P:P[0]**2+P[1]**2)
return points[:k]a different solution could be using heap, which results in O(nlogk) time complexity
Python
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
distance = []
for i in points:
heapq.heappush(distance,(i[0]**2+i[1]**2,i))
K_points = []
for i in range(K):
K_points.append(heapq.heappop(distance)[1])
return K_points2023-09-29#
3. Longest Substring Without Repeating Characters#
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
sub = set()
begin = 0
maxLength = 0
for i in s:
if i not in sub:
sub.add(i)
maxLength = max(maxLength, len(sub))
else:
while i in sub:
sub.remove(s[begin])
begin += 1
sub.add(i)
return maxLength