🥷Beats 100% | Simple dynamic programming approach | No extra space 🔥
Intuition\n\nWhen approaching the problem of finding the largest submatrix of 1s in a matrix, the initial thought involves exploring a method to identify a cont
# Intuition\n\nWhen approaching the problem of finding the largest submatrix of 1s in a matrix, the initial thought involves exploring a method to identify a contiguous area that comprises only 1s. It\'s crucial to establish a systematic way to track the maximum possible area of such a submatrix within the given matrix.\n\n### Approach Visualization:\n\n- **Dynamic Programming for Heights of 1s:**\n  - **Step 1:** Traverse the matrix to calculate the maximum height of consecutive 1s ending at each cell.\n  - **Step 2:** Update the matrix with these maximum heights.\n\n- **Finding Maximum Area:**\n  - **Step 3:** For each row:\n    - **Substep a:** Sort the row to identify the maximum heights of 1s.\n    - **Substep b:** Calculate the area using height and width (index).\n    - **Substep c:** Track the maximum area encountered.\n\n### Intuition Visualization:\n\n- **Initial Thoughts (Intuition):**\n  - The problem focuses on identifying the largest submatrix within a matrix that comprises only 1s.\n  - The challenge involves systematically tracking the maximum possible area of such a submatrix.\n\n- **Approach Exploration:**\n  - The intuition suggests exploring a method to efficiently identify contiguous areas of 1s.\n  - Emphasizes the importance of establishing a systematic approach to determine the largest submatrix area of 1s.\n\n\n\n# Complexity\n- Time complexity:\n$$O(m\xD7nlogn)$$ \n\n- Space complexity:\nNo extra space\n\n# Code\n```\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        if (matrix.empty() || matrix[0].empty()) return 0;\n\n        int rows = matrix.size();\n        int cols = matrix[0].size();\n        int maxArea = 0;\n\n        for (int i = 1; i < rows; ++i) {\n            for (int j = 0; j < cols; ++j) {\n                if (matrix[i][j] == 1)\n                    matrix[i][j] += matrix[i - 1][j];\n            }\n        }\n\n        for (int i = 0; i < rows; ++i) {\n            sort(matrix[i].begin(), matrix[i].end(), greater<int>()); \n\n            for (int j = 0; j < cols; ++j) {\n                maxArea = max(maxArea, matrix[i][j] * (j + 1)); \n            }\n        }\n\n        return maxArea;\n    }\n};\n```
['Array', 'Sorting', 'Matrix', 'C++']