algoadvance

Leetcode 764. Largest Plus Sign

Problem Statement

You are given an integer n representing an n x n grid containing only 1’s and 0’s. You are also given an array mines where mines[i] = [xi, yi] represents the position (xi, yi) of a mine on the grid. Return the order of the largest axis-aligned plus sign of 1’s contained in the grid. If there is none, return 0.

An “axis-aligned plus sign of 1’s of order k” has some center cell (r, c) such that:

Example

n = 5, mines = [[4, 2]]
Output: 2

Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can be formed of order 2, where the center of the plus is at position (1, 2).

Clarifying Questions

  1. Can n be 0 or 1?
    • No, the minimum size of the grid is 2x2.
  2. Are there any constraints on the number and positions of mines?
    • Yes, there can be up to n * n mines, and they can be located anywhere on the grid.

Strategy

  1. Initialization: Create an n x n grid filled with 1s. Then, place mines (0s) in the grid as specified by the mines array.
  2. Dynamic Programming: Use four auxiliary grids to track the maximum count of consecutive 1s up to that cell in four directions (left, right, up, down).
  3. Combine the results: The value at any cell in these grids will give the maximum order of the plus sign centered at that cell.
  4. Find the result: The order of the largest plus sign is the maximum value in these grids.

Steps:

  1. Initialize the grid with 1’s and place mines.
  2. Create and populate auxiliary grids for left, right, up, and down directions.
  3. Calculate the maximum order of plus signs by taking the minimum of the values from these auxiliary grids for each cell.
  4. Find and return the maximum value obtained in the plus sign orders.

Code

public class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] grid = new int[n][n];
        
        // Fill grid with all 1s
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = 1;
            }
        }
        
        // Place mines
        for (int[] mine : mines) {
            grid[mine[0]][mine[1]] = 0;
        }
        
        int[][] left = new int[n][n];
        int[][] right = new int[n][n];
        int[][] up = new int[n][n];
        int[][] down = new int[n][n];
        
        // Fill the auxiliary grids
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    left[i][j] = (j > 0) ? left[i][j - 1] + 1 : 1;
                    up[i][j] = (i > 0) ? up[i - 1][j] + 1 : 1;
                }
            }
        }
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    right[i][j] = (j < n - 1) ? right[i][j + 1] + 1 : 1;
                    down[i][j] = (i < n - 1) ? down[i + 1][j] + 1 : 1;
                }
            }
        }
        
        // Calculate the largest plus sign order
        int maxOrder = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int order = Math.min(Math.min(left[i][j], right[i][j]), 
                                     Math.min(up[i][j], down[i][j]));
                maxOrder = Math.max(maxOrder, order);
            }
        }
        
        return maxOrder;
    }
}

Time Complexity

The space complexity is also O(n^2) because of the four auxiliary grids.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI