Typescript: sort and without sort solutions (Runtime beats 100%)
Complexity\n- Time complexity:\nO(n * m)\n\n- Space complexity:\nO(n)\n\n# Code\n\n// TC (m * n), SC: (n)\nfunction largestSubmatrix(matrix: number[][]): number
# Complexity\n- Time complexity:\nO(n * m)\n\n- Space complexity:\nO(n)\n\n# Code\n```\n// TC (m * n), SC: (n)\nfunction largestSubmatrix(matrix: number[][]): number {\n    const m: number = matrix.length;\n    const n: number = matrix[0].length;\n    let maxArea: number = 0;\n    let prevHeights: [number, number][] = [];\n\n    for (let row = 0; row < m; row++) {\n        const heights: [number, number][] = [];\n        const seen: boolean[] = new Array(n).fill(false);\n\n        for (const [height, col] of prevHeights) {\n            if (matrix[row][col] == 1) {\n                heights.push([height + 1, col]);\n                seen[col] = true;\n            }\n        }\n\n        for (let col = 0; col < n; col++) {\n            if (!seen[col] && matrix[row][col] == 1) {\n                heights.push([1, col]);\n            }\n        }\n\n        for (let i = 0; i < heights.length; i++) {\n            maxArea = Math.max(maxArea, heights[i][0] * (i + 1));\n        }\n\n        prevHeights = heights;\n    }\n\n    return maxArea;\n}\n\n// TC: O(m * n * logn), SC: O(m * n)\nfunction largestSubmatrixSort(matrix: number[][]): number {\n    const m: number = matrix.length;\n    const n: number = matrix[0].length;\n    let maxArea: number = 0;\n\n    for (let row = 0; row < m; row++) {\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        const currentRow = [...matrix[row]].sort((a, b) => b - a);\n\n        for (let i = 0; i < n; i++) {\n            maxArea = Math.max(maxArea, currentRow[i] * (i + 1));\n        }\n    }\n\n    return maxArea;\n};\n```
['Array', 'Greedy', 'Sorting', 'Matrix', 'TypeScript', 'JavaScript']