764. Largest Plus Sign LeetCode Solution

In this guide, you will get 764. Largest Plus Sign LeetCode Solution with the best time and space complexity. The solution to Largest Plus Sign problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Largest Plus Sign solution in C++
Largest Plus Sign solution in Java
Largest Plus Sign solution in Python
Additional Resources

764. Largest Plus Sign LeetCode Solution image

Problem Statement of Largest Plus Sign

You are given an integer n. You have an n x n binary grid grid with all values initially 1’s except for some indices given in the array mines. The ith element of the array mines is defined as mines[i] = [xi, yi] where grid[xi][yi] == 0.
Return the order of the largest axis-aligned plus sign of 1’s contained in grid. If there is none, return 0.
An axis-aligned plus sign of 1’s of order k has some center grid[r][c] == 1 along with four arms of length k – 1 going up, down, left, and right, and made of 1’s. Note that there could be 0’s or 1’s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1’s.

Example 1:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

Example 2:

Input: n = 1, mines = [[0,0]]
Output: 0
Explanation: There is no plus sign, so return 0.

Constraints:

1 <= n <= 500
1 <= mines.length <= 5000
0 <= xi, yi < n
All the pairs (xi, yi) are unique.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

764. Largest Plus Sign LeetCode Solution in C++

class Solution {
 public:
  int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
    vector<vector<int>> grid(n, vector<int>(n, n));

    for (const vector<int>& mine : mines)
      grid[mine[0]][mine[1]] = 0;

    // Extend the four directions. If meet 0, need to start over from 0.
    for (int i = 0; i < n; ++i) {
      for (int j = 0, leftToRight = 0; j < n; ++j) {
        leftToRight = (grid[i][j] == 0 ? 0 : leftToRight + 1);
        grid[i][j] = min(grid[i][j], leftToRight);
      }
      for (int j = n - 1, rightToLeft = 0; j >= 0; --j) {
        rightToLeft = (grid[i][j] == 0 ? 0 : rightToLeft + 1);
        grid[i][j] = min(grid[i][j], rightToLeft);
      }
      for (int j = 0, upToDown = 0; j < n; ++j) {
        upToDown = (grid[j][i] == 0 ? 0 : upToDown + 1);
        grid[j][i] = min(grid[j][i], upToDown);
      }
      for (int j = n - 1, downToUp = 0; j >= 0; --j) {
        downToUp = (grid[j][i] == 0) ? 0 : downToUp + 1;
        grid[j][i] = min(grid[j][i], downToUp);
      }
    }

    int ans = 0;

    for (const vector<int>& row : grid)
      ans = max(ans, ranges::max(row));

    return ans;
  }
};
/* code provided by PROGIEZ */

764. Largest Plus Sign LeetCode Solution in Java

class Solution {
  public int orderOfLargestPlusSign(int n, int[][] mines) {
    int[][] grid = new int[n][n];
    Arrays.stream(grid).forEach(A -> Arrays.fill(A, n));

    for (int[] mine : mines)
      grid[mine[0]][mine[1]] = 0;

    // Extend the four directions. If meet 0, need to start over from 0.
    for (int i = 0; i < n; ++i) {
      for (int j = 0, leftToRight = 0; j < n; ++j) {
        leftToRight = (grid[i][j] == 0 ? 0 : leftToRight + 1);
        grid[i][j] = Math.min(grid[i][j], leftToRight);
      }
      for (int j = n - 1, rightToLeft = 0; j >= 0; --j) {
        rightToLeft = (grid[i][j] == 0 ? 0 : rightToLeft + 1);
        grid[i][j] = Math.min(grid[i][j], rightToLeft);
      }
      for (int j = 0, upToDown = 0; j < n; ++j) {
        upToDown = (grid[j][i] == 0 ? 0 : upToDown + 1);
        grid[j][i] = Math.min(grid[j][i], upToDown);
      }
      for (int j = n - 1, downToUp = 0; j >= 0; --j) {
        downToUp = (grid[j][i] == 0) ? 0 : downToUp + 1;
        grid[j][i] = Math.min(grid[j][i], downToUp);
      }
    }

    int ans = 0;

    for (int[] row : grid)
      ans = Math.max(ans, Arrays.stream(row).max().getAsInt());

    return ans;
  }
}
// code provided by PROGIEZ