2020 June 20 Questions
74 views
Skip to first unread message
karan alang
Jun 21, 2020, 5:01:51 PM6/21/20
to leetcode-meetup
lc437 :
Time Complexity - O(n)
Space Complexity - O(height of Tree) (since i'm using recursion + list for storing the node values)
def pathSum(self, root: TreeNode, sum: int) -> int:
res = 0
# listOfNodes = []
def dfs(root, listOfNodes):
nonlocal res
# nonlocal listOfNodes
if not root: return
listOfNodes.append(root)
dfs(root.left, listOfNodes)
dfs(root.right, listOfNodes)
# iterate the listofnodes backwards
tmpSum = 0
for i in range(len(listOfNodes)-1, -1, -1):
tmpSum += listOfNodes[i].val
if tmpSum == sum:
res += 1
listOfNodes.pop()
dfs(root, [])
return res
Daryl Wang
Jun 27, 2020, 2:14:32 PM6/27/20
to leetcode-meetup
The brute force solution is to run a DFS from the root to find paths that start at the root. To handle paths that start further down in the tree, call the function recursively on the root's children.
This brute force solution gets exponential in the worst case; we can improve this with some memoization.
class Solution:
def pathSum(self, root: TreeNode, sum1: int) -> int:
if not root:
return 0
def helper(node, target):
ans = 0
if not node:
return ans
if node.val + target == sum1:
ans = 1
return helper(node.left, target + node.val) + helper(node.right, target + node.val) + ans
return helper(root, 0) + self.pathSum(root.left, sum1) + self.pathSum(root.right, sum1)
The key insight here is that we can keep a single sum of the current path, and still figure out if there are subpaths that hit the target. As we traverse the tree and sum up the path, we keep a dictionary of path lengths to number of times it has appeared in the tree. We can then check for if a subpath hits the target by looking for its complement:
Length of path - target
Each subpath that hits the target will be joined to a path that has the complement sum. This idea of finding the number of subtotals by keeping a running count of the cumulative totals and then looking for the complementary total is one that appears in multiple problems.
One complication is that since the map is shared by all dfs calls, we might end counting paths from the left subtree when we're going down the right subtree. We decrement the current path total after we're done with the dfs call to deal with this.
O(n) time
O(n) space
class Solution:
def pathSum(self, root: TreeNode, target_sum: int) -> int:
self.sums = collections.defaultdict(lambda: 0)
self.result = 0
# We start off with a sum of 0
self.sums[0] = 1
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
self.result += self.sums[running_sum - target_sum]
self.sums[running_sum] += 1
dfs(node.left, running_sum)
dfs(node.right, running_sum)
# Decrement the count now that we're done with the entire subtree, so that dfs calls on other parts of the tree don't get thrown off.
self.sums[running_sum] -= 1
dfs(root, 0)
return self.result
On Friday, June 19, 2020 at 7:55:39 PM UTC-7, Daryl Wang wrote:
Daryl Wang
Jun 27, 2020, 2:40:19 PM6/27/20
to leetcode-meetup
| 105 | Construct Binary Tree from Preorder and Inorder Traversal | 47.8% | Medium |
The main insight here is:
The first element of the preorder list is the root.
All of the elements before the root value in the inorder list are in the root's left subtree, and all elements after are in the right subtree.
So we have a way to find the root, the left subtree, and the right subtree. We can then solve the subtrees recursively.
O(n) time. My code posted below is a little sloppy in searching the inorder list and picking the root from the perorder list so it's O(n) per call, but it's possible to make these O(1) via a map for the inorder list and a head pointer for the preorder list.
O(1) space per call, O(n) calls on stack
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def build_tree(inorder_sublist):
if not inorder_sublist:
return None
val = preorder.pop(0)
inorder_index = inorder_sublist.index(val)
root = TreeNode(val)
root.left = build_tree(inorder_sublist[:inorder_index])
root.right = build_tree(inorder_sublist[inorder_index + 1:])
return root
return build_tree(inorder)
On Friday, June 19, 2020 at 7:55:39 PM UTC-7, Daryl Wang wrote:
Daryl Wang
Jun 27, 2020, 3:22:04 PM6/27/20
to leetcode-meetup
| 85 | Maximal Rectangle | 37.1% | Hard |
This is a dynamic programming problem. We start at the top left and work our way down to the bottom right. For each cell we calculate the largest possible rectangle at that position. If the cell is 0 then the rectangle is 0 and we move on.
If the cell is 1 then we have more work to do. There will be a rectangle of minimum size 1 at this cell, but there could be bigger rectangles. We check then neighbors to see if we can then
The solution makes two passes. The first checks to see how many long a row of 1's goes for each cell, and the second checks for the longest column of 1's. After checking the current row/column, the algorithm then tries to see if there is a neighboring rectangle that this cell could be part of.
O(n^2) time
O(n^2) space
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
area = 0
if not matrix:
return area
dp = [[(0,0)] * len(matrix[0]) for _ in range(len(matrix))]
def calcArea(tpl):
return tpl[0] * tpl[1]
for i in range(len(matrix)):
prevHort = 0
for j in range(len(matrix[i])):
if matrix[i][j] == "1":
prevHort += 1
dp[i][j] = (prevHort, 1)
if i > 0:
prevWidth, prevHeight = dp[i - 1][j]
extendUp = (min(prevHort, prevWidth), prevHeight + 1)
if calcArea(extendUp) > calcArea(dp[i][j]):
dp[i][j] = extendUp
area = max(area, calcArea(dp[i][j]))
else:
prevHort = 0
for j in range(len(matrix[0])):
prevVert = 0
for i in range(len(matrix)):
if matrix[i][j] == "1":
prevVert += 1
dp[i][j] = (1, prevVert)
if j > 0:
prevWidth, prevHeight = dp[i][j - 1]
extendLeft = (prevWidth + 1, min(prevVert, prevHeight))
if calcArea(extendLeft) > calcArea(dp[i][j]):
dp[i][j] = extendLeft
area = max(area, calcArea(dp[i][j]))
else:
prevVert = 0
dp[i][j] = (0,0)
return area
On Friday, June 19, 2020 at 7:55:39 PM UTC-7, Daryl Wang wrote:
Reply all
Reply to author
Forward
0 new messages