Largest Square with all 1 in the boundary


  • 1
    S

    Given a matrix containing either 0 or 1 in each cell, find the square with the longest side containing all 1s in its boundary. Cells inside the square may contain either 0 or 1.

    For example, given matrix

    [
      [0, 1, 0, 1, 1]
      [0, 1, 1, 1, 0]
      [0, 1, 0, 1, 1]
      [1, 1, 1, 1, 1]
      [1, 1, 1, 1, 1]
    ]
    

    The square with the maximum size containing all 1s in its boundary has top-left corner at (1,1) and bottom-right corner at (3, 3).

    Note: You only need to return the length of each side of the square, In the above example, the length of each side of the square is 3.


  • 2
    M

    Create two 2D arrays of the same size, and keep track of the longest top-to-bottom side and longest left-to-right side at any given point in the matrix.

    Finding the side length of the square would be easy from there.

    	public static int getLargestSquareSide(int[][] matrix) {
    
    		int maxLength = 0;
    
    		int rows = matrix.length;
    
    		if (rows == 0)
    			return 0;
    
    		int cols = matrix[0].length;
    
    		int[][] lToRLength = new int[rows][cols];
    		int[][] tTobLength = new int[rows][cols];
    
    		for (int i = 0; i < cols; i++) {
    			tTobLength[0][i] = matrix[0][i];
    			if (matrix[0][i] == 1) {
    				lToRLength[0][i] = (i > 0) ? lToRLength[0][i - 1] + 1 : 1;
    				maxLength = 1;
    			} else {
    				lToRLength[0][i] = 0;
    			}
    		}
    
    		if (rows == 1)
    			return maxLength;
    
    		if (cols == 0)
    			return 0;
    
    		for (int i = 0; i < rows; i++) {
    			lToRLength[i][0] = matrix[i][0];
    			if (matrix[i][0] == 1) {
    				tTobLength[i][0] = (i > 0) ? (tTobLength[i - 1][0] + 1) : 1;
    				maxLength = 1;
    			} else {
    				tTobLength[i][0] = 0;
    			}
    		}
    
    		if (cols == 1)
    			return maxLength;
    
    		for (int i = 1; i < rows; i++) {
    			for (int j = 1; j < cols; j++) {
    				if (matrix[i][j] != 1) {
    					tTobLength[i][j] = 0;
    					lToRLength[i][j] = 0;
    				} else {
    					tTobLength[i][j] = tTobLength[i - 1][j] + 1;
    					lToRLength[i][j] = lToRLength[i][j - 1] + 1;
    
    					int sideLength = 1;
    
    					for (int maxSide = Math.min(tTobLength[i][j], lToRLength[i][j]); maxSide > 1; maxSide--) {
    						if (tTobLength[i][j - maxSide + 1] >= maxSide && lToRLength[i - maxSide + 1][j] >= maxSide) {
    							sideLength = maxSide;
    							break;
    						}
    					}
    					maxLength = Math.max(maxLength, sideLength);
    				}
    			}
    		}
    
    		return maxLength;
    	}
    

  • 0

    Another aproach is to fill with 0 all regions bounded by 0 .Then find maximum rectangle all with 0


  • 0

    Sorry I am not able to edit now. There is a minor mistake in the approach above.We should fill with 1
    all bounded with 1 regions and later find maximum square all with 1


  • 0
    M

    @elmirap

    I wonder if that approach would be better in worst case time for a huge matrix


  • 0

    Yes, the first approach is more efficient.I mentioned the second one as an option.


  • 2
    L

    @mithmatt In case if anyone has any difficulty understanding the code, the same approach is explained in detail here -
    http://www.geeksforgeeks.org/given-matrix-o-x-find-largest-subsquare-surrounded-x/


  • 0
    S

    Since it's only 1's and 0's, just keep a sum. Everytime you hit a 1, increment sum and everytime u hit a 0, set sum = 0. Now if sum > max ( stored), then check if a square of this size (sum) exists. If so, set max to the new sum. O(n^2) solution (I Think) and O(1) space. ^-^

    // FB problem to find the sqaure with largest 1's
    bool check(const vector<vector<int>>& v, int i, int j,int sum){
    	if (sum == 1) return true; // square of size 1
    	//cout <<  i << " "<<j<< " " <<sum<< " "<<j-sum +1 << " "<<i+sum-1<<endl;
    	// ck outof bounds
    	if (j-sum +1 < 0 || i+sum-1 >= v.size()) 
    		return false; // out of bounds
    	//cout << " ======================= in here\n";
    	// right bottom
    	int row = 0,col = 0;
    	for (int row = i; row < i + sum; ++row)
    		if (v[row][j] == 0)
    			return false;
    
    	// check left
    	for (col = j -sum+1; row < i +sum; ++row)
    		if (v[row][j] == 0)
    			return false;
    
    	// check bottom most
    	row = j - sum+1;
    	col = i + sum -1;
    	for (; col <= j; ++col)
    		if (v[row][col] == 0)
    			return false;
    
    	return true;
    
    }
    
    int findMax(const vector<vector<int>>& v){
    	int max = 0,sum = 0; 
    	for (int i = 0; i < v.size();++i){
    		for (int j = 0;j<v[0].size();++j){
    			if (v[i][j] == 1) sum++; // increment sum
    			else if (v[i][j] == 0) sum = 0; // lost the sum
    			if (sum > max && check(v,i,j,sum))
    				max = sum; // new max square 
    		}
    	}
    	return max;
    }
    
    

  • 0
    int maxOnesSquare(int[][] grid) {
    		int max = 0;
    		for (int i = 0; i < grid.length; i++) {
    			for (int j = 0; j < grid[i].length; j++) {
    				max = Math.max(max, maximumSquareLength(grid, i, j));
    			}
    		}
    		return max;
    	}
    
    	int maximumSquareLength(int[][] grid, int i, int j) {
    		if (grid[i][j] == 0)
    			return 0;
    		int max = 1;
    		int maxLength = grid.length - j;
    		for (int k = 2; k <= maxLength && (j + k) <= grid.length && (i + k) <= grid.length; k++)
    			max = Math.max(max, allOnes(grid, i, j, k));
    		return max;
    	}
    
    	int allOnes(int[][] grid, int i, int j, int k) {
    		// check right horizontal
    		for (int c = j; c < (j + k) && c < grid.length; c++) {
    			if (grid[i][c] == 0)
    				return 0;
    		}
    
    		// check right vertical
    		for (int r = i; r < (i + k) && r < grid.length; r++) {
    			if (grid[r][j + k - 1] == 0)
    				return 0;
    		}
    
    		// check left horizontal
    		for (int c = j; c < (j + k) && c < grid.length; c++) {
    			if (grid[i + k - 1][c] == 0)
    				return 0;
    		}
    
    		// check right vertical
    		for (int r = i; r < (i + k) && r < grid.length; r++) {
    			if (grid[r][j] == 0)
    				return 0;
    		}
    		return k;
    	}
    

  • 0
    D

    @k' great perfect


  • 0
    S

    @swaranga Is the problem statement to find sub matrix with all 1s or just the boundary with 1s ? The same problem is mentioned elsewhere with requirement that cells in the sub matrix be 1. For dynamic programming to be applicable in this case, all cells need to be 1s


  • 1
    
    
    public int longestOnes(int[][] m){
    	
    	if(m == null|| m.length == 0 || m[0].length == 0){
    		
    		return -1;
    	}
    	int[][] leftToRight = new int[m.length][m[0].length];//iterate along columns
    	int[][] topToBott = new int[m.length][m[0].length];//iterate along rows
    	for(int r = 0; r < m.length; r++){
    		if(m[r][0] == 1){
    			leftToRight[r][0] = 1;
    		}
    		
    	}
    	for(int c = 0; c < m[0].length; c++){
    		if(m[0][c] == 1){
    			
    			topToBott[0][c] = 1;
    		}
    	}
    	for(int c = 1; c < m[0].length; c++){
    		for(int r = 0; r < m.length; r++){
    			
    			if(m[r][c] == 1){
    				
    				leftToRight[r][c] = leftToRight[r][c - 1] + 1;
    			}
    		}
    		
    	}
    	for(int r = 1; r < m.length; r++){
    		
    		for(int c = 0; c < m[0].length; c++){
    			
    			if(m[r][c] == 1){
    				topToBott[r][c] = topToBott[r - 1][c] + 1;
    			}
    		}
    	}
    	int maxLen = 0;
    	for(int d = 1; d < Math.min(m.length,m[0].length);d++){
    		
    		for(int r = 0; r < m.length; r++){
    			for(int c = 0; c < m[0].length;c++){
    				if((r + d <= m.length) && (c + d <= m[0].length)){
    					int bottRowOnes = topToBott[r + d - 1][c + d - 1] - ((c > 0)?topToBott[r + d - 1][c - 1]:0);
    					int topRowOnes = topToBott[r][c] - ( (c > 0)?topToBott[r][c - 1]: 0);
    					int leftColOnes = leftToRight[r][c] - ((r > 0)? leftToRight[r - 1][c]: 0);
    					int rightColOnes = leftToRight[ r + d - 1][ c + d - 1] - ((r > 0)? leftToRight[r - 1][c + d - 1]:0);
    					if(bottRowOnes == topRowOnes && rightColOnes == leftColOnes && bottRowOnes == leftColOnes){
    						maxLen = d;
    					}
    					
    				}
    			}
    		}
    	}
    	return maxLen;
    	
    }

  • 0
    A

    python solution O(n^3)

    def find_largest_square(mat):
        m, n = len(mat), len(mat[0])
        col_cont = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0:
                    col_cont[i][j] = mat[i][j]
                else:
                    if mat[i][j]:
                        col_cont[i][j] = col_cont[i - 1][j] + 1
                    else:
                        col_cont[i][j] = 0
    
        row_cont = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if j == 0:
                    row_cont[i][j] = mat[i][j]
                else:
                    if mat[i][j]:
                        row_cont[i][j] = row_cont[i][j - 1] + 1
                    else:
                        row_cont[i][j] = 0
    
        max_edge = 0
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                edge = min(row_cont[i][j], col_cont[i][j])
                for e in reversed(range(edge)):
                    if row_cont[i - e][j] >= e + 1 and col_cont[i][j - e] >= e + 1:
                        max_edge = max(max_edge, e + 1)
                        break
        return max_edge
    
    mat = [[0, 1, 0, 1, 1],
           [0, 1, 1, 1, 0],
           [0, 1, 0, 1, 1],
           [1, 1, 1, 1, 1],
           [1, 1, 1, 1, 1]]
    
    print find_largest_square(mat)
    #3
    
    mat = [[1, 0, 1, 1, 1, 1],
           [1, 0, 1, 1, 0, 1],
           [1, 1, 1, 0, 0, 1],
           [1, 1, 1, 1, 1, 1],
           [1, 1, 1, 0, 1, 0]]
    
    print find_largest_square(mat)
    #4
    
    

  • 0
    F
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.