Daily Coding Problem #22

// Given an N by M matrix consisting only of 1's and 0's, find the largest rectangle containing only 1's and return its area.

//

// For example, given the following matrix :

//

// [[1, 0, 0, 0],

// [1, 0, 1, 1],

// [1, 0, 1, 1],

// [0, 1, 0, 0]]

// Return 4.

#include <iostream>

#include <string>

#include <vector>

#include <stack>

#include <algorithm>

using namespace std;

int getMaxArea(vector<vector<int>> matrix, int rowIndex)

{

// Create an empty stack. The stack holds indexes of

// hist[] array/ The bars stored in stack are always

// in increasing order of their heights.

stack<int> result;

vector<int> row = matrix[rowIndex];

int top_val;

int max_area = 0;

int area = 0;

int i = 0;

while (i < matrix.size())

{

// If this bar is higher than the bar on top stack,

// push it to stack

if (result.empty() || row[result.top()] <= row[i])

{

result.push(i++);

}

else

{

// If this bar is lower than top of stack, then

// calculate area of rectangle with stack top as

// the smallest (or minimum height) bar. 'i' is

// 'right index' for the top and element before

// top in stack is 'left index'

top_val = row[result.top()];

result.pop();

area = top_val * i;

if (!result.empty())

area = top_val * (i - result.top() - 1);

max_area = max(area, max_area);

}

}

// Now pop the remaining bars from stack and calculate area

// with every popped bar as the smallest bar

while (!result.empty())

{

top_val = row[result.top()];

result.pop();

area = top_val * i;

if (!result.empty())

area = top_val * (i - result.top() - 1);

max_area = max(area, max_area);

}

return max_area;

}

vector<vector<int>> generateMatrix()

{

vector<vector<int>> vec;

vector<int> v0 = vector<int>(4, 0);

vector<int> v1 = vector<int>(4, 0);

vector<int> v2 = vector<int>(4, 0);

vector<int> v3 = vector<int>(4, 0);

v0[0] = 1;

v1[0] = 1; v1[2] = 1; v1[3] = 1;

v2[0] = 1; v2[2] = 1; v2[3] = 1;

v3[1] = 1;

vec.push_back(v0);

vec.push_back(v1);

vec.push_back(v2);

vec.push_back(v3);

return vec;

}

int getMaxRect(vector<vector<int>> matrix)

{

// Calculate area for first row and initialize it as

// result

int result = getMaxArea(matrix, 0);

// iterate over row to find maximum rectangular area

// considering each row as histogram

for (int i = 1; i < matrix.size(); i++)

{

for (int j = 0; j < matrix[i].size(); j++)

if (matrix[i][j])

matrix[i][j] += matrix[i - 1][j];

result = max(result, getMaxArea(matrix, i));

}

return result;

}

int main()

{

vector<vector<int>> vec = generateMatrix();

auto result = getMaxRect(vec);

cout << result << endl;

return 0;

}