Max rectangle

JavaView on GFG

Time: O(n*m)

Space: O(m)

Intuition

Build histograms row by row and apply "largest rectangle in histogram" for each row.

Algorithm

1Maintain heights[] array. For each row: update heights (increment if cell=1, reset to 0 if cell=0).
2For each row's heights, compute largest rectangle using stack-based approach.

Example Walkthrough

Input: [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]

1.Row 0 heights=[1,0,1,0,0]â†’area=1. Row 1=[2,0,2,1,1]â†’area=3. Row 2=[3,1,3,2,2]â†’area=6.

Output: 6

Common Pitfalls

•Use the histogram approach for each row. The largest rectangle in histogram uses a monotone stack.

Max rectangle.java

Java

// Approach: Compute histogram row by row. For each row apply largest rectangle in histogram (monotonic stack).
// Time: O(n*m) Space: O(m)
import java.util.*;

class Solution {
    static int maxArea(int mat[][]) {
        int h[] = new int[mat[0].length];

        int pse[] = new int[mat[0].length];
        int nse[] = new int[pse.length];

        int ans = 0;

        for (var a : mat) {
            for (int i = 0; i < h.length; i++)
                h[i] = a[i] == 1 ? h[i] + 1 : 0;

            PSE(h, pse);
            NSE(h, nse);

            for (int i = 0; i < h.length; i++) {
                if (h[i] == 0)
                    continue;
                ans = Math.max(ans, (nse[i] - pse[i] - 1) * h[i]);
            }
        }

        return ans;
    }

    static void PSE(int arr[], int pse[]) {
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (st.size() > 0 && arr[st.peek()] >= arr[i])
                st.pop();
            if (st.size() == 0)
                pse[i] = -1;
            else
                pse[i] = st.peek();
            st.push(i);
        }
    }

    static void NSE(int arr[], int nse[]) {
        Stack<Integer> st = new Stack<>();
        for (int i = arr.length - 1; i >= 0; i--) {
            while (st.size() > 0 && arr[st.peek()] >= arr[i])
                st.pop();
            if (st.size() == 0)
                nse[i] = arr.length;
            else
                nse[i] = st.peek();
            st.push(i);
        }
    }
}

Was this solution helpful?