codingPractice/maximalRectangle.js at master · Abhas-Bhatnagar/codingPractice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * @param {character[][]} matrix
 * @return {number}
 */
function histogramMaxArea(heights) {
    let prevSmallElementArr = [];
    let stack = [];
    for(let itr = 0; itr < heights.length; itr++) {
        while(stack.length && heights[stack[stack.length-1]] >=  heights[itr]){
            stack.pop();
        }
        if(stack.length == 0) {
            prevSmallElementArr.push(-1 + 1);
        } else {
            prevSmallElementArr.push(stack[stack.length-1] + 1);
        }
        stack.push(itr);
    }
  //  console.log(prevSmallElementArr);
    let nextSmallerElementArr = [];
    stack = [];
    for(let itr = heights.length-1; itr >= 0; itr--) {
        while(stack.length && heights[stack[stack.length-1]] >=  heights[itr]){
            stack.pop();
        }
        if(stack.length == 0) {
            nextSmallerElementArr.push(heights.length-1);
        } else {
            nextSmallerElementArr.push(stack[stack.length-1] - 1);
        }
        stack.push(itr);
    }
    nextSmallerElementArr.reverse()
   // console.log(nextSmallerElementArr);
    let maxArea = 0;
    for(let itr = 0; itr < heights.length; itr++) {
        let area = heights[itr] * ( nextSmallerElementArr[itr] - prevSmallElementArr[itr] +1 );
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}
var maximalRectangle = function(matrix) {

    let heights = [];
    for(let itrCol = 0 ; itrCol < matrix[0].length; itrCol++) {
        heights.push(matrix[0][itrCol]);
    }
    let maxArea = histogramMaxArea(heights);
    for(let itrRow = 1 ; itrRow < matrix.length; itrRow++) {
        for(let itrCol = 0 ; itrCol < matrix[0].length; itrCol++) {
            let value = matrix[itrRow][itrCol];
            if(value == 0) {
                heights[itrCol] = 0;
            } else {
                heights[itrCol]++;
            }
        }
        let area = histogramMaxArea(heights);
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
};
//https://leetcode.com/problems/maximal-rectangle/