const int STACK_CAP_DEFAULT = 10;

typedef struct {
    int *data;
    int len;
    int cap;
} Stack;

Stack *Stack_init() {
    Stack *stk = malloc(sizeof(Stack));
    stk->len = 0;
    stk->cap = STACK_CAP_DEFAULT;
    stk->data = malloc(stk->cap * sizeof(int));

    return stk;
}

void Stack_push(Stack *stk, int v) {
    if(stk->len == stk->cap) {
        // grow stack
        int n_cap = stk->cap * 2;
        stk->data = realloc(stk->data, stk->cap * sizeof(int));
    }
    // Append element
    stk->data[stk->len] = v;
    stk->len++;
}

bool Stack_empty(Stack *stk) {
    return stk->len == 0;
}

int Stack_peek(Stack *stk) {
    if(Stack_empty(stk)) return -1;
    return stk->data[stk->len-1];
}

int Stack_pop(Stack *stk) {
    if(Stack_empty(stk)) return -1;
    int top = stk->data[stk->len-1];
    stk->len -= 1;
    return top;
}

void Stack_free(Stack *stk) {
    free(stk->data);
    free(stk);
}

int **make_dp_mat(int rowSize, int colSize) {
     int **dp = (int **)malloc(rowSize * sizeof(int *));
    for(int i = 0; i < rowSize; i++){
        dp[i] = (int *)malloc(colSize * sizeof(int));
        memset(dp[i], 0, colSize * sizeof(int));
    }

    return dp;
}

int max_int(int a, int b) {
    return a > b ? a : b;
}

// Determine the largest rectangle that can be formed
// from contiguous 1's on a single row
int max_rect_row(int *heights, int len) {
    if(len == 0) {
        return 0;
    }

    // For each column and direction (left/right),
    // determine the index of the last column with
    // height >= the starting column
    int dp_left[len];
    dp_left[0] = -1;

    // Stack tracks indices of columns with height
    // less than
    Stack *stk = Stack_init();
    Stack_push(stk, 0);
    for(int i = 1; i < len; i++) {
        int h = heights[i];
        // For current position, drain indices of all
        // columns with equal or greater height than
        // current
        while(!Stack_empty(stk) &&
              heights[Stack_peek(stk)] >= h) {
            Stack_pop(stk);
        }

        // Leftover indices on stack mark first column
        // with height < column height
        if(!Stack_empty(stk)) {
            dp_left[i] = Stack_peek(stk);
        } else {
            dp_left[i] = -1;
        }

        Stack_push(stk, i);
    }


    int dp_right[len];
    dp_right[len-1] = len;
    Stack_free(stk);
    stk = Stack_init();
    Stack_push(stk, len-1);
    for(int i = len-2; i >= 0; i--) {
        int h = heights[i];

        while(!Stack_empty(stk) &&
             heights[Stack_peek(stk)] >= h) {
            Stack_pop(stk);
        }

        if(!Stack_empty(stk)) {
            dp_right[i] = Stack_peek(stk);
        } else {
            dp_right[i] = len;
        }

        Stack_push(stk, i);
    }

    for(int i = len-1; i >= 0; i--) {
        int h = heights[i];
        int j = i-1;
        for(; j >= 0; j--) {
            if(heights[j] < h) break;
        }
        dp_left[i] = j;
    }

    // Calculate max rect area for each column
    int max = 0;
    for(int i = 0; i < len; i++) {
        int left_dist = i - dp_left[i];
        int right_dist = dp_right[i] - i;
        max = max_int(max, heights[i] * (left_dist+right_dist-1));
    }

    Stack_free(stk);
    return max;
}

int maximalRectangle(char** matrix, int matrixRowSize, int *matrixColSizes) {
    // Initialize an RxC Rect matrix and set elements to 0
    if(matrixRowSize == 0) return 0;
    if((int)matrixColSizes == 0) return 0;
    int colSize = (int)matrixColSizes;
    int rowSize = matrixRowSize;
    int **dp = make_dp_mat(rowSize, colSize);

    // For each col in each row, calculate the number
    // of contiguous 1's above the column
    for(int c = 0; c < colSize; c++) {
        dp[0][c] = matrix[0][c] - '0';
    }
    for(int r = 1; r < rowSize; r++) {
        int p = r-1;
        for(int c = 0; c < colSize; c++) {
            if(matrix[r][c] == '0') {
                dp[r][c] = 0;
                continue;
            }
            dp[r][c] = dp[p][c] + 1;
        }
    }

    int max = 0;
    for(int r = 0; r < rowSize; r++) {
        max = max_int(max, max_rect_row(dp[r], colSize));
    }

    return max;
}