764.md

764 Largest Plus Sign

Description

link

---

Solution 1 : DP TLE

dp[i][j] : the max ans can be get in position (i,j)

Recursive :

• dp[i][y] = min(dp[i][y], abs(i - x)), dp[x][i] = min(dp[x][i], abs(i - y)) for i in range(N), for (x, y) in mines

Init : min(i, N-1-i, j, N-1-j)

Max ans can get in position (i,j)

---

Code 1

Complexity T : O(n^2) M : O(n^2)

class Solution:
    def orderOfLargestPlusSign(self, N, mines):
        """
        :type N: int
        :type mines: List[List[int]]
        :rtype: int
        """
        dp = [[min(i, N-1-i, j, N-1-j) + 1 for j in range(N)] for i in range(N)]
        
        for (x, y) in mines:
            for i in range(N):
                dp[i][y] = min(dp[i][y], abs(i - x))
                dp[x][i] = min(dp[x][i], abs(i - y))

        return max([max(row) for row in dp])

---

Solution 2 : DP AC

dp[i][j][k] : the max ans can be get in position (i,j)

k :

• 0 : UP
• 1 : LEFT
• 2 : DOWN
• 3 : RIGHT

Recursive :

two cycles, one from top to down and from left to right, dp[i][j][k] = dp[i - 1][j][0k + 1 if (i, j) not in mines else 1, min(dp[i][j]) means max res in position (i,j)

---

Code 2

Complexity T : O(n^2) M : O(n^2)

class Solution:
    def orderOfLargestPlusSign(self, N, mines):
        """
        :type N: int
        :type mines: List[List[int]]
        :rtype: int
        """
        #up, left, down, right
        dp, res, mines = [[[0, 0, 0, 0] for j in range(N)] for i in range(N)], 0, {(i, j) for i, j in mines}
        for i in range(N):
            for j in range(N):
                if (i, j) not in mines:
                    try:
                        dp[i][j][0] = dp[i - 1][j][0] + 1
                    except:
                        dp[i][j][0] = 1
                    try:
                        dp[i][j][1] = dp[i][j - 1][1] + 1
                    except:
                        dp[i][j][1] = 1

        for i in range(N - 1, -1, -1):
            for j in range(N - 1, -1, -1):
                if (i, j) not in mines:
                    try:
                        dp[i][j][2] = dp[i + 1][j][2] + 1
                    except:
                        dp[i][j][2] = 1
                    try:
                        dp[i][j][3] = dp[i][j + 1][3] + 1
                    except:
                        dp[i][j][3] = 1
                    res = max(res, min(dp[i][j]))
        return res

---

Solution 3 : Less MEMO

just one DP dimension

---

Code 2

Complexity T : O(n^2) M : O(n^2)

class Solution:
    def orderOfLargestPlusSign(self, N, mines):
        """
        :type N: int
        :type mines: List[List[int]]
        :rtype: int
        """
        #up, left, down, right
        dp, res, mines = [[0 for j in range(N)] for i in range(N)], 0, {(i, j) for i, j in mines}

        for j in range(N):
            cnt = 0
            for i in range(N):
                cnt = 0 if (i, j) in mines else cnt + 1
                dp[i][j] = cnt

            cnt = 0
            for i in range(N - 1, -1, -1):
                cnt = 0 if (i, j) in mines else cnt + 1
                dp[i][j] = min(cnt, dp[i][j])

        for i in range(N):
            cnt = 0
            for j in range(N):
                cnt = 0 if (i, j) in mines else cnt + 1
                dp[i][j] = min(cnt, dp[i][j])

            cnt = 0
            for j in range(N - 1, -1, -1):
                cnt = 0 if (i, j) in mines else cnt + 1
                dp[i][j] = min(cnt, dp[i][j])

        res = max([max(row) for row in dp])
        return res