How can I find the coordinates of the largest all-true rectangle in a 2d array of booleans in less than O(n^3)?

Question

Currently, I'm using this solution:

https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/

I convert true to 1 & false to -infinity, then find the greatest sum rectangle. According to the article, this solution is O(n^3), and it's really not fast enough for what I need. I've tried to use the Max Histogram method (https://www.youtube.com/watch?v=g8bSdXCG-lA), but the way the rectangle size is stored caused me some trouble with finding the ultimate coordinates.

Code in C# would be awesome, but I'm happy to take pseudocode & write it myself if needed.

Answer 1

Based on the link provided by the OP:

// C# program to find largest rectangle 
// with all 1s in a binary matrix 
using System; 
using System.Collections.Generic; 

class GFG { 
    // Finds the maximum area under the 
    // histogram represented by histogram. 
    // See below article for details. 
    // https:// www.geeksforgeeks.org/largest-rectangle-under-histogram/ 
    public static (int area, int left, int right) maxHist(int C, int[] row) 
    { 
        // Create an empty stack. The stack 
        // holds indexes of hist[] array. 
        // The bars stored in stack are always 
        // in increasing order of their heights. 
        Stack<int> result = new Stack<int>(); 

        int top_val; // Top of stack 
        int left; 

        int max_area = 0; // Initialize max area in current row (or histogram) 
        int max_left = -1;
        int max_right = -1;
    
        int area = 0; // Initialize area with current top 

        // Run through all bars of 
        // given histogram (or row) 
        int i = 0; 
        while (i < C) { 
            // If this bar is higher than the 
            // bar on top stack, push it to stack 
            if (result.Count == 0 || row[result.Peek()] <= row[i]) { 
                result.Push(i++); 
            } 
            else { 
                // If this bar is lower than top 
                // of stack, then calculate area of 
                // rectangle with stack top as 
                // the smallest (or minimum height) 
                // bar. 'i' is 'right index' for 
                // the top and element before 
                // top in stack is 'left index' 
                left = result.Peek();
                top_val = row[left]; 
                result.Pop(); 
                area = top_val * i; 

                if (result.Count > 0) {
                    left = result.Peek() + 1;
                    area = top_val * (i - left); 
                }

                if (area > max_area) {
                    max_area = area;
                    max_left = left;
                    max_right = i - 1;
                }
            } 
        } 

        // Now pop the remaining bars from 
        // stack and calculate area with 
        // every popped bar as the smallest bar 
        while (result.Count > 0) {
            left = result.Peek();
            top_val = row[left]; 
            result.Pop(); 
            area = top_val * i; 
            if (result.Count > 0) { 
                left = result.Peek() + 1;
                area = top_val * (i - left); 
            } 

            if (area > max_area) {
                max_area = area;
                max_left = left;
                max_right = C - 1;
            }
        } 
        return (max_area, max_left, max_right); 
    } 

    // Returns area of the largest 
    // rectangle with all 1s in A[][] 
    public static (int area, int top, int bottom, int left, int right)
        maxRectangle(int R, int C, int[][] A) 
    { 
        int top = 0;
        int bottom = 0;

        // Calculate area for first row 
        // and initialize it as result 
        (int result, int left, int right) = maxHist(C, A[0]); 

        // iterate over row to find 
        // maximum rectangular area 
        // considering each row as histogram 
        for (int i = 1; i < R; i++) { 
            for (int j = 0; j < C; j++) { 

                // if A[i][j] is 1 then 
                // add A[i -1][j] 
                if (A[i][j] == 1) { 
                    A[i][j] += A[i - 1][j]; 
                } 
            } 

            (int tmp_result, int tmp_left, int tmp_right) = maxHist(C, A[i]);
            // Update result if area with current 
            // row (as last row of rectangle) is more
            if (tmp_result > result) {
                left = tmp_left;
                right = tmp_right;
                bottom = i;
                result = tmp_result;
                top = bottom - (result / (right - left + 1)) + 1;
            }
        } 

        return (result, top, bottom, left, right); 
    } 

    // Driver code 
    public static void Main(string[] args) 
    { 
        int R = 4; 
        int C = 4; 

        int[][] A = new int[][] { 
            new int[] { 0, 1, 1, 0 }, 
            new int[] { 1, 1, 1, 1 }, 
            new int[] { 1, 1, 1, 1 }, 
            new int[] { 1, 1, 0, 0 } 
        }; 
        var result = maxRectangle(R, C, A);
        Console.Write("Area of maximum rectangle is " + result.area + 
            ", rows " + result.top + "-" + result.bottom + 
            ", columns " + result.left + "-" + result.right); 
    } 
}