One of the few times I got to the solution on my own and thought to myself, this is for sure gonna give a time out and was so surprised that it worked. I've for sure missed your videos over the past couple of days, thanks @neetcodeio for your videos and explanations
You can kind of tell ahead of time whether or not a solution will time out by looking at the problem constraints. For this problem, they're n == grid.length == grid[i].length 3
simple as: class Solution: def largestLocal(self, g: List[List[int]]) -> List[List[int]]: return[ [max(*g[i][j:j+3],*g[i+1][j:j+3],*g[i+2][j:j+3])for j in range(len(g)-2)] for i in range(len(g)-2)]
Solve this one with only 2 nested loops for each i, j element where i is 0...N and j is 0...N-2. Firstly you need to count max of every three elements in rows and write it to the first one, after second row we count max of last three elements in each column and write it to the first one. As a result cut off last 2 rows and columns of modified grid and return it. Seems easier for me and more efficient
class Solution: def largestLocal(self, grid: List[List[int]]) -> List[List[int]]: n = len(grid) - 2 res = [[0] * (n) for _ in range(n)] for i in range(n): for j in range(n): res[i][j] = max(max(row[j:j+3]) for row in grid[i:i+3]) return res
is it more effificent than my solution i think its o(n^2) ? class Solution: def largestLocal(self, grid: List[List[int]]) -> List[List[int]]: res = [] for i in range(1, len(grid) - 1): row = [] for j in range(1, len(grid) - 1): cur_max = max(grid[i][j], grid[i+1][j], grid[i][j+1], grid[i-1][j], grid[i][j-1], grid[i+1][j+1], grid[i+1][j-1], grid[i-1][j+1], grid[i-1][j-1],) row.append(cur_max) res.append(row) return res
Time Complexity - 119ms (74%) class Solution: def largestLocal(self, grid: List[List[int]]) -> List[List[int]]: n = len(grid) result = [] for i in range(n-2): a = [] for j in range(n-2): a.append(max(max(x[j:j+3]) for x in grid[i:i+3])) result.append(a) return result
