no message

Chris Wu · Chris Wu · commit cda3f4178d8b · 2020-07-31T10:09:37.000+08:00
diff --git a/problems/capacity-to-ship-packages-within-d-days.py b/problems/capacity-to-ship-packages-within-d-days.py
@@ -18,15 +18,17 @@ def shipWithinDays(self, weights, D):
             if daily_weight: d += 1
 
             if d>D:
-                #K cannot be the answer.
-                #next round we don't need to put K in l~r.
+                #c cannot be the answer.
+                #next round we don't need to put c in l~r.
                 l = c+1
             else:
-                #K might ot might not be the answer.
-                #next round we still need to put K in l~r.
+                #c might ot might not be the answer.
+                #next round we still need to put c in l~r.
                 r = c
         return l
 
+
+
 """
 This is a binary search problem.
 If you do not understand binary search yet, please study it first.
@@ -43,6 +45,12 @@ def shipWithinDays(self, weights, D):
 [2]
 So the boundary of our answer, `l` and `r`, will collides together (`l==r`) and jump out of the loop.
 
-Time complexity: `O(NlogN)`. There will be `O(LogN)` iteration. For every iteration we need O(N) to calculate the `t`. `N` is the length of `piles`.
-Space complexity is O(N). For calculating `t`.
+Time complexity: `O(NlogW)`.
+`N` is the number of `weights`.
+`W` is the max weight.
+There will be `O(LogW)` iteration. For every iteration we need O(N) to calculate the `d`. 
+Space complexity is O(1).
+
+Also take a look at problem, 875, very similar.
+https://leetcode.com/problems/koko-eating-bananas/discuss/750699/
 """
diff --git a/problems/insert-into-a-binary-search-tree.py b/problems/insert-into-a-binary-search-tree.py
@@ -0,0 +1,26 @@
+class Solution(object):
+    def insertIntoBST(self, root, val):
+        if not root: return TreeNode(val)
+        
+        node = root
+        while node:
+            if val<node.val:
+                if not node.left:
+                    node.left = TreeNode(val)
+                    return root
+                else:
+                    node = node.left
+            else:
+                if not node.right:
+                    node.right = TreeNode(val)
+                    return root
+                else:
+                    node = node.right
+        
+        return None
+
+
+"""
+Time complexity: O(LogN)
+Space complexity: O(1)
+"""
diff --git a/problems/kth-smallest-element-in-a-bst.py b/problems/kth-smallest-element-in-a-bst.py
@@ -0,0 +1,32 @@
+class Solution(object):
+    def kthSmallest(self, root, k):
+        count = 0
+        stack = []
+        node = root
+        
+        while node or stack:
+            while node:
+                stack.append(node)
+                node = node.left
+                
+            node = stack.pop()
+            count += 1
+            
+            if count==k: return node.val
+            
+            node = node.right
+            
+        return 0
+
+"""
+Time complexity: O(N). Because we use inorder traversal.
+Space complexity: O(N). For stack may contains all the nodes.
+"""
+
+"""
+For follow up question.
+We might need to keep a sorted list of node.
+Every time we inset and delete. We need to update the list. Taking up O(N) of time.
+(Originally it was O(LogN) for insert and delete)
+But to find the kth smallest element will only takes O(1).
+"""
diff --git a/problems/kth-smallest-element-in-a-sorted-matrix.py b/problems/kth-smallest-element-in-a-sorted-matrix.py
@@ -12,3 +12,38 @@ def kthSmallest(self, matrix, k):
             opt.append(m)
             memo[i_min]+=1
         return opt[-1]
+
+"""
+Time: O(kN).
+Space: O(kN)
+"""
+
+
+class Solution(object):
+    def kthSmallest(self, matrix, k):
+        def count_smaller(t):
+            count = 0
+            col = 0
+            for i, row in enumerate(reversed(matrix)):
+                while col<len(row) and row[col]<=t:
+                    count += len(matrix)-i
+                    col += 1
+            return count
+        
+        l = matrix[0][0]
+        r = matrix[-1][-1]
+        
+        while l<r:
+            m = (l+r)/2
+            c = count_smaller(m)
+            
+            if c<k:
+                l = m+1
+            else:
+                r = m
+                
+        return l
+
+"""
+Time: O(NLOG(max-min))
+"""
diff --git a/problems/minimum-absolute-difference-in-bst.py b/problems/minimum-absolute-difference-in-bst.py
@@ -0,0 +1,46 @@
+class Solution(object):
+    def getMinimumDifference(self, root):
+        stack = []
+        node = root
+        temp = float('-inf')
+        ans = float('inf')
+        
+        while node or stack:
+            while node:
+                stack.append(node)
+                node = node.left
+                
+            node = stack.pop()
+            ans = min(ans, node.val-temp)
+            temp = node.val
+            
+            node = node.right
+        return ans
+
+"""
+Time complexity: O(N)
+Space complexity: O(1)
+"""
+
+
+class Solution(object):
+    def getMinimumDifference(self, root):
+        def traverse(node):
+            if not node: return
+            traverse(node.left)
+            A.append(node.val)
+            traverse(node.right)
+            
+        A = []
+        ans = float('inf')
+        traverse(root)
+        
+        for i, n in enumerate(A):
+            if i==0: continue
+            ans = min(ans, A[i]-A[i-1])
+        return ans
+
+"""
+Time complexity: O(N)
+Space complexity: O(N)
+"""
diff --git a/problems/search-in-a-binary-search-tree.py b/problems/search-in-a-binary-search-tree.py
@@ -0,0 +1,19 @@
+class Solution(object):
+    def searchBST(self, root, val):
+        node = root
+        
+        while node:
+            if node.val==val:
+                return node
+            elif node.val>val:
+                node = node.left
+            else:
+                node = node.right
+
+        return None
+
+
+"""
+Time complexity: O(LogN)
+Space complexity: O(1)
+"""
diff --git a/problems/validate-binary-search-tree.py b/problems/validate-binary-search-tree.py
@@ -29,16 +29,10 @@ class Solution(object):
 	#recursive
     def isValidBST(self, root):
         def helper(node, min_val, max_val):
-            if node==None:
-                return True
-            if node.val<=min_val or node.val>=max_val:
-                return False
-            
-            left_valid = helper(node.left, min_val, node.val)
-            if not left_valid: return False
-            right_valid = helper(node.right, node.val, max_val)
-            if not right_valid: return False
-            
+            if not node: return True
+            if node.val<=min_val or node.val>=max_val:return False
+            if not helper(node.left, min_val, node.val): return False
+            if not helper(node.right, node.val, max_val): return False
             return True
         return helper(root, float('-inf'), float('inf'))
 
