【Video】Sorting solution
Intuition\nUsing sort for width.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/odAv92zWKqs\n\nThese days, many people watch my video more than 70% of whole tim
# Intuition\nUsing sort for width.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/odAv92zWKqs\n\nThese days, many people watch my video more than 70% of whole time, which is good to my channel reputation. Thank you!\n\nI\'m creating this video or post with the goal of ensuring that viewers, whether they read the post or watch the video, won\'t waste their time. I\'m confident that if you spend 10 minutes watching the video, you\'ll grasp the understanding of this problem.\n\n\u25A0 Timeline of the video\n\n`0:05` How we can move columns\n`1:09` Calculate height\n`2:48` Calculate width\n`4:10` Let\'s make sure it works\n`5:40` Demonstrate how it works\n`7:44` Coding\n`9:59` Time Complexity and Space Complexity\n`10:35` Summary of the algorithm with my solution code\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 4,543\nMy first goal is 10,000 (It\'s far from done \uD83D\uDE05)\nThank you for your support!\n\n**My channel reached 3,000 subscribers these days. Thank you so much for your support!**\n\n---\n\n# Approach\n## How we think about a solution\n\nWe should return the largest square in the metrix. Simply formula is\n\n```\nheight * width\n```\nLet\'s think about this.\n```\nInput: matrix = [[0,0,1],[1,1,1],[1,0,1]]\n```\nSince we can rearrange the matrix by entire columns, we can consider entire columns as a height.\n\n### How can we rearrange the matrix?\n\nFor example, we can move entire columns at index 2 to left.\n```\n     \u2193       \u2193\n[0,0,1]   [0,1,0]\n[1,1,1] \u2192 [1,1,1]\n[1,0,1]   [1,1,0]\n```\nWe can\'t move part of columns like this.\n```\n[0,0,1]   [0,0,1]\n[1,1,1] \u2192 [1,1,1]\n[1,0,1]   [1,1,0]\u2190\n```\n### Calculate height at each column.\n```\nAt column index 0\n\n[0,0,1]   [0,0,1]\n[1,1,1] \u2192 [1,1,1]\n[1,0,1]   [2,0,1]\n\nmatrix[0][0] is 0 height.\nmatrix[1][0] is 1 height.\nmatrix[2][0] is 2 height.(= from matrix[1][0] to matrix[2][0])\n```\n```\nAt column index 1\n\n[0,0,1]   [0,0,1]\n[1,1,1] \u2192 [1,1,1] \n[2,0,1]   [2,0,1]\n\nmatrix[0][1] is 0 height.\nmatrix[1][1] is 1 height.\nmatrix[2][1] is 0 height.\n```\n```\nAt column index 2\n\n[0,0,1]   [0,0,1]\n[1,1,1] \u2192 [1,1,2] \n[2,0,1]   [2,0,3]\n\nmatrix[0][2] is 1 height.\nmatrix[1][2] is 2 height. (= from matrix[0][2] to matrix[1][2])\nmatrix[2][2] is 3 height. (= from matrix[0][2] to matrix[2][2])\n```\nIn the end\n```\nOriginal\n[0,0,1]   [0,0,1]\n[1,1,1] \u2192 [1,1,2]\n[1,0,1].  [2,0,3]\n```\nIn my solution code, we iterate through each row one by one, then calculate heights. It\'s not difficult. When current number is `1`, add height from above row to current place. You can check it later in my solution code.\n\n### Calculate width at each row.\n\nNext, we need to think about width. We know that if each number is greater than `0`, it means that there is at least `1` in each position, so we can consider non zero position as `1` length for width.\n\nSince we can rearrange the matrix by entire columns, we can sort each row to move zero position to small index(left side).\n\nIn the solution code, we sort each row one by one but image of entire matrix after sorting is like this.\n```\n[0,0,1]   [0,0,1]\n[1,1,2] \u2192 [1,1,2]\n[2,0,3]   [0,2,3]\n```\nAfter sorting, all zeros in each row move to left side, that means we have some numbers on the right side, so we can consider right side as part of width.\n\nCalculation of each postion\nHeight is each number.\nWidth is length of row - current column index\n```\n[0,0,1]\n[1,1,2]\n[0,2,3]\n\n              h w a\nmatrix[0][0]: 0 3 0\nmatrix[0][1]: 0 2 0\nmatrix[0][2]: 1 1 1\nmatrix[1][0]: 1 3 3\nmatrix[1][1]: 1 2 3\nmatrix[1][2]: 2 1 3\nmatrix[2][0]: 0 3 3\nmatrix[2][1]: 2 2 4\nmatrix[2][2]: 3 1 4\n\nh: height\nw: width\na: max area so far\n```\n```\nOutput: 4\n```\n### Are you sure sorting works?\n \nSomebody is wondering "Are you sure sorting works?"\n\nLet\'s focus on `[0,2,3]`. This means at `column index 1`, there is `2` heights and at `column index 2`(different column index from `column index 1`), there are `3` heights.\n\nSo we are sure that we can create this matrix.\n```\n[0,0,1]   \n[1,1,1]\n[0,1,1]\n   \u2191 \u2191\n   2 3\n```\nThat\'s why at `matrix[2][1]`, we calculate `2`(= height from `matrix[1][1]` to `matrix[2][1]`) * `2`(= width from `matrix[2][1]` to `matrix[2][2]`).\n\nSorting enables the creation of heights from right to left in descending order. In other words, we are sure after `column index 1`, we have `at least 2 height or more`(in this case, we have `3 heights`), so definitely we can calculate size of the square(in this case, `2 * 2`).\n\nThank you sorting algorithm!\nLet\'s wrap up the coding part quickly and grab a beer! lol\n\n---\n\n\n\n### Algorithm Overview:\n\n1. Calculate Heights:\n2. Calculate Maximum Area:\n\n### Detailed Explanation:\n\n1. **Calculate Heights:**\n```python\nclass Solution:\n    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n        row, col = len(matrix), len(matrix[0])\n\n        # Calculate Heights for Each Column\n        for i in range(1, row):\n            for j in range(col):\n                if matrix[i][j] == 1:\n                    matrix[i][j] += matrix[i - 1][j]\n```\n\n**Explanation:**\n- This part iterates through each row (starting from the second row) and each column.\n- If the current element is 1 (`matrix[i][j] == 1`), it adds the value from the previous row to the current element.\n- This creates a cumulative sum of heights for each column, forming a "height matrix."\n\n\n2. **Calculate Maximum Area:**\n\n```python\n        res = 0\n\n        # Calculate Maximum Area\n        for i in range(row):\n            # Sort the heights in ascending order\n            matrix[i].sort()\n\n            # Iterate through the sorted heights\n            for j in range(col):\n                height = matrix[i][j]\n                width = col - j\n\n                # Calculate the area using the current height and remaining width\n                res = max(res, height * width)\n```\n\n**Explanation:**\n- This part initializes `res` to 0, which will store the maximum area.\n- It then iterates through each row of the matrix.\n- For each row, it sorts the heights in ascending order. This is crucial for calculating the maximum area.\n- It iterates through the sorted heights and calculates the area for each height and its corresponding width.\n- The maximum area is updated in the variable `res` if a larger area is found.\n\n\n---\n\n\n\n# Complexity\n- Time complexity: $$O(row * col * log(col))$$\nSort each row and each row has length of col.\n\n- Space complexity: $$O(log col)$$ or $$O(col)$$\nExcept matrix. The sort() operation on the heights array utilizes a temporary working space, which can be estimated as $$O(log col)$$ or $$O(col)$$ in the worst case.\n\n```python []\nclass Solution:\n    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n        row, col = len(matrix), len(matrix[0])\n\n        # Calculate heights for each column\n        for i in range(1, row):\n            for j in range(col):\n                if matrix[i][j] == 1:\n                    matrix[i][j] += matrix[i - 1][j]\n\n        res = 0\n        for i in range(row):\n            # Sort the heights in ascending order\n            matrix[i].sort()\n\n            # Iterate through the sorted heights\n            for j in range(col):\n                height = matrix[i][j]\n                width = col - j\n                res = max(res, height * width)\n\n        return res\n```\n```javascript []\nvar largestSubmatrix = function(matrix) {\n    const row = matrix.length;\n    const col = matrix[0].length;\n\n    // Calculate heights for each column\n    for (let i = 1; i < row; i++) {\n        for (let j = 0; j < col; j++) {\n            if (matrix[i][j] === 1) {\n                matrix[i][j] += matrix[i - 1][j];\n            }\n        }\n    }\n\n    let res = 0;\n    for (let i = 0; i < row; i++) {\n        // Sort the heights in ascending order\n        matrix[i].sort((a, b) => a - b);\n\n        // Iterate through the sorted heights\n        for (let j = 0; j < col; j++) {\n            const height = matrix[i][j];\n            const width = col - j;\n            res = Math.max(res, height * width);\n        }\n    }\n\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public int largestSubmatrix(int[][] matrix) {\n        int row = matrix.length;\n        int col = matrix[0].length;\n\n        // Calculate heights for each column\n        for (int i = 1; i < row; i++) {\n            for (int j = 0; j < col; j++) {\n                if (matrix[i][j] == 1) {\n                    matrix[i][j] += matrix[i - 1][j];\n                }\n            }\n        }\n\n        int res = 0;\n        for (int i = 0; i < row; i++) {\n            // Sort the heights in ascending order\n            Arrays.sort(matrix[i]);\n\n            // Iterate through the sorted heights\n            for (int j = 0; j < col; j++) {\n                int height = matrix[i][j];\n                int width = col - j;\n                res = Math.max(res, height * width);\n            }\n        }\n\n        return res;        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int row = matrix.size();\n        int col = matrix[0].size();\n\n        // Calculate heights for each column\n        for (int i = 1; i < row; i++) {\n            for (int j = 0; j < col; j++) {\n                if (matrix[i][j] == 1) {\n                    matrix[i][j] += matrix[i - 1][j];\n                }\n            }\n        }\n\n        int res = 0;\n        for (int i = 0; i < row; i++) {\n            // Sort the heights in ascending order\n            sort(matrix[i].begin(), matrix[i].end());\n\n            // Iterate through the sorted heights\n            for (int j = 0; j < col; j++) {\n                int height = matrix[i][j];\n                int width = col - j;\n                res = max(res, height * width);\n            }\n        }\n\n        return res;         \n    }\n};\n```\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n\u25A0 Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### My next daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/solutions/4340183/video-give-me-7-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/DF9NXNW0G6E\n\n\u25A0 Timeline of the video\n\n`0:05` Return 0\n`0:38` Think about a case where we can put dividers\n`4:44` Coding\n`7:18` Time Complexity and Space Complexity\n`7:33` Summary of the algorithm with my solution code\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/solutions/4329227/video-give-me-10-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/bwQh44GWME8\n\n\u25A0 Timeline of the video\n\n`0:05` How we can solve this question\n`1:56` Calculate left total\n`6:32` Calculate right total\n`11:12` Create answers\n`11:51` Coding\n`14:14` Time Complexity and Space Complexity\n`14:39` Summary of the algorithm with my solution code\n\n
['C++', 'Java', 'Python3', 'JavaScript']