213ms Beats 100.00%of users with C
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nHistogram Calculation:\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Histogram Calculation:**\nFor each element in the matrix, the algorithm computes the height of the column up to that element by accumulating the consecutive occurrences of 1s in the column. This operation results in a histogram representation for each column in every row.\n**Sorting:**\nAfter obtaining the histograms, the algorithm sorts each row\'s histogram in non-decreasing order. This sorting step is crucial for identifying the maximum area efficiently.\n**Maximum Area Computation:**\nThe algorithm then iterates through each row and calculates the maximum rectangular area achievable by considering different column orders. The maximum area is determined by multiplying the minimum histogram height within a row by the corresponding width, which is the remaining number of columns after sorting.\n\n\n# Complexity\n- Time complexity: **O(m * n * log(n))**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**Histogram Calculation:**\nIn the worst case, for each element in the matrix, we perform a constant amount of work to calculate the histogram.\nThis step takes **O(m * n)** time, where m is the number of rows, and n is the number of columns.\n**Sorting:**\nFor each row, we sort the histogram array.\nSorting a single row takes **O(n * log(n))** time.\nSince we do this for m rows, the total time complexity for sorting is **O(m * n * log(n))**.\nThe dominant factor is the sorting step, so the overall time complexity is **O(m * n * log(n)).**\n\n\n- Space complexity:**O(m * n)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n**Histogram Array:**\nWe allocate a 2D histogram array to store the heights for each column in each row. The space required for this array is **O(m * n).**\n**Sorting:**\nThe space complexity for sorting is usually considered as **O(1)** since it\'s an in-place sort (qsort in C).\nso the overall space complexity is **O(m * n)**.\n\n# Code\n```\nint compare(const void* a, const void* b) \n{\n    return (*(int*)a - *(int*)b);\n}\n\nint largestSubmatrix(int** matrix, int matrixSize, int* matrixColSize) \n{\n    if (matrix == NULL || matrixSize == 0 || matrixColSize == NULL || *matrixColSize == 0)\n        return 0;\n\n    int m = matrixSize;\n    int n = *matrixColSize;\n\n    // Calculate the histogram for each column\n    int** histogram = (int**)malloc(m * sizeof(int*));\n    for (int i = 0; i < m; ++i) \n    {\n        histogram[i] = (int*)malloc(n * sizeof(int));\n        for (int j = 0; j < n; ++j) \n        {\n            if (i == 0) \n                histogram[i][j] = matrix[i][j];\n            else \n                histogram[i][j] = (matrix[i][j] == 0) ? 0 : histogram[i - 1][j] + 1;\n        }\n    }\n    // Calculate the maximum area for each row\n    int result = 0;\n    for (int i = 0; i < m; ++i) \n    {\n        qsort(histogram[i], n, sizeof(int), compare);\n        for (int j = 0; j < n; ++j)\n            result = fmax(result, histogram[i][j] * (n - j));\n    }\n\n    // Free allocated memory\n    for (int i = 0; i < m; ++i)\n        free(histogram[i]);\n    free(histogram);\n\n    return result;\n}\n```
['C']