Fully Explained C++ solution using largest rectangle in histogram problem
Similar to Problem No.84 \n# Intuition\nTo solve this problem, we can utilize the concept of histograms and the largest rectangle in histogram problem. We\'ll t
Similar to Problem No.84 \n# Intuition\nTo solve this problem, we can utilize the concept of histograms and the largest rectangle in histogram problem. We\'ll treat each row of the matrix as the base of a histogram, where the height of each bar represents the number of consecutive \'1\'s in the corresponding column. Then, we\'ll find the largest rectangle in each histogram and return the maximum area.\n\n# Approach\n1. Define a helper function `largestRectangle()` that calculates the largest rectangle in a histogram represented by a vector of heights.\n2. Define two helper functions `nextsmaller()` and `prevsmaller()` that find the indices of the next smaller and previous smaller elements for each element in a vector.\n3. Iterate through each row of the matrix.\n4. For each row, update the heights vector to represent the histogram.\n5. Calculate the largest rectangle in the histogram using the `largestRectangle()` function and update the maximum area.\n6. Return the maximum area.\n\n# Complexity\n- Time complexity: \n  - For each row, we perform operations to update the heights vector and find the largest rectangle in the histogram, both of which take O(m) time, where m is the number of columns. Therefore, the overall time complexity is O(n * m), where n is the number of rows and m is the number of columns.\n- Space complexity:\n  - We use additional space to store vectors for heights, next smaller indices, and previous smaller indices, each of size m (the number of columns). Therefore, the space complexity is O(m).\n\n# Code\n```cpp\nclass Solution {\npublic:\n    vector<int> nextsmaller(vector<int>&v , int n){\n        vector<int>ans(n,n);\n        stack<int>st;\n        for(int i=n-1;i>=0;i--){\n            while(!st.empty() && v[st.top()]>=v[i]){\n                st.pop();\n            }\n            if(!st.empty()) ans[i]=st.top();\n            st.push(i);\n        }\n        return ans;\n    }\n\n    vector<int> prevsmaller(vector<int>&v , int n){\n        vector<int>ans(n,-1);\n        stack<int>st;\n        for(int i=0;i<n;i++){\n            while(!st.empty() && v[st.top()]>=v[i]){\n                st.pop();\n            }\n            if(!st.empty()) ans[i]=st.top();\n            st.push(i);\n        }\n        return ans;\n    }\n\n    int largestRectangle(vector<int>& heights) {\n        int n = heights.size();\n        int ans = 0;\n        vector<int> next(n), prev(n);\n        next = nextsmaller(heights, n);\n        prev = prevsmaller(heights, n);\n        for(int i=0;i<n;i++){\n            int l = heights[i];\n            int b = next[i] - prev[i] - 1;\n            int area = l * b;\n            ans = max(ans, area);\n        }\n        return ans;\n    }\n\n    int maximalRectangle(vector<vector<char>>& mat) {\n        int n = mat.size();\n        int m = mat[0].size();\n        vector<int> h(m,0);\n        int ans = 0;\n        for(int i=0;i<n;i++){\n            vector<int> he;\n            for(int j=0;j<m;j++){\n                if(mat[i][j]==\'1\') he.push_back(1 + h[j]);\n                else he.push_back(0);\n            }\n            ans = max(ans, largestRectangle(he));\n            h = he;\n        }\n        return ans;\n    }\n};\n```\n\nThis code efficiently calculates the area of the largest rectangle in a binary matrix by treating each row as a histogram and finding the largest rectangle in each histogram. The time complexity is proportional to the number of rows times the number of columns, making it an efficient solution for large matrices.
['Stack', 'Matrix', 'C++']