You need to store level and maximum height (span) wrt root for each node in a hashmap, then store maximum and second maximum span values for each level.
I have yesterday LC:2458 solution for ref. First, create 3x tables, 1. Node vs level from root. 2. Node vs Height from leave. 3. Node same level cousins Max 2x heights. Func. findH is to create these 3x tables. At the end, it solve the answer by each query in queries, class Solution: def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]: node_lv = [-1] * 100001 #node level -> current lv from root where root is 0 node_h = [0] * 100001 #node height -> distance from its lowest leaf top2h = [[0] * 2 for _ in range(100001)] #Keep top 2x height at this level def findH (node, lv): #Preprocessing => create node_lv, node_h, top2h tables if not node: return 0 h = 1 + max(findH(node.left, lv + 1), findH(node.right, lv + 1)) node_lv[node.val] = lv node_h[node.val] = h if h > top2h[lv][0]: top2h[lv][1] = top2h[lv][0] top2h[lv][0] = h elif h > top2h[lv][1]: top2h[lv][1] = h return h findH(root, 0) #Start the preprocessing res = [] for q in queries: #Process each query lv = node_lv[q] h = node_h[q] maxH = top2h[lv][1] if h == top2h[lv][0] else top2h[lv][0] res.append(maxH + lv - 1) return res
🥳, I've done alone without seeing solution or video, I got logic within 10-15 min, but there was lot of bug and fixing it by using print statment at many areas and finished code successfully and took 1hour and 15 min. count=0 @cache def dp(row,col): f=s=t=0 if col==len(grid[0])-1: return 0 curr=grid[row][col] if row>0 and grid[row-1][col+1]>curr: f=1+dp(row-1,col+1) else: f=0 if grid[row][col+1]>curr: s=1+dp(row,col+1) else: s=0 if rowcurr: t=1+dp(row+1,col+1) else: t=0 return max(f,s,t) for i in range(len(grid)): count=max(count,dp(i,0)) return count
At 6:54, isn't the maximal square of the 1 to the right of the origin a 2x2 square? The origin still ends up having a 2x2 square due to the 1s below and to the diagonal having the minimum square size of 1, but I just wanted to get that clarified.
The trick is that you solved a similar problem 3 years ago and still remember it. I solve a problem few months back and don't remember it at all. Could you tell me how often you revise these problems?
good question i also have the same doubt i usually forget the question i did yesterday. I have never seen any revision strategy. everyone just says practice more question and that it. but some of them are classical problem and we might need to know or recall.
If someone wants one of the previous neetcode's solution to be just updated by 1 more lines - class Solution: def countSquares(self, matrix: List[List[int]]) -> int: ROWS, COLS = len(matrix), len(matrix[0]) cache = {} def dfs(r, c): if (r, c) in cache: return cache[(r, c)] if r not in range(ROWS) or c not in range(COLS): return 0 right = dfs(r + 1, c) down = dfs(r, c + 1) dia = dfs(r + 1, c + 1) if matrix[r][c] == 1: cache[(r, c)] = 1 + min(right, down, dia) else: cache[(r, c)] = 0 return cache[(r, c)] sumVal = sum(dfs(r, c) for r in range(ROWS) for c in range(COLS)) return sumVal
I watched until 1:38 to be able to solve the problem, I think that I jumped too fast to the solution. But as always thank you very much NeetCode!. Edit, my solution was pretty different I did not used cache neither matrix but the first intuition was the same: impl Solution { pub fn count_squares(matrix: Vec) -> i32 { let mut res = 0; let row = matrix.len(); let col = matrix[0].len(); fn count_squares( matrix: &Vec, r_start: usize, c_start: usize, r_end: usize, c_end: usize, ) -> i32 { for c in c_start..c_end { if matrix[r_end - 1][c] == 0 { return 0; } } for r in r_start..r_end { if matrix[r][c_end - 1] == 0 { return 0; } } if r_end < matrix.len() && c_end < matrix[0].len() { return 1 + count_squares(matrix, r_start, c_start, r_end + 1, c_end + 1); } return 1; } for r in 0..row { for c in 0..col { res += count_squares(&matrix, r, c, r + 1, c + 1); } } res } }
Funnily enough, a brute force method has a lower runtime than the DP or the recursive one. I guess it's because the matrices are not that big in the leetcode's test cases
the idea is like this suppose top left cell only results in 1x1 matrix then ouput is 1 if top left results in 2x2 matrix then it is top left 2 matrics, 1x1 and 2x2 similar;y if it is top left of 3x3 matrix then, it is top left of 3 different matrix, 1x1,2x2,and 3x3 and so on and so forth this is the logic of adding the sums. each element only adds the numberof arrays stemming from it hope this helps
I went out and went back in after sometime. How's the car looking? my father asked. "Me at Leetcode" I just replied. He smiled and nodded. He knew the car was washed.
