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

largestPlusSign.py

"""
Idea:
- If the question asked us to find the longest line in one cardinal direction
  (for example, south) from any point in the grid, we could just cache that
  value for every cell. I.e., for every cell, starting from the bottom, draw
  the longest line upwards that we can where at each cell the value = 1 + the
  value at the cell below it. 
- Instead, we're being asked to find the longest lin in ALL cardinal directions
  so we can just repeat this process four times--once for each cardinal direction
- Now the kicker: they also want the longest symmetrical line, i.e., the minimum
  of all possible cardinal lines that can be drawn from a given cell. So we just
  return the minimum of all four cardinal line lengths from each cell.
"""
class Solution:
    def orderOfLargestPlusSign(self, N: int, mines: List[List[int]]) -> int:
        # initialise to 1 because there's always a line of length 1
        north = [[1]*N for i in range(N)]
        south = [[1]*N for i in range(N)]
        east  = [[1]*N for i in range(N)]
        west  = [[1]*N for i in range(N)]
        # unless there's a mine in that cell, in which case it's a line of length 0
        for row, col in mines:
            north[row][col] = 0
            south[row][col] = 0
            east[row][col]  = 0
            west[row][col]  = 0

        # iterate in left -> right, top -> bottom order for north-west conflicts
        for row in range(N):
            for col in range(N):
                # north
                if row > 0 and north[row][col] != 0:
                    north[row][col] = north[row-1][col] + 1                    
                # west
                if col > 0 and west[row][col] != 0:
                    west[row][col] = west[row][col-1] + 1
                    
        # iterate in right -> left, bottom -> top order for south east conflicts
        for row in range(N-1, -1, -1):
            for col in range(N-1, -1, -1):
                # east
                if col < N-1 and east[row][col] != 0:
                    east[row][col] = east[row][col+1] + 1    
                # south
                if row < N-1 and south[row][col] != 0:
                    south[row][col] = south[row+1][col] + 1
                    
        result = 0 # track and return the max
        for row in range(N):
            for col in range(N):
                # i.e., the min of all cardinal lines that can be drawn from a given cell
                result = max(result, min(north[row][col], south[row][col], east[row][col], west[row][col]))
        
        return result