September 2023 Daily Leetcode: Grind 75 in Python
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
1class Solution: 2 def isValid(self, s: str) -> bool: 3 stack = [] 4 for c in s: 5 if c == '(' or c == '{' or c == '[': 6 stack.append(c) 7 else: 8 if len(stack) == 0: 9 return False 10 if c == ')': 11 last = stack.pop() 12 if last != '(': 13 return False 14 if c == '}': 15 last = stack.pop() 16 if last != '{': 17 return False 18 if c == ']': 19 last = stack.pop() 20 if last != '[': 21 return False 22 if len(stack) > 0: 23 return False 24 return True
21. Merge Two Sorted Lists
1class Solution: 2 def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: 3 4 sentinel = ListNode() 5 head = sentinel 6 while list1 and list2: 7 if list1.val < list2.val: 8 head.next = list1 9 list1 = list1.next 10 else: 11 head.next = list2 12 list2 = list2.next 13 head = head.next 14 15 while list1: 16 head.next = list1 17 list1 = list1.next 18 head = head.next 19 20 while list2: 21 head.next = list2 22 list2 = list2.next 23 head = head.next 24 25 return sentinel.next
2023-09-11
121. Best Time to Buy and Sell Stock
1class Solution: 2 def maxProfit(self, prices: List[int]) -> int: 3 # naive solution would require O(n^2) 4 # how we can do better? Likely a greedy algorithm would help 5 # if it is a greedy, how can we find the local optimal solution? 6 # a new optimal would either: a new higher, or a new lower 7 low = prices[0] 8 opt = 0 9 10 for p in prices: 11 # potiential new lowest 12 if p < low: 13 low = p 14 else: 15 # potiential new high 16 opt = max(p - low, opt) 17 18 return opt
125. Valid Palindrome
1class Solution: 2 def alphanumeric(self, c) -> bool: 3 return (ord(c) <= 57 and ord(c)>=48) or (ord(c) >= 65 and ord(c)<=90) or(ord(c) >= 97 and ord(c) <= 122) 4 5 def isPalindrome(self, s: str) -> bool: 6 s = s.lower() 7 ptr1=0 8 ptr2=len(s)-1 9 10 while ptr1<ptr2: 11 if not self.alphanumeric(s[ptr1]): 12 ptr1 += 1 13 continue 14 if not self.alphanumeric(s[ptr2]): 15 ptr2 -= 1 16 continue 17 if s[ptr1] != s[ptr2]: 18 return False 19 else: 20 ptr1 += 1 21 ptr2 -= 1 22 23 return True
2023-09-12
226. Invert Binary Tree
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: 9 if not root: 10 return root 11 else: 12 right = self.invertTree(root.left) 13 left = self.invertTree(root.right) 14 root.left = left 15 root.right = right 16 return root
242. Valid Anagram
1class Solution: 2 def isAnagram(self, s: str, t: str) -> bool: 3 if len(s) != len(t): 4 return False 5 count_table = [0]*26 6 for s_c in s: 7 count_table[ord(s_c)-97] += 1 8 9 for t_c in t: 10 if count_table[ord(t_c)-97] == 0: 11 return False 12 else: 13 count_table[ord(t_c)-97] -= 1 14 15 return True
2023-09-13
704. Binary Search
1class Solution: 2 def search(self, nums: List[int], target: int) -> int: 3 # two pointer binary search is cooler 4 left = 0 5 right = len(nums) - 1 6 while left <= right: 7 mid = math.floor((left + right) / 2) 8 if target > nums[mid]: 9 left = mid + 1 10 elif target < nums[mid]: 11 right = mid - 1 12 else: 13 return mid 14 15 return -1
733. Flood Fill
1# DFS implementation 2class Solution: 3 def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]: 4 visited = [[False for x in range(len(image[0]))] for y in range(len(image))] 5 stack = [(sr,sc)] 6 probe = image[sr][sc] 7 dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] 8 while len(stack) > 0: 9 curr = stack.pop() 10 visited[curr[0]][curr[1]] = True 11 if image[curr[0]][curr[1]] == probe: 12 image[curr[0]][curr[1]] = color 13 # new tasks 14 for d in dirs: 15 sr = curr[0] + d[0] 16 sc = curr[1] + d[1] 17 if sr>=0 and sr<len(image) and sc>=0 and sc<len(image[0]): 18 if not visited[sr][sc]: 19 stack.append((sr,sc)) 20 return image
2023-09-14
235. Lowest Common Ancestor of a Binary Search Tree
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, x): 4# self.val = x 5# self.left = None 6# self.right = None 7 8class Solution: 9 def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 10 # stop when p is on the left subtree, and q is on the right subtree 11 if p.val < root.val and q.val < root.val: 12 return self.lowestCommonAncestor(root.left, p, q) 13 elif p.val > root.val and q.val > root.val: 14 return self.lowestCommonAncestor(root.right, p, q) 15 else: 16 return root
110. Balanced Binary Tree
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def isBalanced(self, root: Optional[TreeNode]) -> bool: 9 if self.heightBBT(root) != -1: 10 return True 11 return False 12 13 def heightBBT(self, root): 14 if root is None: 15 return 0 16 17 left = self.heightBBT(root.left) 18 right = self.heightBBT(root.right) 19 20 if left == -1 or right == -1: 21 return -1 22 23 if abs(left-right) > 1: 24 return -1 25 26 return max(left, right) + 1
2023-09-15
141. Linked List Cycle
1# Definition for singly-linked list. 2# class ListNode: 3# def __init__(self, x): 4# self.val = x 5# self.next = None 6 7class Solution: 8 def hasCycle(self, head: Optional[ListNode]) -> bool: 9 fast = head 10 slow = head 11 while fast is not None and fast.next is not None: 12 fast = fast.next.next 13 slow = slow.next 14 15 if fast == slow: 16 return True 17 return False
232. Implement Queue using Stacks
1class MyQueue: 2 3 def __init__(self): 4 self.pop_stack = [] 5 self.push_stack = [] 6 7 8 def push(self, x: int) -> None: 9 self.push_stack.append(x) 10 11 def pop(self) -> int: 12 if len(self.pop_stack) > 0: 13 return self.pop_stack.pop() 14 while len(self.push_stack) > 0: 15 elem = self.push_stack.pop() 16 self.pop_stack.append(elem) 17 return self.pop_stack.pop() 18 19 def peek(self) -> int: 20 if len(self.pop_stack) > 0: 21 return self.pop_stack[-1] 22 else: 23 return self.push_stack[0] 24 25 def empty(self) -> bool: 26 return len(self.pop_stack) + len(self.push_stack) == 0 27 28 29 30# Your MyQueue object will be instantiated and called as such: 31# obj = MyQueue() 32# obj.push(x) 33# param_2 = obj.pop() 34# param_3 = obj.peek() 35# param_4 = obj.empty()
2023-09-18
278. First Bad Version
1# The isBadVersion API is already defined for you. 2# def isBadVersion(version: int) -> bool: 3 4class Solution: 5 def firstBadVersion(self, n: int) -> int: 6 left = 1 7 right = n 8 9 while left <= right: 10 mid = math.floor((left + right) / 2) 11 if isBadVersion(mid) == True: 12 if mid - 1 >= 1: 13 if isBadVersion(mid - 1) == False: 14 return mid 15 else: 16 right = mid - 1 17 else: 18 return mid 19 if mid - 1 >= 1 and isBadVersion(mid-1) == False: 20 return mid 21 else: 22 left = mid + 1 23 24 return -1
383. Ransom Note
1class Solution: 2 def canConstruct(self, ransomNote: str, magazine: str) -> bool: 3 table = dict() 4 for m in magazine: 5 if m in table: 6 table[m] += 1 7 else: 8 table[m] = 1 9 10 for r in ransomNote: 11 if r in table: 12 if table[r] > 0: 13 table[r] -= 1 14 else: 15 return False 16 else: 17 return False 18 19 return True
2023-09-19
70. Climbing Stairs
1class Solution: 2 def climbStairs(self, n: int) -> int: 3 db = [0 for i in range(n+1)] 4 db[-1] = 1 5 db[-2] = 1 6 7 for i in range(n-2, -1, -1): 8 db[i] = db[i+1]+db[i+2] 9 return db[0]
409. Longest Palindrome
1class Solution: 2 def longestPalindrome(self, s: str) -> int: 3 table = {} 4 for i in s: 5 if i in table: 6 table[i] += 1 7 else: 8 table[i] = 1 9 length = 00 10 for (_, v) in table.items(): 11 length += math.floor(v/2) * 2 12 if length % 2 == 0 and v % 2 == 1: 13 length += 1 14 return length
Reverse Linked List
1# Definition for singly-linked list. 2# class ListNode: 3# def __init__(self, val=0, next=None): 4# self.val = val 5# self.next = next 6class Solution: 7 def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: 8 sentinel = ListNode() 9 curr = head 10 next = head 11 while curr: 12 next = curr.next 13 curr.next = sentinel.next 14 sentinel.next = curr 15 curr = next 16 return sentinel.next
2023-09-21
169. Majority Element
classical divide and conquer problem
Complexity:
O(nlgn)
1class Solution: 2 def majorityElement(self, nums: List[int]) -> int: 3 if len(nums) == 1: 4 return nums[0] 5 left = self.majorityElement(nums[math.floor(len(nums)/2):]) 6 right = self.majorityElement(nums[:math.floor(len(nums)/2)]) 7 8 9 if nums[:math.floor(len(nums)/2)].count(left) > nums[math.floor(len(nums)/2):].count(right): 10 return left 11 else: 12 return right
Linear 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
1class Solution: 2 def majorityElement(self, nums: List[int]) -> int: 3 curr, count = nums[0], 1 4 for i in range(1, len(nums)): 5 if count: 6 # fight elephant 7 if nums[i] != curr: 8 count -= 1 9 else: 10 count += 1 11 else: 12 curr = nums[i] 13 count = 1 14 return curr
2023-09-22
67 Add Binary
1class Solution: 2 def addBinary(self, a: str, b: str) -> str: 3 if len(a) < len(b): 4 temp = a[::] 5 a = b 6 b = temp 7 a = a[::-1] 8 b = b[::-1] 9 10 res = "" 11 carry = False 12 for i in range(len(b)): 13 if carry: 14 if a[i] == '1': 15 x = '0' 16 else: 17 x = '1' 18 carry = False 19 else: 20 x = a[i] 21 22 if x == '1' and b[i] == '1': 23 res += '0' 24 carry = True 25 elif x == '1' and b[i] == '0': 26 res += '1' 27 elif x == '0' and b[i] == '1': 28 res += '1' 29 else: 30 res += '0' 31 32 for i in range(len(b), len(a)): 33 34 if carry: 35 if a[i] == '1': 36 res += '0' 37 else: 38 res += '1' 39 carry = False 40 else: 41 res += a[i] 42 if carry: 43 res += '1' 44 return res[::-1]
cleaner solution
1class Solution: 2 def addBinary(self, a: str, b: str) -> str: 3 s = [] 4 carry = 0 5 i = len(a) - 1 6 j = len(b) - 1 7 8 while i >= 0 or j >= 0 or carry: 9 if i >= 0: 10 carry += int(a[i]) 11 i -= 1 12 if j >= 0: 13 carry += int(b[j]) 14 j -= 1 15 s.append(str(carry % 2)) 16 carry //= 2 17 18 return ''.join(reversed(s))
2023-09-24
543. Diameter of Binary Tree
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: 9 return self.daemon(root)[1] 10 11 def daemon(self, root): 12 if root is None or root.left is None and root.right is None: 13 return [0, 0] 14 15 left = self.daemon(root.left) 16 right = self.daemon(root.right) 17 noThroughRoot = max(left[0], right[0]) + 1 18 goThroughRoot = left[0]+right[0] 19 if root.left: 20 goThroughRoot += 1 21 if root.right: 22 goThroughRoot += 1 23 longest = max([noThroughRoot, goThroughRoot, left[1], right[1]]) 24 return [noThroughRoot, longest] 25
965. Univalued Binary Tree
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def isUnivalTree(self, root: Optional[TreeNode]) -> bool: 9 return self.daemon(root, root.val) 10 11 def daemon(self, root, val): 12 if root is None: 13 return True 14 if root.val == val: 15 return self.daemon(root.left, val) and self.daemon(root.right, val) 16 else: 17 return False
494. Target Sum
1class Solution: 2 def findTargetSumWays(self, nums: List[int], target: int) -> int: 3 dp = [[0]*(2001) for _ in range(len(nums))] 4 dp[0][1000+nums[0]] += 1 5 dp[0][1000-nums[0]] += 1 6 7 # state transition function 8 for i in range(1, len(nums)): 9 for j in range(2001): 10 t1 = dp[i-1][j-nums[i]] if j-nums[i] >= 0 else 0 11 t2 = dp[i-1][j+nums[i]] if j+nums[i] <= 2000 else 0 12 dp[i][j] = t1+t2 13 14 # result 15 return dp[-1][1000+target] 16
876. Middle of the Linked List
1# Definition for singly-linked list. 2# class ListNode: 3# def __init__(self, val=0, next=None): 4# self.val = val 5# self.next = next 6class Solution: 7 def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: 8 slow = head 9 fast = head 10 while fast and fast.next: 11 slow = slow.next 12 fast = fast.next.next 13 return slow
2023-09-25
104. Maximum Depth of Binary Tree
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def maxDepth(self, root: Optional[TreeNode]) -> int: 9 if root is None: 10 return 0 11 12 left = self.maxDepth(root.left) 13 right = self.maxDepth(root.right) 14 15 return max(left, right) + 1
217. Contains Duplicate
1class Solution: 2 def containsDuplicate(self, nums: List[int]) -> bool: 3 table = set() 4 for i in nums: 5 if i in table: 6 return True 7 else: 8 table.add(i) 9 return False
53. Maximum Subarray
Divide and Conquer
1class Solution: 2 def maxSubArray(self, nums: List[int]) -> int: 3 if len(nums) == 1: 4 return nums[0] 5 if not nums: 6 return 0 7 mid = len(nums)//2 8 left = self.maxSubArray(nums[:mid]) 9 right = self.maxSubArray(nums[mid:]) 10 11 continousLeft = float('-inf') 12 continousRight = float('-inf') 13 acc = 0 14 for i in range(mid-1, -1, -1): 15 acc += nums[i] 16 continousLeft = max(continousLeft, acc) 17 acc = 0 18 for i in range(mid, len(nums), 1): 19 acc += nums[i] 20 continousRight = max(continousRight, acc) 21 22 return max([left,right, continousLeft+continousRight])
DP
1def maxSubArray(self, nums): 2 dp = [0]*len(nums) 3 for i,num in enumerate(nums): 4 dp[i] = max(dp[i-1] + num, num) 5 return max(dp)
2023-09-26
57. Insert Interval
1class Solution: 2 def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: 3 left = [i for i in intervals if i[1] < newInterval[0]] 4 right = [i for i in intervals if i[0] > newInterval[1]] 5 6 7 if left + right != intervals: 8 newInterval[0] = min(newInterval[0], intervals[len(left)][0]) 9 newInterval[1] = max(newInterval[1], intervals[-len(right)-1][1]) 10 11 return left + [newInterval] + right
2023-09-27
542. 01 Matrix
- BFS uses queue
- DFS uses stack
1class Solution: 2 def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: 3 Row, Col = len(mat), len(mat[0]) 4 queue = [] 5 directions = [[0, +1], [0, -1], [1, 0], [-1, 0]] 6 7 for i in range(Row): 8 for j in range(Col): 9 if mat[i][j] == 0: 10 queue.append((i, j)) 11 else: 12 mat[i][j] = "*" 13 14 for r, c in queue: 15 for dr, dc in directions: 16 row = r + dr 17 col = c + dc 18 if 0 <= row < Row and 0 <= col < Col and mat[row][col] == "*": 19 mat[row][col] = mat[r][c] + 1 20 queue.append((row, col)) 21 return mat
2023-09-28
973. K Closest Points to Origin
sort solution, O(nlogn)
1class Solution: 2 def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: 3 points.sort(key = lambda P:P[0]**2+P[1]**2) 4 return points[:k]
a different solution could be using heap, which results in O(nlogk) time complexity
1import heapq 2class Solution: 3 def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]: 4 distance = [] 5 for i in points: 6 heapq.heappush(distance,(i[0]**2+i[1]**2,i)) 7 K_points = [] 8 for i in range(K): 9 K_points.append(heapq.heappop(distance)[1]) 10 return K_points
2023-09-29
3. Longest Substring Without Repeating Characters
1class Solution: 2 def lengthOfLongestSubstring(self, s: str) -> int: 3 sub = set() 4 begin = 0 5 maxLength = 0 6 for i in s: 7 if i not in sub: 8 sub.add(i) 9 maxLength = max(maxLength, len(sub)) 10 else: 11 while i in sub: 12 sub.remove(s[begin]) 13 begin += 1 14 sub.add(i) 15 return maxLength