Problem statement

https://leetcode.com/problems/largest-plus-sign/

Solution

Classical grid dp, where for each cell we need to find biggest number of continuous ones in for directions: up, down, left, right. We need to traverse our grid in 4 different directions and for this I use couple of tricks to make code shorter (notice though that it becomes slower, though complexity is still O(n^2).

  1. We create (N+2)x(N+2) grid where we add zero padding of size 1 in each direction.
  2. To traverse in direct or opposite direction we use range(1,N+1)[::(-dx>=0)*2-1]. Notice that if dx = 1, we have 1, ..., N+1 and if we have dx = -1, then range is (N+1, ..., 1). Similar logic for dy.

Complexity

Time complexity is O(n^2), however with quite big constant: we have 4 directions and also a lot of time spend for creating of empty dp array and finding maximum: so, it is like O(12n^2) in all. Space complexity is O(4n^2).

Code

class Solution:
    def orderOfLargestPlusSign(self, N, mines):
        grid = {tuple([x+1, y+1]) for x, y in mines}
        dp = [[[0] * 4 for _ in range(N+2)] for _ in range(N+2)]
        
        for dx, dy, dr in [(-1,0,0),(1,0,1),(0,-1,2),(0,1,3)]:
            for x in range(1,N+1)[::(-dx>=0)*2-1]:
                for y in range(1,N+1)[::(-dy>=0)*2-1]:
                    if (y, x) not in grid:
                        dp[y][x][dr] = dp[y+dy][x+dx][dr] + 1
                                                
        return max(min(q) for p in dp for q in p)