C++ | Easiest Solution | Basic Maths | Commented Code for Understanding
\n\n\n# IF YOU WANT ANOTHER MORE OPTIMIZED SOLUTION, YOU CAN CHECK THIS SOLUTION OUT: \nIt is 100% Faster using Stacks:\nhttps://leetcode.com/problems/maximal-r
\n![Zombie Upvote.png](https://assets.leetcode.com/users/images/4fd59279-f4a6-490b-8864-7a8ec0745feb_1712980788.0234125.png)\n\n# IF YOU WANT ANOTHER MORE OPTIMIZED SOLUTION, YOU CAN CHECK THIS SOLUTION OUT: \nIt is 100% Faster using Stacks:\nhttps://leetcode.com/problems/maximal-rectangle/solutions/5014969/c-100-faster-easy-stacks-basic-maths-easy-step-by-step-explanation/\n\n# THIS IS NOT THE MOST EFFECIENT SOLUTION, BUT IS THE EASIEST POSSIBLE CODE\n\n# THE BASIC IDEA IS TO CALCULATE THE LARGEST RECTANGLE FOR HISTOGRAM\nYOU CAN REFER TO STRIVER YT VIDEO FOR LARGEST RECTANGLE FOR HISTOGRAM : https://youtu.be/X0X6G-eWgQ8?si=cCUSmjz96Dx9lkGk\n\n# AFTER THIS CREATE ROW-WISE HISTOGRAM AND THEN FIND THE LARGEST RECTANGLE FOR EACH OF THEM AND RETURN THE LARGEST RECTANGLE AREA AS THE ANSWER\n\n# REFER TO CODE FOR COMMENTS AND EXPLANATION LINE BY LINE\n\n# Intuition\nThe problem asks us to find the rectangle with the largest area that consists entirely of 1s in a binary matrix. Here\'s an intuitive approach:\n\n1. **Think horizontally:** For each row, imagine stacking 1s vertically. We can treat this as a histogram where the height of each bar represents the number of consecutive 1s in the current row.\n2. **Find maximal area in a histogram:** We know efficient algorithms (like the stack-based approach) to find the largest rectangle within a histogram.\n\n# Approach\n1. **Build row-wise histograms:** Iterate through the matrix. For each row, create a new histogram array to keep track of the number of consecutive 1s encountered so far for each column. If a 0 is encountered, reset the count to 0.\n2. **Process each histogram:** For each row\'s histogram, apply the findLargestAreaInHistogram function to determine the maximum rectangle area that can be formed using the heights in that row.\n3. **Track global maximum:** Maintain a variable area to keep track of the largest rectangle area found so far across all rows. Update area with the maximum area calculated for each row\'s histogram.\n\n# Complexity\n- Time complexity: **O(n*m)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(m)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int findLargestAreaInHistogram(int n, vector<int>& rowHistogram) {\n        int area = 0;\n        for (int i = 0; i < n; i++) {\n            int breadth = 1;\n            // first find only this area\n            area = max(area, rowHistogram[i] * breadth);\n            // now start checking for other lengths as well\n            // as we might need other heights for more area\n\n            // first check for heights behind it\n            for (int j = i - 1; j >= 0; j--) {\n                if (rowHistogram[j] >= rowHistogram[i]) {\n                    breadth++;\n                } else {\n                    break;\n                }\n            }\n\n            // now check for heights after it\n            for (int j = i + 1; j < n; j++) {\n                if (rowHistogram[j] >= rowHistogram[i]) {\n                    breadth++;\n                } else {\n                    break;\n                }\n            }\n\n            // now compute the area\n            area = max(area, rowHistogram[i] * breadth);\n        }\n        return area;\n    }\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int n = matrix.size();\n        int m = matrix[0].size();\n        int area = 0;\n        // first make the histogram row wise\n        vector<int> rowHistogram(m, 0);\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; ++j) {\n                if (matrix[i][j] == \'1\') {\n                    rowHistogram[j]++;\n                } else {\n                    rowHistogram[j] = 0;\n                }\n            }\n            // now I have created the histogram for the particular level\n            // now find the largest area in that level\n            area = max(area, findLargestAreaInHistogram(m, rowHistogram));\n        }\n        return area;\n    }\n};\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Array', 'Matrix', 'C++']