✅☑[C++/Java/Python/JavaScript] || 3 Approaches || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n#### Approach 1(Sort By Height On Each Baseline Row)\n1. Matrix traversal:\
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n#### ***Approach 1(Sort By Height On Each Baseline Row)***\n1. **Matrix traversal:**\n    - The code iterates through each row of the matrix.\n1. **Accumulating consecutive ones:**\n    - For each non-zero element in the matrix (except in the first row), the code accumulates its value with the element directly above it. This accumulation happens vertically, tracking consecutive ones.\n\n    - For example, if we start with the first row, the elements with 1s in the second row get incremented by the value in the first row if the element in the first row at the same column is also 1. It accumulates the count of consecutive ones vertically.\n\n1. **Finding the largest submatrix:**\n    - After accumulating the consecutive ones, it creates a copy of the current row and sorts it in descending order.\n\n    - By sorting, the largest consecutive blocks of ones are moved to the front of the row.\n\n    - The code then calculates the area of the largest submatrix by multiplying the height (number of consecutive ones) with the width (position in the sorted row). It updates and keeps track of the maximum area found.\n\n*In the example matrix:*\n\n- **For the first row:** `[0, 1, 1, 0, 1]`, the consecutive ones count would be `[0, 1, 1, 0, 2]`.\n- **For the second row:** `[1, 2, 1, 2, 0]`, the consecutive ones count would be `[1, 2, 1, 2, 0]`.\n- **For the third row:** `[1, 2, 3, 4, 0]`, the consecutive ones count would be `[1, 2, 3, 4, 0]`.\n- **For the fourth row:** `[2, 3, 4, 5, 1]`, the consecutive ones count would be `[2, 3, 4, 5, 1]`.\n\n# Complexity\n- *Time complexity:*\n   $$O(m.n.logn)$$\n    \n\n- *Space complexity:*\n   $$O(m.n)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m = matrix.size(); // Number of rows in the matrix\n        int n = matrix[0].size(); // Number of columns in the matrix\n        int ans = 0; // Initialize the maximum area of the largest submatrix\n        \n        // Traverse through each row in the matrix\n        for (int row = 0; row < m; row++) {\n            // For each non-zero element in the matrix (except the first row),\n            // accumulate its value with the element directly above it\n            for (int col = 0; col < n; col++) {\n                if (matrix[row][col] != 0 && row > 0) {\n                    matrix[row][col] += matrix[row - 1][col];\n                }\n            }\n            \n            // Create a copy of the current row to work with\n            vector<int> currRow = matrix[row];\n            \n            // Sort the elements in the current row in descending order\n            sort(currRow.begin(), currRow.end(), greater<int>());\n            \n            // Calculate the maximum area of the largest submatrix with consecutive ones\n            for (int i = 0; i < n; i++) {\n                ans = max(ans, currRow[i] * (i + 1));\n            }\n        }\n        \n        return ans; // Return the maximum area of the largest submatrix\n    }\n};\n\n\n\n```\n```C []\n\n#include <stdio.h>\n#include <stdlib.h>\n\n// Function to calculate the maximum area of the largest submatrix with consecutive ones\nint largestSubmatrix(int** matrix, int m, int n) {\n    int ans = 0; // Initialize the maximum area of the largest submatrix\n\n    // Traverse through each row in the matrix\n    for (int row = 0; row < m; row++) {\n        // For each non-zero element in the matrix (except the first row),\n        // accumulate its value with the element directly above it\n        for (int col = 0; col < n; col++) {\n            if (matrix[row][col] != 0 && row > 0) {\n                matrix[row][col] += matrix[row - 1][col];\n            }\n        }\n\n        // Create a copy of the current row to work with\n        int* currRow = malloc(n * sizeof(int));\n        for (int i = 0; i < n; i++) {\n            currRow[i] = matrix[row][i];\n        }\n\n        // Sort the elements in the current row in descending order\n        for (int i = 0; i < n - 1; i++) {\n            for (int j = 0; j < n - i - 1; j++) {\n                if (currRow[j] < currRow[j + 1]) {\n                    int temp = currRow[j];\n                    currRow[j] = currRow[j + 1];\n                    currRow[j + 1] = temp;\n                }\n            }\n        }\n\n        // Calculate the maximum area of the largest submatrix with consecutive ones\n        for (int i = 0; i < n; i++) {\n            ans = ans > currRow[i] * (i + 1) ? ans : currRow[i] * (i + 1);\n        }\n\n        free(currRow);\n    }\n\n    return ans; // Return the maximum area of the largest submatrix\n}\n\n\n```\n```Java []\nclass Solution {\n    public int largestSubmatrix(int[][] matrix) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n        int ans = 0;\n        \n        for (int row = 0; row < m; row++) {\n            for (int col = 0; col < n; col++) {\n                if (matrix[row][col] != 0 && row > 0) {\n                    matrix[row][col] += matrix[row - 1][col];\n                }\n            }\n            \n            int[] currRow = matrix[row].clone();\n            Arrays.sort(currRow);\n            for (int i = 0; i < n; i++) {\n                ans = Math.max(ans, currRow[i] * (n - i));\n            }\n        }\n        \n        return ans;\n    }\n}\n\n\n```\n```python3 []\nclass Solution:\n    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n        m = len(matrix)\n        n = len(matrix[0])\n        ans = 0\n\n        for row in range(m):\n            for col in range(n):\n                if matrix[row][col] != 0 and row > 0:\n                    matrix[row][col] += matrix[row - 1][col]\n\n            curr_row = sorted(matrix[row], reverse=True)\n            for i in range(n):\n                ans = max(ans, curr_row[i] * (i + 1))\n\n        return ans\n\n```\n\n```javascript []\nfunction largestSubmatrix(matrix) {\n    let m = matrix.length; // Number of rows\n    let n = matrix[0].length; // Number of columns\n    let ans = 0; // Initialize the maximum area of the largest submatrix\n\n    // Traverse through each row in the matrix\n    for (let row = 0; row < m; row++) {\n        // For each non-zero element in the matrix (except the first row),\n        // accumulate its value with the element directly above it\n        for (let col = 0; col < n; col++) {\n            if (matrix[row][col] !== 0 && row > 0) {\n                matrix[row][col] += matrix[row - 1][col];\n            }\n        }\n\n        // Create a copy of the current row to work with\n        let currRow = matrix[row].slice();\n        \n        // Sort the elements in the current row in descending order\n        currRow.sort((a, b) => b - a);\n\n        // Calculate the maximum area of the largest submatrix with consecutive ones\n        for (let i = 0; i < n; i++) {\n            ans = Math.max(ans, currRow[i] * (i + 1));\n        }\n    }\n\n    return ans; // Return the maximum area of the largest submatrix\n}\n\n\n\n```\n\n---\n\n#### ***Approach 2(Without Modifying Input)***\n1. **Initialization:** Define the matrix\'s size, initialize the `prevRow` vector, and initialize ans to store the maximum area.\n1. **Iteration through Rows:** Traverse through each row of the matrix.\n1. **Cumulative Sum:** Calculate the cumulative sum for each element in the current row by adding the element with its corresponding element in the `prevRow`.\n1. **Sorting:** Sort the elements of the current row in descending order.\n1. **Calculate Maximum Area:** For each index `i`, calculate the area considering the sorted row and update `ans` if a larger area is found.\n1. **Update Previous Row:** Update the `prevRow` for the next iteration with the current row.\n1. **Return Result:** Return the maximum area found.\n\n\n\n# Complexity\n- *Time complexity:*\n   $$O(m\u22C5n\u22C5logn)$$\n    \n\n- *Space complexity:*\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\n\n\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m = matrix.size(); // Number of rows in the matrix\n        int n = matrix[0].size(); // Number of columns in the matrix\n        vector<int> prevRow = vector<int>(n, 0); // Vector to store the previous row\n        int ans = 0; // Initialize the maximum area of the largest submatrix\n        \n        for (int row = 0; row < m; row++) {\n            vector<int> currRow = matrix[row]; // Copy the current row of the matrix\n            \n            // Calculate the cumulative sum for each element in the current row\n            for (int col = 0; col < n; col++) {\n                if (currRow[col] != 0) {\n                    currRow[col] += prevRow[col]; // Add the element with its corresponding element in the previous row\n                }\n            }\n            \n            // Sort the elements in the current row in descending order\n            vector<int> sortedRow = currRow;\n            sort(sortedRow.begin(), sortedRow.end(), greater<int>());\n            \n            // Calculate the maximum area of the largest submatrix with consecutive ones\n            for (int i = 0; i < n; i++) {\n                ans = max(ans, sortedRow[i] * (i + 1)); // Update the maximum area\n            }\n            \n            prevRow = currRow; // Update the previous row for the next iteration\n        }\n\n        return ans; // Return the maximum area of the largest submatrix\n    }\n};\n\n\n\n```\n```C []\n\n#include <stdio.h>\n#include <stdlib.h>\n\n// Function to calculate the largest submatrix\nint largestSubmatrix(int** matrix, int m, int n) {\n    int ans = 0;\n    int* prevRow = (int*)malloc(n * sizeof(int));\n    for (int i = 0; i < n; i++) {\n        prevRow[i] = 0;\n    }\n\n    for (int row = 0; row < m; row++) {\n        int* currRow = matrix[row];\n\n        for (int col = 0; col < n; col++) {\n            if (currRow[col] != 0) {\n                currRow[col] += prevRow[col];\n            }\n        }\n\n        int sortedRow[n];\n        for (int i = 0; i < n; i++) {\n            sortedRow[i] = currRow[i];\n        }\n        // Sort the row in descending order\n        for (int i = 0; i < n - 1; i++) {\n            for (int j = 0; j < n - i - 1; j++) {\n                if (sortedRow[j] < sortedRow[j + 1]) {\n                    int temp = sortedRow[j];\n                    sortedRow[j] = sortedRow[j + 1];\n                    sortedRow[j + 1] = temp;\n                }\n            }\n        }\n\n        for (int i = 0; i < n; i++) {\n            ans = ans > sortedRow[i] * (i + 1) ? ans : sortedRow[i] * (i + 1);\n        }\n\n        for (int i = 0; i < n; i++) {\n            prevRow[i] = currRow[i];\n        }\n    }\n\n    free(prevRow);\n    return ans;\n}\n\n\n```\n```Java []\n\nclass Solution {\n    public int largestSubmatrix(int[][] matrix) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n        int[] prevRow = new int[n];\n        int ans = 0;\n        \n        for (int row = 0; row < m; row++) {\n            int[] currRow = matrix[row].clone();\n            for (int col = 0; col < n; col++) {\n                if (currRow[col] != 0) {\n                    currRow[col] += prevRow[col];\n                }\n            }\n            \n            int[] sortedRow = currRow.clone();\n            Arrays.sort(sortedRow);\n            for (int i = 0; i < n; i++) {\n                ans = Math.max(ans, sortedRow[i] * (n - i));\n            }\n            \n            prevRow = currRow;\n        }\n        \n        return ans;\n    }\n}\n\n\n```\n```python3 []\nclass Solution:\n    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n        m = len(matrix)\n        n = len(matrix[0])\n        prev_row = [0] * n\n        ans = 0\n        \n        for row in range(m):\n            curr_row = matrix[row][:]\n            for col in range(n):\n                if curr_row[col] != 0:\n                    curr_row[col] += prev_row[col]\n\n            sorted_row = sorted(curr_row, reverse=True)\n            for i in range(n):\n                ans = max(ans, sorted_row[i] * (i + 1))\n\n            prev_row = curr_row\n\n        return ans\n\n```\n\n```javascript []\nfunction largestSubmatrix(matrix) {\n    let m = matrix.length;\n    let n = matrix[0].length;\n    let prevRow = Array(n).fill(0);\n    let ans = 0;\n\n    for (let row = 0; row < m; row++) {\n        let currRow = [...matrix[row]];\n\n        for (let col = 0; col < n; col++) {\n            if (currRow[col] !== 0) {\n                currRow[col] += prevRow[col];\n            }\n        }\n\n        let sortedRow = [...currRow].sort((a, b) => b - a);\n\n        for (let i = 0; i < n; i++) {\n            ans = Math.max(ans, sortedRow[i] * (i + 1));\n        }\n\n        prevRow = [...currRow];\n    }\n\n    return ans;\n}\n\n```\n\n---\n#### ***Approach 3(No Sort)***\n\n1. **largestSubmatrix Function:**\n    - Finds the largest submatrix of consecutive ones in the given matrix.\n    \n1. **Variables Used:**\n    - **`m` and `n`:** Number of rows and columns in the matrix, respectively.\n    - **prevHeights:** Stores heights of 1s from the previous row.\n    - **ans:** Tracks the maximum submatrix area.\n1. **Iterating Through Each Row:**\n    - The outer loop iterates through each row of the matrix.\n1. **Finding Heights of Ones in Each Row:**\n    - For each row, it tracks the heights of consecutive 1s and columns seen in the previous row.\n    - **heights:** Vector that stores pairs of heights and corresponding columns for the current row.\n    - **seen:** Tracks the columns that have already been seen in the previous row.\n1. **Calculating Heights:**\n    - It iterates through the previous heights and increments the height for each 1 encountered in the current row.\n    - For new 1s in the current row (not seen in the previous row), it sets a new height.\n1. **Calculating Maximum Submatrix Area:**\n    - For each height, it calculates the area by multiplying the height by the width (i + 1) and updates `ans` if a larger area is found.\n1. **Updating Heights for the Next Row:**\n    - Updates `prevHeights` with the heights from the current row to prepare for the next row iteration.\n1. **Returns:**\n    - Returns the maximum submatrix area found.\n\n# Complexity\n- *Time complexity:*\n   $$O(m.n)$$\n    \n\n- *Space complexity:*\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m = matrix.size();  // Number of rows in the matrix\n        int n = matrix[0].size();  // Number of columns in the matrix\n        vector<pair<int,int>> prevHeights;  // To store heights of 1s from the previous row\n        int ans = 0;  // Initialize the maximum submatrix area\n        \n        for (int row = 0; row < m; row++) {\n            vector<pair<int,int>> heights;  // Heights of 1s for the current row\n            vector<bool> seen = vector(n, false);  // To track the columns already seen\n            \n            // Process the heights from the previous row\n            for (auto [height, col] : prevHeights) {\n                if (matrix[row][col] == 1) {\n                    heights.push_back({height + 1, col});  // Increase the height if the current element is 1\n                    seen[col] = true;  // Mark the column as seen\n                }\n            }\n            \n            // Process the new heights in the current row\n            for (int col = 0; col < n; col++) {\n                if (seen[col] == false && matrix[row][col] == 1) {\n                    heights.push_back({1, col});  // New height for a new column\n                }\n            }\n            \n            // Calculate the area for each height and update the maximum area\n            for (int i = 0; i < heights.size(); i++) {\n                ans = max(ans, heights[i].first * (i + 1));\n            }\n            \n            prevHeights = heights;  // Update the heights for the next row\n        }\n\n        return ans;  // Return the maximum submatrix area\n    }\n};\n\n\n\n```\n```C []\n\n#include <stdio.h>\n#include <stdlib.h>\n\nstruct Pair {\n    int first;\n    int second;\n};\n\nint max(int a, int b) {\n    return (a > b) ? a : b;\n}\n\nint largestSubmatrix(int** matrix, int m, int n) {\n    struct Pair* prevHeights = malloc(sizeof(struct Pair) * n);\n    int ans = 0;\n    \n    for (int row = 0; row < m; row++) {\n        struct Pair* heights = malloc(sizeof(struct Pair) * n);\n        int* seen = calloc(n, sizeof(int));\n        \n        for (int i = 0; i < n; i++) {\n            heights[i].first = 0;\n            heights[i].second = 0;\n        }\n        \n        for (int i = 0; i < n; i++) {\n            heights[i].first = prevHeights[i].first;\n            heights[i].second = prevHeights[i].second;\n        }\n        \n        for (int col = 0; col < n; col++) {\n            if (matrix[row][col] == 1) {\n                if (row > 0 && matrix[row - 1][col] == 1) {\n                    heights[col].first++;\n                }\n                else {\n                    heights[col].first = 1;\n                    heights[col].second = col;\n                }\n                seen[col] = 1;\n            }\n        }\n        \n        for (int col = 0; col < n; col++) {\n            if (seen[col] == 0 && matrix[row][col] == 1) {\n                heights[col].first = 1;\n                heights[col].second = col;\n            }\n        }\n        \n        for (int i = 0; i < n; i++) {\n            ans = max(ans, heights[i].first * (i + 1));\n        }\n        \n        for (int i = 0; i < n; i++) {\n            prevHeights[i].first = heights[i].first;\n            prevHeights[i].second = heights[i].second;\n        }\n        \n        free(heights);\n        free(seen);\n    }\n\n    free(prevHeights);\n    return ans;\n}\n\n\n```\n```Java []\nclass Solution {\n    public int largestSubmatrix(int[][] matrix) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n        List<Pair<Integer,Integer>> prevHeights = new ArrayList();\n        int ans = 0;\n        \n        for (int row = 0; row < m; row++) {\n            List<Pair<Integer,Integer>> heights = new ArrayList();\n            boolean[] seen = new boolean[n];\n            \n            for (Pair<Integer, Integer> pair : prevHeights) {\n                int height = pair.getKey();\n                int col = pair.getValue();\n                if (matrix[row][col] == 1) {\n                    heights.add(new Pair(height + 1, col));\n                    seen[col] = true;\n                }\n            }\n            \n            for (int col = 0; col < n; col++) {\n                if (seen[col] == false && matrix[row][col] == 1) {\n                    heights.add(new Pair(1, col));\n                }\n            }\n            \n            for (int i = 0; i < heights.size(); i++) {\n                ans = Math.max(ans, heights.get(i).getKey() * (i + 1));\n            }\n\n            prevHeights = heights;\n        }\n        \n        return ans;\n    }\n}\n\n\n\n\n```\n```python3 []\nclass Solution:\n    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n        m = len(matrix)\n        n = len(matrix[0])\n        prev_heights = []\n        ans = 0\n\n        for row in range(m):\n            heights = []\n            seen = [False] * n\n            \n            for height, col in prev_heights:\n                if matrix[row][col] == 1:\n                    heights.append((height + 1, col))\n                    seen[col] = True\n\n            for col in range(n):\n                if seen[col] == False and matrix[row][col] == 1:\n                    heights.append((1, col))\n            \n            for i in range(len(heights)):\n                ans = max(ans, heights[i][0] * (i + 1))\n                \n            prev_heights = heights\n\n        return ans\n\n```\n\n```javascript []\nfunction largestSubmatrix(matrix) {\n    let m = matrix.length;\n    let n = matrix[0].length;\n    let prevHeights = new Array(n).fill({ first: 0, second: 0 });\n    let ans = 0;\n\n    for (let row = 0; row < m; row++) {\n        let heights = new Array(n).fill({ first: 0, second: 0 });\n        let seen = new Array(n).fill(0);\n\n        for (let i = 0; i < n; i++) {\n            heights[i].first = prevHeights[i].first;\n            heights[i].second = prevHeights[i].second;\n        }\n\n        for (let col = 0; col < n; col++) {\n            if (matrix[row][col] === 1) {\n                if (row > 0 && matrix[row - 1][col] === 1) {\n                    heights[col].first++;\n                } else {\n                    heights[col].first = 1;\n                    heights[col].second = col;\n                }\n                seen[col] = 1;\n            }\n        }\n\n        for (let col = 0; col < n; col++) {\n            if (seen[col] === 0 && matrix[row][col] === 1) {\n                heights[col].first = 1;\n                heights[col].second = col;\n            }\n        }\n\n        for (let i = 0; i < n; i++) {\n            ans = Math.max(ans, heights[i].first * (i + 1));\n        }\n\n        prevHeights = heights;\n    }\n\n    return ans;\n}\n\n```\n\n---\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Array', 'Greedy', 'C', 'Sorting', 'Matrix', 'C++', 'Java', 'Python3', 'JavaScript']