[We💕Simple] Counting Sort, Dynamic Programming w/ Explanations
I always like to find solutions that are very simple and easy, yet do not sacrifice time complexity. I keep creating more solutions\n\n# Code\nKotlin []\nclass 
I always like to find solutions that are very simple and easy, yet do not sacrifice time complexity. I keep creating more solutions\n\n# Code\n``` Kotlin []\nclass Solution {\n    fun largestSubmatrix(matrix: Array<IntArray>): Int {\n        val heights = IntArray(matrix[0].size)\n        var maxArea = 0\n        for (row in matrix) {\n            val countByHeightInRow = sortedMapOf<Int, Int>(Comparator.reverseOrder())\n            for ((j, v) in row.withIndex()) {\n                if (v == 0) {\n                    heights[j] = 0\n                } else {\n                    heights[j] += 1\n                    countByHeightInRow[heights[j]] = countByHeightInRow.getOrDefault(heights[j], 0) + 1\n                }\n            }\n            var accHeightCount = 0\n            for ((height, count) in countByHeightInRow) {\n                accHeightCount += count\n                maxArea = maxOf(maxArea, accHeightCount * height)\n            }\n        }\n        return maxArea\n    }\n}\n\n// Shorter version\nclass Solution {\n    fun largestSubmatrix(matrix: Array<IntArray>): Int =\n        matrix.fold(0 to IntArray(matrix[0].size)) { (maxArea, heights), row ->\n            sortedMapOf<Int, Int>(Comparator.reverseOrder()).apply {\n                for ((j, v) in row.withIndex()) {\n                    heights[j] = if (v == 0) 0 else heights[j] + 1\n                    this[heights[j]] = this.getOrDefault(heights[j], 0) + 1\n                }\n            }.entries.fold(maxArea to 0) { (maxArea, acc), (height, count) ->\n                maxOf(maxArea, height * (acc + count)) to acc + count\n            }.first to heights\n        }.first\n}\n\n// Sort version\nclass Solution {\n    fun largestSubmatrix(matrix: Array<IntArray>): Int {\n        val m = matrix.size\n        val n = matrix[0].size\n        var maxArea = 0\n\n        for (i in 1 until m) {\n            for (j in 0 until n) {\n                if (matrix[i][j] != 0) {\n                    matrix[i][j] += matrix[i - 1][j]\n                }\n            }\n        }\n\n        for (row in matrix) {\n            row.sort()\n            for (j in 0 until n) {\n                maxArea = maxOf(maxArea, row[j] * (n - j))\n            }\n        }\n\n        return maxArea\n    }\n}\n\n```\n\n``` Python3 []\nclass Solution:\n    def largestSubmatrix(self, matrix):\n        heights = [0] * len(matrix[0])\n        answer = 0\n\n        for row in matrix:\n            count_by_height = {}\n            for j, value in enumerate(row):\n                if value == 0:\n                    heights[j] = 0\n                else:\n                    heights[j] += 1\n                    count_by_height[heights[j]] = count_by_height.get(heights[j], 0) + 1\n            \n            acc_height_count = 0\n            for height in sorted(count_by_height.keys(), reverse=True):\n                acc_height_count += count_by_height[height]\n                answer = max(answer, acc_height_count * height)\n        \n        return answer\n```\n\n1.  **Iterating Through Each Row and Calculating Heights**: The algorithm iterates through each row of the matrix and calculates the \'heights\' of consecutive 1s for each column. This \'height\' represents the number of 1s stacked vertically up to the current row. For instance, if a column has 1s in three consecutive rows, its height would be 3 in the third row. This step is crucial because it transforms the problem into a series of histogram-like structures where each column\'s height can be visualized as a bar in a histogram.\n\n2.  **Count Sorting of Heights**: After computing the heights for each column in a row, these heights are sorted in descending order using a `sortedMapOf`. This sorting is essential because it aligns the columns in order of their heights, prioritizing taller \'bars\' first. This priority is key for efficiently finding the largest rectangle at each step.\n3.  **Iterating in Descending Order of Heights**: The algorithm then iterates over these heights, starting from the tallest. During this iteration, it calculates the potential size of the submatrix (rectangle) that can be formed using the current height as the limiting factor. The idea is to consider the tallest column and see how wide the rectangle can be, encompassing shorter columns to its right. This process is repeated for each height, progressively considering shorter heights and wider potential rectangles.\n4.  **Updating the Maximum Submatrix Size**: For each height, the algorithm calculates the area of the potential rectangle and updates the maximum size found so far. This update is a crucial step because it ensures that the largest possible submatrix is not missed. The area is calculated by multiplying the current height with the cumulative count of columns that are at least as tall as the current height.\n\nBy integrating these steps, the algorithm efficiently finds the largest rectangular area in a binary matrix. The use of height calculation transforms the 2D problem into a series of 1D problems (like histograms), and the sorted iteration ensures that the largest possible rectangles are considered first, optimizing the search for the maximum area. This approach is a blend of dynamic programming (keeping track of heights) and a greedy strategy (prioritizing larger heights first).\n
['Dynamic Programming', 'Counting Sort', 'Python', 'Python3', 'Kotlin']