Maximal Rectangle LeetCode solution in C++

1
class Solution {
2
 private:
3
  vector<int> nextSmallerElement(int *arr, int n) {
4
    stack<int> st;
5
    st.push(-1);
6
    vector<int> ans(n);
7

8
    for (int i = n - 1; i >= 0; i--) {
9
      int curr = arr[i];
10

11
      while (st.top() != -1 && arr[st.top()] >= curr) {
12
        st.pop();
13
      }
14

15
      ans[i] = st.top();
16
      st.push(i);
17
    }
18
    return ans;
19
  }
20

21
  vector<int> prevSmallerElement(int *arr, int n) {
22
    stack<int> st;
23
    st.push(-1);
24
    vector<int> ans(n);
25

26
    for (int i = 0; i < n; i++) {
27
      int curr = arr[i];
28

29
      while (st.top() != -1 && arr[st.top()] >= curr) {
30
        st.pop();
31
      }
32

33
      ans[i] = st.top();
34
      st.push(i);
35
    }
36
    return ans;
37
  }
38

39
  int largestRectangleArea(int *heights, int n) {
40
    int area = INT_MIN;
41

42
    vector<int> next(n);
43
    next = nextSmallerElement(heights, n);
44

45
    vector<int> prev(n);
46
    prev = prevSmallerElement(heights, n);
47

48
    for (int i = 0; i < n; i++) {
49
      int length = heights[i];
50

51
      if (next[i] == -1) next[i] = n;
52

53
      int breadth = next[i] - prev[i] - 1;
54
      int newArea = length * breadth;
55
      area = max(area, newArea);
56
    }
57
    return area;
58
  }
59

60
 public:
61
  int maximalRectangle(vector<vector<char>> &matrix) {
62
    int n = matrix.size();
63
    int m = matrix[0].size();
64
    int M[n][m];
65

66
    for (int i = 0; i < n; i++) {
67
      for (int j = 0; j < m; j++) {
68
        M[i][j] = matrix[i][j] - '0';
69
      }
70
    }
71

72
    // step 1 : compute area of 1st row
73
    int area = largestRectangleArea(M[0], m);
74

75
    for (int i = 1; i < n; i++) {
76
      for (int j = 0; j < m; j++) {
77
        // step 2 : add upar wala element if it is 1
78
        if (M[i][j] != 0)
79
          M[i][j] = M[i][j] + M[i - 1][j];
80

81
        else
82
          M[i][j] = 0;
83
      }
84

85
      area = max(area, largestRectangleArea(M[i], m));
86
    }
87
    return area;
88
  }
89
};