Home » Interview coding problems/challenges

# Largest Square Sub Matrix of 1's in Given Binary Matrix

Given a N*M binary matrix find the size of largest square sub-matrix of 1's present in it.

Submitted by Divyansh Jaipuriyar, on September 03, 2020

**Problem statement:**

Given a *N*M* binary matrix find the size of largest square sub-matrix of 1's present in it.

**Problem description:**

They want you to find the size of the largest square matrix which have all its elements equal to 1, we need to notice that there are several rectangles which have all its elements equal to 1 but you need to find the square only no rectangle. A square matrix has an equal number of rows and columns.

**Input:**

The first line of input consist of *T* number of test cases. Each test case consist of size of *N* and *M*, each of the following *N* lines consist of *M* values either 1 or 0.

**Output:**

You need to print the largest square sub-matrix of 1 in separate lines.

**Examples:**

Input: T=1 N=3,M=3 0 1 1 0 1 1 0 1 1 Output: 2 Input: T=1 N=4,M=4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 Output: 2

**Solution Approach:**

**(a) Recursion Approach:**

We will use the logic that a square matrix can be formed only when its top-left, top and left matrix has size one less than the current square matrix, i.e. if we are using *(n*n)* size matrix then it must have *(n-1)*(n-1)* matrix in other three parts as discussed earlier.

We will use the recurrence relation: The size of the largest square submatrix ending at cell *(i,j)* is equal to 1 plus the minimum among the other three parts as *(i-1,j)*, *(i,j-1)* and *(i-1,j-1)*. The final maximum value will be the maximum among all such a square matrix.

if(current cell has 1) mat[i][j]=1+min(mat[i-1][j],mat[i][j-1],mat[i-1][j-1]) else mat[i][j]=0,which ends at here.

The maximum will be the maximum among all such *mat[i][j]*.

**Time complexity** for the above approach in the worst case is * exponential*.

**(b) Dynamic Programming Approach:**

In this approach we will see the bottom-up approach in which we will initialize our base cases as if there is no 1 in the matrix then the answer is 0 otherwise our answer will be 1 initially, then we iterate through all the matrix position and check if current position if the matrix contains 1 or not if 1 then we check the minimum value among the three other matrices before it and 1 to it. Then we check the maximum value among our max variable and matrix value.

**Time complexity** for the above case is in the worst case is: **O(N*M)**

**Space complexity** for the above case is in the worst case is: **O(N*M)**

**C++ Implementation (Recursion Approach):**

#include <bits/stdc++.h> using namespace std; typedef long long ll; //declare a matrix ll mat[1003][1003]; //declare solve function which will //take three parameters as n,m and res. ll solve(ll n, ll m, ll& res) { //base case when in first row //or in first column. if (n == 0 || m == 0) { //store maximum value in res. res = max(res, mat[n][m]); return mat[n][m]; } //largest square-sub matrix in left of //current position. ll l = solve(n, m - 1, res); //largest square-sub matrix in top-left //of current position. ll lt = solve(n - 1, m - 1, res); //largest square-sub matrix in top //of current position. ll up = solve(n - 1, m, res); //declare temporary variable ans. ll ans = 0; //check if current position has 1 or not //if it has 1 then it must be in the largest //square-sub matrix. if (mat[n][m] != 0) ans = 1 + min(min(l, lt), up); //store maximum value in res. res = max(res, ans); return ans; } int main() { ll t; cout << "Enter number of test cases: "; cin >> t; while (t--) { cout << "Enter size of matrix N and M: "; ll n, m; cin >> n >> m; cout << "Enter elements:\n"; for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) cin >> mat[i][j]; ll res = 0; solve(n - 1, m - 1, res); cout << "Largest size of sub-matrix: "; cout << res << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter size of matrix N and M: 4 4 Enter elements: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Largest size of sub-matrix: 4 Enter size of matrix N and M: 2 2 Enter elements: 1 1 0 0 Largest size of sub-matrix: 1 Enter size of matrix N and M: 4 4 Enter elements: 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 Largest size of sub-matrix: 2

**C++ Implementation (Dynamic Programming Approach):**

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll t; cout << "Enter number of test cases: "; cin >> t; while (t--) { cout << "Enter size of matrix N and M: "; ll n, m; cin >> n >> m; ll mat[n][m]; //initialize variable mv with 0. ll mv = 0; cout << "Enter elements:\n"; for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) { cin >> mat[i][j]; { if (mat[i][j]) mv = 1; } } cout << "Largest size of sub-matrix: "; //if there is no 1 then simply print 0. if (mv == 0) cout << 0 << "\n"; else { //iterate through all elements //of the matrix then check for other cases. for (ll i = 1; i < n; i++) { for (ll j = 1; j < m; j++) { //check if current position is 1 or not. if (mat[i][j]) { //check minimum among other 3 matrix. if (mat[i - 1][j] and mat[i][j - 1] and mat[i - 1][j - 1]) { mat[i][j] = 1 + min(min(mat[i - 1][j], mat[i][j - 1]), mat[i - 1][j - 1]); mv = max(mv, mat[i][j]); } } } } cout << mv << "\n"; } } return 0; }

**Output:**

Enter number of test cases: 3 Enter size of matrix N and M: 2 2 Enter elements: 1 0 0 1 Largest size of sub-matrix: 1 Enter size of matrix N and M: 2 2 Enter elements: 1 1 1 1 Largest size of sub-matrix: 2 Enter size of matrix N and M: 3 3 Enter elements: 0 1 1 0 1 1 0 1 1 Largest size of sub-matrix: 2

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.