Max rectangle

JavaView on GFG

Time: O(n*m)

Space: O(m)

Problem Overview

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

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?