LeetCode 85 | Maximal Rectangle | Java | Hard | Monotonic Stack & Histogram Reduction | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 85 — Maximal Rectangle using Array, Matrix, and Monotonic Stack in Java.
Given a binary matrix filled with 0s and 1s, the challenge is to determine the area of the largest rectangle composed solely of 1s. This classic problem can be reduced into multiple subproblems of LeetCode 84 (Largest Rectangle in Histogram). By scanning the matrix row by row and maintaining continuous vertical counts of 1s as histogram heights, we transform 2D matrix exploration into a series of 1D histogram area evaluations.
For every row, we update our column heights array: if an element is 1, its height increments; if 0, it resets to 0. We then process the resulting heights array with a monotonic increasing stack in linear time. The stack stores indices of bars in increasing order of height, resolving the left and right boundaries of every potential rectangle on the fly. This yields an optimal O(M * N) time complexity with O(N) auxiliary space.
🔥 Problem Highlights
✅ Row-wise reduction of 2D binary matrix to 1D Largest Rectangle in Histogram
✅ Dynamic histogram height tracking with reset on encountering 0
✅ Monotonic increasing stack implementation for O(N) histogram evaluation
✅ Graceful handling of edge cases including single-cell and all-zero matrices
✅ Full optimal code provided across Java, Python, C++, and JavaScript
✅ Optimal O(M * N) time complexity and O(N) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
00:55 Problem Understanding
01:48 Observation & Histogram Conversion
02:46 Monotonic Stack Approach
03:47 Java Code Walkthrough
05:02 Test Cases & Edge Cases Walkthrough
06:08 Time Complexity Analysis
06:50 Space Complexity Analysis
07:22 Summary & Outro
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/11-January/85-Maximal-Rectangle
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Monotonic Stack Patterns
Histogram Problems
Matrix Optimization Techniques
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does a cell with value '0' reset the histogram height for that column to 0 instead of keeping the previous height?
1️⃣ Because a rectangle cannot span across a '0' cell vertically
2️⃣ To reduce stack memory usage
3️⃣ Because 0 acts as a sentinel boundary for the stack
4️⃣ It prevents integer overflow during area calculations
#LeetCode85 #LeetCode #MaximalRectangle #Java #JavaDSA #MonotonicStack #Matrix #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 85 — Maximal Rectangle using Array, Matrix, and Monotonic Stack in Java.
Given a binary matrix filled with 0s and 1s, the challenge is to determine the area of the largest rectangle composed solely of 1s. This classic problem can be reduced into multiple subproblems of LeetCode 84 (Largest Rectangle in Histogram). By scanning the matrix row by row and maintaining continuous vertical counts of 1s as histogram heights, we transform 2D matrix exploration into a series of 1D histogram area evaluations.
For every row, we update our column heights array: if an element is 1, its height increments; if 0, it resets to 0. We then process the resulting heights array with a monotonic increasing stack in linear time. The stack stores indices of bars in increasing order of height, resolving the left and right boundaries of every potential rectangle on the fly. This yields an optimal O(M * N) time complexity with O(N) auxiliary space.
🔥 Problem Highlights
✅ Row-wise reduction of 2D binary matrix to 1D Largest Rectangle in Histogram
✅ Dynamic histogram height tracking with reset on encountering 0
✅ Monotonic increasing stack implementation for O(N) histogram evaluation
✅ Graceful handling of edge cases including single-cell and all-zero matrices
✅ Full optimal code provided across Java, Python, C++, and JavaScript
✅ Optimal O(M * N) time complexity and O(N) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
00:55 Problem Understanding
01:48 Observation & Histogram Conversion
02:46 Monotonic Stack Approach
03:47 Java Code Walkthrough
05:02 Test Cases & Edge Cases Walkthrough
06:08 Time Complexity Analysis
06:50 Space Complexity Analysis
07:22 Summary & Outro
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/11-January/85-Maximal-Rectangle
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/11-January/85-Maximal-Rectangle/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Monotonic Stack Patterns
Histogram Problems
Matrix Optimization Techniques
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does a cell with value '0' reset the histogram height for that column to 0 instead of keeping the previous height?
1️⃣ Because a rectangle cannot span across a '0' cell vertically
2️⃣ To reduce stack memory usage
3️⃣ Because 0 acts as a sentinel boundary for the stack
4️⃣ It prevents integer overflow during area calculations
#LeetCode85 #LeetCode #MaximalRectangle #Java #JavaDSA #MonotonicStack #Matrix #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description