C Online Compiler
Example: Maximal Rectangle in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Maximal Rectangle #include <stdio.h> #include <stdlib.h> // For malloc, free #include <string.h> // For memset #include <math.h> // For fmax (though standard max is fine) // Helper function to find the maximum of two integers int max(int a, int b) { return (a > b) ? a : b; } // Function to find the largest rectangle area in a histogram // Uses an array-based stack for simplicity in C int largestRectangleArea(int* heights, int num_cols) { // We'll use a stack to store indices of bars // MAX_COLS needs to be large enough, or use dynamic allocation for stack // For LeetCode-like problems, num_cols typically up to 200, so a static // array stack of that size is acceptable. int* stack = (int*) malloc(sizeof(int) * (num_cols + 1)); // +1 for sentinel if (stack == NULL) { perror("Failed to allocate stack"); return 0; } int top = -1; // Stack is empty int max_area = 0; int i = 0; while (i < num_cols) { // If current bar is taller than or equal to stack top, push it if (top == -1 || heights[stack[top]] <= heights[i]) { stack[++top] = i++; } else { // If current bar is smaller, pop from stack and calculate area int h_idx = stack[top--]; int height = heights[h_idx]; int width = (top == -1) ? i : (i - stack[top] - 1); max_area = max(max_area, height * width); } } // Process remaining elements in stack while (top != -1) { int h_idx = stack[top--]; int height = heights[h_idx]; int width = (top == -1) ? i : (i - stack[top] - 1); max_area = max(max_area, height * width); } free(stack); return max_area; } // Main function to solve Maximal Rectangle int maximalRectangle(char** matrix, int matrix_rows, int matrix_cols) { if (matrix_rows == 0 || matrix_cols == 0) { return 0; } // Heights array for the histogram, needs to be dynamically allocated int* heights = (int*) malloc(sizeof(int) * matrix_cols); if (heights == NULL) { perror("Failed to allocate heights array"); return 0; } // Initialize heights to 0 memset(heights, 0, sizeof(int) * matrix_cols); int max_overall_area = 0; // Iterate through each row for (int i = 0; i < matrix_rows; i++) { // Update heights for the current row for (int j = 0; j < matrix_cols; j++) { if (matrix[i][j] == '1') { heights[j]++; } else { heights[j] = 0; // Reset height if '0' is encountered } } // Calculate largest rectangle in the current histogram max_overall_area = max(max_overall_area, largestRectangleArea(heights, matrix_cols)); } free(heights); return max_overall_area; } // Example usage int main() { // Example 1 char* matrix1[] = { "10100", "10111", "11111", "10010" }; int rows1 = 4; int cols1 = 5; printf("Matrix 1:\n"); for (int i = 0; i < rows1; i++) { printf("%s\n", matrix1[i]); } printf("Maximal Rectangle Area for Matrix 1: %d\n", maximalRectangle(matrix1, rows1, cols1)); // Expected: 6 // Example 2 char* matrix2[] = { "0" }; int rows2 = 1; int cols2 = 1; printf("\nMatrix 2:\n"); for (int i = 0; i < rows2; i++) { printf("%s\n", matrix2[i]); } printf("Maximal Rectangle Area for Matrix 2: %d\n", maximalRectangle(matrix2, rows2, cols2)); // Expected: 0 // Example 3 char* matrix3[] = { "1" }; int rows3 = 1; int cols3 = 1; printf("\nMatrix 3:\n"); for (int i = 0; i < rows3; i++) { printf("%s\n", matrix3[i]); } printf("Maximal Rectangle Area for Matrix 3: %d\n", maximalRectangle(matrix3, rows3, cols3)); // Expected: 1 // Example 4 (Full of 1s) char* matrix4[] = { "111", "111", "111" }; int rows4 = 3; int cols4 = 3; printf("\nMatrix 4:\n"); for (int i = 0; i < rows4; i++) { printf("%s\n", matrix4[i]); } printf("Maximal Rectangle Area for Matrix 4: %d\n", maximalRectangle(matrix4, rows4, cols4)); // Expected: 9 return 0; }
Output
Clear
ADVERTISEMENTS