Maximal Rectangle | LeetCode 85 | Optimal Stack + Histogram Approach | Explained

Problem: LeetCode 85 - Maximal Rectangle

Code:
https://leetcode.com/problems/maximal-rectangle/solutions/7484811/easy-solution-histogram-type-problem-com-4dwm

Upsolve Leetcode Contest:
https://youtube.com/playlist?list=PLsLlEdtakGoxoGbAwVRSlRjuB1yv1ycnc&si=_IDShX4wq0BxIkNf

Greedy & Heaps:
https://youtube.com/playlist?list=PLsLlEdtakGozAWFrLtFyKfzHL69QMdpkK&si=05iZsUB_hCmYZGPN

Two pointers:
https://youtube.com/playlist?list=PLsLlEdtakGow7Brk6c1OM_Bh-Mz55V7nX&si=hwShAQg6AT_VlwOm

Sliding Window:
https://youtube.com/playlist?list=PLsLlEdtakGozlKx_L-5PQJO-ua_maQb6R&si=hNoGQVZUI7OR9poU

Maths & Geometry:
https://youtube.com/playlist?list=PLsLlEdtakGoyWTBlOMC_mQ8Pv1M_pY2MX&si=MHwHo53uuirf26zC

Stack:
https://youtube.com/playlist?list=PLsLlEdtakGowhIcIi8uvWRy7Zw-bKoD85&si=9jvT_g2NQHFUHAMg

Set & Map:
https://youtube.com/playlist?list=PLsLlEdtakGozffR58V-u_qpYkwkR2Nc_F&si=_h2GBLEVi-hQyvI-

Bit manipulation:
https://youtube.com/playlist?list=PLsLlEdtakGowS_aAEQDNtNJA9zWkyk5uf&si=f0yO3hkGsorAhiod

Backtracking:
https://youtube.com/playlist?list=PLsLlEdtakGox7HMCBg3_sh8TrZoKnTPep&si=CMvDSFGzMRg6io1Y

Linked List:
https://youtube.com/playlist?list=PLsLlEdtakGowLdcT3ocFdt5MCEuTYVOzF&si=16QNR2HY_bLvVw2n

Binary Search:
https://youtube.com/playlist?list=PLsLlEdtakGozNxx5rfRgEW-1DYseLnDbV&si=RZ1BUYmSAvIvi5a5

Graph:
https://youtube.com/playlist?list=PLsLlEdtakGox1mdnH0PrJUhHJByUstkvx&si=JW-6qPw7zXDH-29j

Dynamic Progamming:
https://youtube.com/playlist?list=PLsLlEdtakGoyNROP7uWS9OLLHs9_JluVM&si=vJY6SxVXIHAbgzgk

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

------------------------------------
Approach:

We treat each row as the base of a histogram.

For every row:
1. Maintain a height[] array where height[j] represents the number of continuous '1's above (including current row) in column j.
2. If matrix[i][j] == '1', height[j]++, else height[j] = 0.
3. After updating height[], compute the largest rectangle area in histogram using a monotonic increasing stack (same as LeetCode 84).
4. Track the maximum area over all rows.

This converts the 2D problem into multiple 1D Largest Rectangle in Histogram problems.

------------------------------------
Time Complexity:
O(R * C)

R = number of rows
C = number of columns

Each row is processed once and histogram is solved in O(C).

------------------------------------
Space Complexity:
O(C) for height array and stack.

-----------------------------------
#leetcode #leetcode85 #maximalrectangle #stack #monotonicstack #histogram #largestrectangleinhistogram #arrays #matrix #binarymatrix #dsa #datastructures #algorithms #codinginterview #codingpractice #java #python #cpp #placements #faang #techinterview #competitiveprogramming #computerscience #programming #interviewpreparation #codinglife #softwareengineer

Видео Maximal Rectangle | LeetCode 85 | Optimal Stack + Histogram Approach | Explained канала Study Placement