algoadvance

Leetcode 764. Largest Plus Sign

Problem Statement

You are given an integer n and an array mines where mines[i] = [xi, yi] represents a mine located at (xi, yi) in an n x n 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 (r, c) such that:

Clarifying Questions

  1. What are the constraints on n?
    • 1 <= n <= 500.
  2. What are the constraints on the number of mines?
    • 0 <= mines.length <= n * n.
  3. Can there be multiple plus signs? If so, should we return the largest one?
    • Yes, there can be multiple plus signs. We need to return the order of the largest plus sign.
  4. What if there are no plus signs?
    • If there are no plus signs, return 0.

Strategy

  1. Create a grid n x n initialized to 1: Marks where the empty spaces are initially.
  2. Mark mines in the grid as 0: This will destroy any possible plus that includes the cell with a mine.
  3. Use dynamic programming to track maximum arms’ lengths for plus signs:
    • For each cell (i, j) in the grid, compute lengths of arms in all four directions (left, right, up, down).
    • Store minimum length of arms in a separate grid which will tell us the size of the largest plus centered at that cell.
    • Traverse the grid to find the maximum size plus.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int orderOfLargestPlusSign(int n, std::vector<std::vector<int>>& mines) {
        std::vector<std::vector<int>> grid(n, std::vector<int>(n, n));
        
        for (const auto& mine : mines) {
            grid[mine[0]][mine[1]] = 0;
        }
        
        for (int i = 0; i < n; ++i) {
            int left = 0, right = 0, up = 0, down = 0;
            for (int j = 0; j < n; ++j) {
                // Left pass
                left = (grid[i][j] == 0) ? 0 : left + 1;
                grid[i][j] = std::min(grid[i][j], left);
                
                // Right pass
                right = (grid[i][n - 1 - j] == 0) ? 0 : right + 1;
                grid[i][n - 1 - j] = std::min(grid[i][n - 1 - j], right);
                
                // Up pass
                up = (grid[j][i] == 0) ? 0 : up + 1;
                grid[j][i] = std::min(grid[j][i], up);
                
                // Down pass
                down = (grid[n - 1 - j][i] == 0) ? 0 : down + 1;
                grid[n - 1 - j][i] = std::min(grid[n - 1 - j][i], down);
            }
        }

        int largestPlus = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                largestPlus = std::max(largestPlus, grid[i][j]);
            }
        }

        return largestPlus;
    }
};

Time Complexity

This solution ensures that we efficiently determine the order of the largest plus sign possible in the grid.

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