• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Maximum size of square sub matrix with all 1’s in a binary matrix

December 12, 2017 by Dhaval Dave

Maximum size of square sub matrix with all 1

Consider a binary matrix as shown in the figure below. You need to find the maximum size of square sub matrix with all 1’s.

Sample problem

Naive Implementation

The naive solution for this problem will be to consider each and every sub matrix and then check if it is max one or not.

Code

The code for naive solution is pretty straight forward.


#include <bits/stdc++.h>
using namespace std;

int findMaxOnesMatrixSize(vector<vector<int> > &matrix){

	int n = matrix.size();
	int m = matrix[0].size();

	int maxOnesMatrixSize = 0;

	for(int a = 1 ; a <= max(m,n) ; a ++){

		for(int i = 0 ; i < n ; i ++)
			for(int j = 0 ; j < m ; j ++){

				int temp = 1;

				if(i + a > n || j + a > m)
					continue;

				for(int x = i ; x < i + a; x ++)
					for(int y = j ; y < j + a ; y ++)
						if(matrix[x][y] == 0){
							temp = 0;
							break;
						}

				if(temp)
					maxOnesMatrixSize = max(maxOnesMatrixSize,a);

			}

	}

	return maxOnesMatrixSize;

}

// Driver function .............
int main(){

	int test;
	cin >> test;

	while(test --){

		int n,m;
		cin >> n >> m;

		vector<vector<int> > matrix(n,vector<int> (m));

		for(int i = 0 ; i < n ; i ++)
			for(int j = 0 ; j < m ; j ++)
				cin >> matrix[i][j];

		cout << findMaxOnesMatrixSize(matrix) << endl;
	
	}

}

Complexity

For a matrix of order m * n, Let c = min(m,n). Then the overall complexity of naive solution will be O(c3mn).

Dynamic Programming Implementation

Let’s make some observations about this problem before delving right into implementation details. Consider a square sub matrix of order n. Then we can consider this sub matrix as a combination of three square sub matrices of order n – 1 and a single cell, As shown in figure below –

Breakdown of sub matrix into smaller sub matrices

Now if all these three sub matrices of order n – 1 and the single cell are filled with 1’s, Then the bigger square sub matrix of order n will also be filled with 1’s. Let’s consider that dp[i][j] represents the maximum size of sub matrix with all 1’s ending at cell (i,j). Then from the above discussion it becomes pretty much intuitive that if, the (i,j) cell contains 1 then,

dp[i][j] = 1 + min(dp[i - 1][j],d[i][j - 1],dp[i - 1][j - 1])

So our overall recurrence relation looks somewhat like this –

            0                                                       matrix[i][j] = 0
dp[i][j] =  
            1 + min(dp[i - 1][j],d[i][j - 1],dp[i - 1][j - 1])      matrix[i][j] = 1

Now, with the recurrence relation in our hand all we need to do is to create a dp matrix of size m * n (Same as the order of given matrix). We will then start iterating from first column of first row and will fill the dp matrix according to the recurrence relation established above. Finally we will again iterate over the dp matrix to find the max value present in the matrix. A much more efficient solution will be to compute the max value right at the time of filling dp matrix.

Code

The above discussion becomes more clear with the code below –

#include <bits/stdc++.h>
using namespace std;

int findMaxOnesMatrixSize(vector<vector<int> > &matrix){

	int n = matrix.size();
	int m = matrix[0].size();

	// Initializing dp matrix with 0 ........
	vector<vector<int> > dp(n, vector<int>(m,0));
	int maxOnesMatrixSize = 0;

	for(int i = 0 ; i < n ; i ++){

		for(int j = 0 ; j < m ; j ++){

			if(matrix[i][j] == 0){

				// If the current block has zero no need to do any computation ...........
				continue;

			}

			int upperMatrixSize = 0, diagonalMatrixSize = 0, sideMatrixSize = 0;

			if(i > 0){

				// Updating upper matrix size ............
				upperMatrixSize = dp[i - 1][j];

			}

			if(j > 0){

				// Updating side matrix size ............
				sideMatrixSize = dp[i][j - 1];

			}

			if(i > 0 && j > 0){

				// Updating diagonal matrix size ...........
				diagonalMatrixSize = dp[i - 1][j - 1];

			}

			dp[i][j] = 1 + min(diagonalMatrixSize,min(upperMatrixSize,sideMatrixSize));
			maxOnesMatrixSize = max(maxOnesMatrixSize,dp[i][j]);

		}

	}

	return maxOnesMatrixSize;

}

// Driver function ...........
int main(){

	int n,m;
	cin >> n >> m;

	vector<vector<int> > matrix(n,vector<int> (m));

	for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < m ; j ++)
			cin >> matrix[i][j];

	cout << findMaxOnesMatrixSize(matrix) << endl;

}

Complexity

In the dynamic programming implementation we iterate m * n times to fill dp matrix. Hence the overall complexity of this solution is O(m*n).

This Article is Published by Abhey Rana.
If you want to be content writer with Gohired.in Please write at career@gohired.in or admin@gohired.in

Similar Articles

Filed Under: Algorithm, Amazon Interview Question, Flipkart Interview Questions, Microsoft Interview Questions Tagged With: Dynamic Programming

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Python String and numbers

SAP Off Campus Hiring_ March 2015 Verbal Skills

Implement LRU Cache

Doubly linked list

Sequence Finder Dynamic Programming

SAP Interview Questions

Binary Tree in Java

Printing Longest Common Subsequence

Number of Islands BFS/DFS

Maximum sum contiguous subarray of an Array

How Radix sort works

Count number of ways to reach a given score in a game

LeetCode: Container With Most Water

Print all nodes that are at distance k from a leaf node

The Magic HackerEarth Nirvana solutions Hiring Challenge

Given a float number convert it into the string WITHOUT using any inbuilt Function

Binary Tree Isomorphic to each other

Facebook Interview Question : Interleave List

The greedy coins game Dynamic Programming

Max Sum in circularly situated Values

Find if a binary tree is height balanced ?

Flipkart SDET Interview Experience

Circular Linked List

Leetcode: Merge Intervals

Right view of Binary tree

VMWare Openings

Find if two rectangles overlap

Implement a generic binary search algorithm for Integer Double String etc

Maximum occurred Smallest integer in n ranges

Regular Expression Matching

Copyright © 2025 · Genesis Framework · WordPress · Log in