C Online Compiler
Example: Maximal Rectangle Binary Submatrix in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Maximal Rectangle Binary Submatrix #include <stdio.h> #include <stdlib.h> // For malloc, free #include <string.h> // For memset, memcpy // Function to find the largest rectangle in a histogram // heights: An array representing the heights of bars in the histogram // n: The number of bars in the histogram int largestRectangleArea(int* heights, int n) { int maxArea = 0; int* stack = (int*)malloc(sizeof(int) * n); // Store indices int top = -1; // Stack top pointer for (int i = 0; i <= n; i++) { int h = (i == n) ? 0 : heights[i]; // Current height, 0 for end of array while (top != -1 && h < heights[stack[top]]) { int currentHeight = heights[stack[top--]]; int width = (top == -1) ? i : (i - stack[top] - 1); if (currentHeight * width > maxArea) { maxArea = currentHeight * width; } } stack[++top] = i; // Push current index onto stack } free(stack); return maxArea; } // Function to find the maximal rectangle of 1s in a binary matrix // matrix: The input binary matrix (represented as a 2D array of ints) // rows: Number of rows in the matrix // cols: Number of columns in the matrix int maximalRectangle(int** matrix, int rows, int cols) { if (rows == 0 || cols == 0) { return 0; } int maxArea = 0; int* heights = (int*)calloc(cols, sizeof(int)); // Initialize with zeros // Iterate through each row for (int i = 0; i < rows; i++) { // Build histogram for the current row for (int j = 0; j < cols; j++) { if (matrix[i][j] == 1) { heights[j]++; // Increment height if current cell is 1 } else { heights[j] = 0; // Reset height to 0 if current cell is 0 } } // Find the largest rectangle in the current histogram int currentMaxArea = largestRectangleArea(heights, cols); if (currentMaxArea > maxArea) { maxArea = currentMaxArea; } } free(heights); return maxArea; } int main() { // Example 1 int matrix1_data[4][5] = { {1, 0, 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0} }; int rows1 = 4; int cols1 = 5; int** matrix1 = (int**)malloc(rows1 * sizeof(int*)); for (int i = 0; i < rows1; i++) { matrix1[i] = (int*)malloc(cols1 * sizeof(int)); for (int j = 0; j < cols1; j++) { matrix1[i][j] = matrix1_data[i][j]; } } printf("Matrix 1:\n"); for (int i = 0; i < rows1; i++) { for (int j = 0; j < cols1; j++) { printf("%d ", matrix1[i][j]); } printf("\n"); } printf("Maximal rectangle area for Matrix 1: %d\n\n", maximalRectangle(matrix1, rows1, cols1)); // Free memory for Matrix 1 for (int i = 0; i < rows1; i++) { free(matrix1[i]); } free(matrix1); // Example 2: Simple case int matrix2_data[2][2] = { {1, 1}, {1, 1} }; int rows2 = 2; int cols2 = 2; int** matrix2 = (int**)malloc(rows2 * sizeof(int*)); for (int i = 0; i < rows2; i++) { matrix2[i] = (int*)malloc(cols2 * sizeof(int)); for (int j = 0; j < cols2; j++) { matrix2[i][j] = matrix2_data[i][j]; } } printf("Matrix 2:\n"); for (int i = 0; i < rows2; i++) { for (int j = 0; j < cols2; j++) { printf("%d ", matrix2[i][j]); } printf("\n"); } printf("Maximal rectangle area for Matrix 2: %d\n\n", maximalRectangle(matrix2, rows2, cols2)); // Free memory for Matrix 2 for (int i = 0; i < rows2; i++) { free(matrix2[i]); } free(matrix2); return 0; }
Output
Clear
ADVERTISEMENTS