Given a binary matrix mat[][] of size N*M, find the maximum size rectangle binary-sub-matrix with all 1’s.
Examples:
Input: mat[][] = { {0, 1, 1, 0},
{1, 1, 1, 1},
{1, 1, 1, 1},
{1, 1, 0, 0} }
Output: 8
Explanation: The largest rectangle formed with only 1s is either: (0, 1) to (2, 2) or (1, 1) to (2, 3) which is
1 1 1 1
1 1 1 1Input: mat[][] = { {0, 1, 1},
{1, 1, 1},
{0, 1, 1} }
Output: 6
Explanation: The largest rectangle with only 1’s is from (0, 1) to (2, 2) which is
1 1
1 1
1 1
Approach: This approach uses the concept of Largest Rectangular Area in Histogram. But the approach to get the maximum area for each row will be different than Set-1.
- Consider each row as the base of the histogram chart formed with all 1s.
- For each row, increase height of a bar by the amount of the previous row, only if the value in current row is 1 and calculate the largest rectangular area of that histogram.
- The largest rectangular area of a histogram among all possible base rows is the required are of the rectangle.
Illustration:
Consider the matrix:
mat[][] = 0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0Calculate maxarea for the first row mat[0]
=> height row[0] = 0 1 1 0.
=> area = height* breadth = 1 * 2 = 2Calculate maxarea for the first row mat[1]
=> update height of mat[1] with mat[0] i.e., mat[1][i] = mat[0][i] + 1 if mat[1][i] = 1, else 0
=> height row[1] = 1 2 2 1.
=> area = height* breadth = 2 * 2 = 4Calculate maxarea for the first row mat[2]
=> update height of mat[2] with mat[1]. i.e., mat[2][i] = mat[1][i] + 1 if mat[2][i] = 1, else 0.
=> height row[2] = 2 3 3 2.
=> area = height* breadth = 2 * 4 = 8 (nextsmaller index of mat[2][0] = 4, and previous smaller index = 0. area = 2*(4 – 0))Calculate maxarea for the first row mat[3]
=> update height of mat[3] with mat[2]. i.e., mat[3][i] = mat[2][i] + 1 if mat[3][i] = 1, else 0.
=> height row[3] = 3 4 0 0.
=> area = height* breadth = 3 * 2 = 6 (nextsmaller index of mat[3][0] = 2, and previous smaller index = 0. area = 3*(2 – 0))
=> here 3 4 0 0 is due to the reason that when mat[i][j] = 0 then don’t add previous heights into it.Thus maxarea = max of(2, 4, 8, 6) = 8.
This approach can be broken into two parts:
- Calculate heights of histogram for each row as base.
- Run a loop to traverse through the rows.
- Now If the current row is not the first row then update the height for that cell as follows,
- If mat[i][j] is not zero then matrix[i][j] = matrix[i-1][j] + matrix[i][j].
- Else mat[i][j] = 0.
- Calculate largest rectangular area in histogram of 1s for each row as base.
- First calculate the heights for each row as base as mentioned above.
- Create two arrays nextSmallereElemen[] and previouSmallerElement[] to store the indices of previous smaller elements and next smaller elements respectively. Refer to this article to find the previous and next smaller element.
- Now for every element, calculate area by taking this jth element as the smallest in the range nextSmallereElemen[j] and previouSmallerElement[j] and multiplying it with the difference of nextSmallereElemen[j] and previouSmallerElement[j].
- So, height will be the jth element in the given input array. And breadth will be, breadth = nextSmallereElemen[j] – previouSmallerElement[j].
- Finally, find the maximum of all the areas to get the desired maximum area.
- Find the maximum areas among all the rows, and that will be the required area of the rectangle.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find next smaller elementvector<int> nextsmallerelement(vector<int>& arr, int n){ stack<int> st; // For the elements which dont have // next smaller element ans will be -1 st.push(-1); // Store indices in output vector<int> right(n); // Start from last index for (int i = n - 1; i >= 0; i--) { // If top element is sorted then // no need to do anything, just store // the answer and push the // current element in stack if ((st.top() != -1) && arr[st.top()] < arr[i]) { right[i] = st.top(); st.push(i); } else { while ((st.top() != -1) && arr[st.top()] >= arr[i]) { st.pop(); } right[i] = st.top(); st.push(i); } } return right;}// Function to find previous smaller elementvector<int> previousmallerelement(vector<int>& arr, int n){ stack<int> st; st.push(-1); vector<int> left(n); // Start from first index for (int i = 0; i < n; i++) { if ((st.top() != -1) && arr[st.top()] < arr[i]) { left[i] = st.top(); st.push(i); } else { while ((st.top() != -1) && arr[st.top()] >= arr[i]) { st.pop(); } left[i] = st.top(); st.push(i); } } return left;}// Function to get the maximum area// considering each row as the histogram baseint getMaxArea(vector<int>& arr, int n){ vector<int> right(n); right = nextsmallerelement(arr, n); // Find the smallest element than // curr element in right side vector<int> left(n); left = previousmallerelement(arr, n); // Find the smallest element // than curr element in left side int maxarea = INT_MIN; // Now the left and right vector have // index of smallest element in left and // right respectively, thus the difference // of right - left - 1 will give us // breadth and thus // area = height(curr==arr[i]) * breadth; for (int i = 0; i < n; i++) { int height = arr[i]; if (right[i] == -1) { right[i] = n; } int breadth = right[i] - left[i] - 1; maxarea = max(maxarea, height * breadth); } return maxarea;}// Function to calculate// the maximum area of rectangleint maxRectangleArea(vector<vector<int> >& M, int n, int m){ // Calculate maxarea for first row int area = getMaxArea(M[0], m); int maxarea = area; for (int i = 1; i < n; i++) { for (int j = 0; j < m; j++) { if (M[i][j] != 0) { // Add heights of previous rows // into current M[i][j] = M[i][j] + M[i - 1][j]; } else { // If current height is 0 then // don't add previous heights M[i][j] = 0; } } maxarea = max(maxarea, getMaxArea(M[i], m)); } return maxarea;}// Driver codeint main(){ int N = 4, M = 4; vector<vector<int> > amt = { { 0, 1, 1, 0 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 0, 0 }, }; cout << maxRectangleArea(amt, N, M); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG{ public static int[] nextsmallerelement(int[] arr, int n) { Stack<Integer> st = new Stack<>(); // For the elements which dont have // next smaller element ans will be -1 st.push(-1); // Store indices in output int[] right = new int[n]; // Start from last index for (int i = n - 1; i >= 0; i--) { // If top element is sorted then // no need to do anything, just store // the answer and push the // current element in stack if ((st.peek() != -1) && arr[st.peek()] < arr[i]) { right[i] = st.peek(); st.push(i); } else { while ((st.peek() != -1) && arr[st.peek()] >= arr[i]) { st.pop(); } right[i] = st.peek(); st.push(i); } } return right; } public static int[] previousmallerelement(int arr[],int n) { Stack<Integer> st = new Stack<>(); st.push(-1); int[] left = new int[n]; // Start from first index - Difference Between Next and Previous Smaller element for (int i = 0; i < n; i++) { if ((st.peek() != -1) && arr[st.peek()] < arr[i]) { left[i] = st.peek(); st.push(i); } else { while ((st.peek() != -1) && arr[st.peek()] >= arr[i]) { st.pop(); } left[i] = st.peek(); st.push(i); } } return left; } public static int getMaxArea(int [] arr, int n) { int [] right = new int [n]; right = nextsmallerelement(arr, n); // Find the smallest element than // curr element in right side int [] left = new int [n]; left = previousmallerelement(arr, n); // Find the smallest element // than curr element in left side int maxarea = Integer.MIN_VALUE; // Now the left and right array have // index of smallest element in left and // right respectively, thus the difference // of right - left - 1 will give us // breadth and thus // area = height(curr==arr[i]) * breadth; for (int i = 0; i < n; i++) { int height = arr[i]; if (right[i] == -1) { right[i] = n; } int breadth = right[i] - left[i] - 1; maxarea = Math.max(maxarea, height * breadth); } return maxarea; } public static int maxRectangleArea(int [][] M, int R, int C) { int area = getMaxArea(M[0], R); int maxarea = area; for (int i = 1; i < R; i++) { for (int j = 0; j < C; j++) { if (M[i][j] != 0) { // Add heights of previous rows // into current M[i][j] = M[i][j] + M[i - 1][j]; } else { // If current height is 0 then // don't add previous heights M[i][j] = 0; } } maxarea = Math.max(maxarea, getMaxArea(M[i], R)); } return maxarea; } // Driver code public static void main(String[] args) { // Given array int R = 4, C = 4; int [][]amt = { { 0, 1, 1, 0 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 0, 0 }, }; System.out.println(maxRectangleArea(amt, R, C)); }}// This code is contributed by rupeshsk30. |
Python3
# Python code for the above approach:INT_MIN = -2147483647 - 1# Function to find next smaller elementdef nextsmallerelement(arr, n): st = [] # For the elements which dont have # next smaller element ans will be -1 st.append(-1) # Store indices in output right = [0 for i in range(n)] # Start from last index for i in range(n-1,-1,-1):# If top element is sorted then# no need to do anything, just store# the answer and append the# current element in stack if ((st[- 1] != -1) and arr[st[- 1]] < arr[i]): right[i] = st[- 1] st.append(i) else: while ((st[- 1] != -1) and arr[st[- 1]] >= arr[i]): st.pop() right[i] = st[- 1] st.append(i) return right# Function to find previous smaller elementdef previousmallerelement(arr, n): st = [] st.append(-1) left = [0 for i in range(n)] # Start from first index for i in range(n): if((st[- 1] != -1) and arr[st[- 1]] < arr[i]): left[i] = st[- 1] st.append(i) else: while ((st[- 1] != -1) and arr[st[- 1]]>= arr[i]): st.pop() left[i] = st[- 1] st.append(i) return left# Function to get the maximum area# considering each row as the histogram basedef getMaxArea(arr, n): right = [0 for i in range(n)] right = nextsmallerelement(arr, n) # Find the smallest element than # curr element in right side left = [0 for i in range(n)] left = previousmallerelement(arr, n) # Find the smallest element # than curr element in left side maxarea = INT_MIN # Now the left and right vector have # index of smallest element in left and # right respectively, thus the difference # of right - left - 1 will give us # breadth and thus # area = height(curr==arr[i]) * breadth for i in range(n): height = arr[i] if (right[i] == -1): right[i] = n breadth = right[i] - left[i] - 1 maxarea = max(maxarea,height * breadth) return maxarea# Function to calculate# the maximum area of rectangledef maxRectangleArea(M, n, m): # Calculate maxarea for first row area = getMaxArea(M[0], m) maxarea = area for i in range(1,n): for j in range(m): if (M[i][j] != 0): # Add heights of previous rows into current M[i][j] = M[i][j] + M[i - 1][j] else: # If current height is 0 then # don't add previous heights M[i][j] = 0 maxarea = max(maxarea,getMaxArea(M[i], m)) return maxarea# Driver codeN,M = 4,4amt = [ [0, 1, 1, 0],[1, 1, 1, 1],[1, 1, 1, 1],[1, 1, 0, 0]]print(maxRectangleArea(amt, N, M))# This code is contributed by shinjanpatra |
C#
// C# code for the above approach:using System;using System.Collections;using System.Collections.Generic;public class GFG { public static int[] NextSmallerElement(int[, ] M, int R, int rowIndex) { Stack<int> st = new Stack<int>(); // For the elements which dont have // next smaller element ans will be -1 st.Push(-1); // Store indices in output int[] right = new int[R]; // Start from last index for (int i = R - 1; i >= 0; i--) { // If top element is sorted then // no need to do anything, just store // the answer and push the // current element in stack if ((st.Peek() != -1) && M[rowIndex, st.Peek()] < M[rowIndex, i]) { right[i] = st.Peek(); st.Push(i); } else { while ((st.Peek() != -1) && M[rowIndex, st.Peek()] >= M[rowIndex, i]) { st.Pop(); } right[i] = st.Peek(); st.Push(i); } } return right; } public static int[] PreviousSmallerElement(int[, ] M, int R, int rowIndex) { Stack<int> st = new Stack<int>(); st.Push(-1); int[] left = new int[R]; // Start from first index - Difference Between Next // and Previous Smaller element for (int i = 0; i < R; i++) { if ((st.Peek() != -1) && M[rowIndex, st.Peek()] < M[rowIndex, i]) { left[i] = st.Peek(); st.Push(i); } else { while ((st.Peek() != -1) && M[rowIndex, st.Peek()] >= M[rowIndex, i]) { st.Pop(); } left[i] = st.Peek(); st.Push(i); } } return left; } public static int GetMaxArea(int[, ] M, int R, int rowIndex) { int[] right = NextSmallerElement(M, R, rowIndex); // Find the smallest element than // curr element in right side int[] left = PreviousSmallerElement(M, R, rowIndex); // Find the smallest element // than curr element in left side int maxarea = int.MinValue; // Now the left and right array have // index of smallest element in left and // right respectively, thus the difference // of right - left - 1 will give us // breadth and thus // area = height(curr==arr[i]) * breadth; for (int i = 0; i < R; i++) { int height = M[rowIndex, i]; if (right[i] == -1) { right[i] = R; } int breadth = right[i] - left[i] - 1; maxarea = Math.Max(maxarea, height * breadth); } return maxarea; } public static int MaxRectangleArea(int[, ] M, int R, int C) { int area = GetMaxArea(M, R, 0); int maxarea = area; for (int i = 1; i < R; i++) { for (int j = 0; j < C; j++) { if (M[i, j] != 0) { // Add heights of previous rows // into current M[i, j] = M[i, j] + M[i - 1, j]; } else { // If current height is 0 then // don't add previous heights M[i, j] = 0; } } maxarea = Math.Max(maxarea, GetMaxArea(M, R, i)); } return maxarea; } static public void Main() { // Code int[, ] amt = { { 0, 1, 1, 0 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 0, 0 }, }; int R = 4, C = 4; Console.WriteLine(MaxRectangleArea(amt, R, C)); }}// This code is contributed by lokeshmvs21. |
Javascript
<script> // JavaScript code for the above approach: const INT_MIN = -2147483647 - 1; // Function to find next smaller element const nextsmallerelement = (arr, n) => { let st = []; // For the elements which dont have // next smaller element ans will be -1 st.push(-1); // Store indices in output let right = new Array(n).fill(0); // Start from last index for (let i = n - 1; i >= 0; i--) { // If top element is sorted then // no need to do anything, just store // the answer and push the // current element in stack if ((st[st.length - 1] != -1) && arr[st[st.length - 1]] < arr[i]) { right[i] = st[st.length - 1]; st.push(i); } else { while ((st[st.length - 1] != -1) && arr[st[st.length - 1]] >= arr[i]) { st.pop(); } right[i] = st[st.length - 1]; st.push(i); } } return right; } // Function to find previous smaller element const previousmallerelement = (arr, n) => { let st = []; st.push(-1); let left = new Array(n).fill(0); // Start from first index for (let i = 0; i < n; i++) { if ((st[st.length - 1] != -1) && arr[st[st.length - 1]] < arr[i]) { left[i] = st[st.length - 1]; st.push(i); } else { while ((st[st.length - 1] != -1) && arr[st[st.length - 1]] >= arr[i]) { st.pop(); } left[i] = st[st.length - 1]; st.push(i); } } return left; } // Function to get the maximum area // considering each row as the histogram base const getMaxArea = (arr, n) => { let right = new Array(n).fill(0); right = nextsmallerelement(arr, n); // Find the smallest element than // curr element in right side let left = new Array(n).fill(0); left = previousmallerelement(arr, n); // Find the smallest element // than curr element in left side let maxarea = INT_MIN; // Now the left and right vector have // index of smallest element in left and // right respectively, thus the difference // of right - left - 1 will give us // breadth and thus // area = height(curr==arr[i]) * breadth; for (let i = 0; i < n; i++) { let height = arr[i]; if (right[i] == -1) { right[i] = n; } let breadth = right[i] - left[i] - 1; maxarea = Math.max(maxarea, height * breadth); } return maxarea; } // Function to calculate // the maximum area of rectangle const maxRectangleArea = (M, n, m) => { // Calculate maxarea for first row let area = getMaxArea(M[0], m); let maxarea = area; for (let i = 1; i < n; i++) { for (let j = 0; j < m; j++) { if (M[i][j] != 0) { // Add heights of previous rows // into current M[i][j] = M[i][j] + M[i - 1][j]; } else { // If current height is 0 then // don't add previous heights M[i][j] = 0; } } maxarea = Math.max(maxarea, getMaxArea(M[i], m)); } return maxarea; } // Driver code let N = 4, M = 4; let amt = [ [0, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 0, 0], ]; document.write(maxRectangleArea(amt, N, M));// This code is contributed by rakeshsahni</script> |
Output
8
Time Complexity: O(N * M)
Auxiliary Space: O(M)
This Article is Contributed by Rupesh Kapse.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
