Maximal Rectangles
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Maximal Rectangles in a Binary Matrix, Matrices, Two-dimensional Array Traversal, Dynamic Programming, Arrays, Stack, Monotonic Stack, Time Complexity, Space Complexity, Optimization, matrix, dynamic programming, mathematical operations, frequency counting, divide and conquer, stack algorithms, Binary Matrix Problems, Largest Rectangle in Histogram, Data Structure Operations.
Problem Statement Given a rows x cols binary matrix matrix filled with '0's and '1's, find the largest rectangle containing only '1's and return its area. Input Specification The input consists of a binary matrix matrix represented as a list of strings, where each string represents a row and contains characters '0' or '1'. Output Specification Return an integer representing the area of the largest rectangle containing only '1's. Constraints 1 <= rows, cols <= 200 matrix[i][j] is '0' or '1'. Sample Test Cases Sample Input 1: Sample Output 1: Explanation 1: The maximal rectangle is formed by the '1's in the middle of the matrix, specifically: This forms a 2x3 rectangle, giving an area of 6.