Largest Plus Sign Leetcode Solution

Difficulty Level Medium
Frequently asked in Facebook Microsoft UberViews 21

Problem Statement :

Largest Plus Sign Leetcode Solution – You are given an integer n. You have an n x n binary 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 the 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 :

Example 1 

Largest Plus Sign Leetcode SolutionPin

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

 

Largest Plus Sign Leetcode Solution

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

Constraints :

Largest Plus Sign Leetcode SolutionPin

Observation :

  • We need to Find the largest axis-aligned plus sign of 1’s contained in the grid.
  • In the matrix, we have only 4 directions i.e. left, right, up, and down.
  • Let’s say, in the left direction we have 6 length sides of 1 contained in the grid, on the right side, we have 8 length sides of 1 contained in the grid, in the top, we have 5 length sides and in the bottom, we have the side of length 7.
  • To make a valid largest axis-aligned mark of 1, we need to take the minimum of all four directions.

Algorithm :

  1. For each direction (Left, Right, Up, Down), and for each coordinate (r, c)and take the coordinate as the center of the plus sign, let’s calculate the count of that coordinate: starting at (r,c) the longest line of ‘1’ is going in that direction.
    • Get the length of 4 arms: RIGHT, DOWN, LEFT, UP
    • The size of the plus-sign is a minimum of 4 arms.
  1. Taking all coordinates as a center, we will calculate our largest axis-aligned plus sign from the maximum of all.
  2. How to find the length of the arms efficiently?
    • We can use dynamic programming to calculate the maximum size of 4 arms starting from position (R, C) in 4 directions: RIGHT, DOWN, LEFT, UP.
    • We will calculate the prefix sum of 1’s in all 4 directions.
    • Let dP(r, c, d) is the longest arm starting at cell r, c and extending in direction d.
    • Our direction array will be int[] DIR={ {0,1} , {1,0} , {0,-1} , {-1,0} }
    • DIR[0] means RIGHT direction, corresponding to (r + DIR[0][0], c + DIR[0][1])
    • DIR[1] means  DOWN direction, corresponding to (r + DIR[1][0], c + DIR[1][1])
    • DIR[2] means LEFT direction, corresponding to (r + DIR[2][0], c + DIR[2][1])
    • DIR[3] means TOP direction, corresponding to (r + DIR[3][0], c + DIR[3][1])
    • Base case: If (r, c) is out of bound or grid[r][c] is a mined cell then dp(r, c, d) = 0.

Code For Largest Plus Sign

Java  Code 

class Solution {
    int[][]DIR = {{0,1},{1,0},{0,-1},{-1,0}};
     Set<Integer> minesSet = new HashSet();
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        Integer[][][]dp=new Integer[n][n][4];
         for (int[] mine: mines){
            minesSet.add(mine[0] * n + mine[1]);
         }
           int ans = 0; 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int plusSignLength=(int)(1e9);
                for(int d=0;d<4;d++){
               plusSignLength=Math.min(dpPrefixSumInGrid(n,i,j,d,dp),plusSignLength);
                }
                ans=Math.max(ans,plusSignLength);
            }
        }
        return ans;
    }
    
    public int dpPrefixSumInGrid(int n,int r,int c,int d,Integer[][][]dp){
      if(r<0|| c<0|| r>=n|| c>=n||minesSet.contains(r*n+c))return 0;
        if(dp[r][c][d]!=null)return dp[r][c][d];
       return dp[r][c][d]=dpPrefixSumInGrid(n,r+DIR[d][0],c+DIR[d][1],d,dp)+1;
    }
}

C++  Code 

class Solution {
      int DIR[4][2] ={{0,1},{1,0},{0,-1},{-1,0}};
  unordered_set <int> minesSet;
    int dp[500][500][4]={};
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
     for (auto &it: mines){
            minesSet.insert(it[0] * n + it[1]);
         }
        int ans = 0; 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int plusSignLength=(int)(1e9);
                for(int d=0;d<4;d++){
               plusSignLength=min(dpPrefixSumInGrid(n,i,j,d),plusSignLength);
                }
                ans=max(ans,plusSignLength);
            }
        }
        return ans;
        
    }
      int dpPrefixSumInGrid(int n,int r,int c,int d){
      if(r<0|| c<0|| r>=n|| c>=n||minesSet.find(r*n+c)!=minesSet.end())return 0;
        if(dp[r][c][d]!=0)return dp[r][c][d];
       return dp[r][c][d]=dpPrefixSumInGrid(n,r+DIR[d][0],c+DIR[d][1],d)+1;
    }
};

Complexity Analysis for Largest Plus Sign Leetcode Solution:

Time Complexity

 O(N ^ 2) ,where N <= 500 is the side size of the square grid.

Space Complexity 

O(N^2), at max all elements in the grid are zero. So, our set contains (N ^ 2) elements.

Translate »