please check out my final project and notify me if there is any efficient way to solve the problemproject
This can be done in
O(n) time complexity, where
n is the number of elements in the matrix, using the following algorithm.
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Step 1: Take row 0 and find the maximum area
1 0 1 0 0 maximum area = 1
For each of the remaining rows,
calculate the size of the histogram and find the max area in the histogram,
if greater than the overall maximum area, then set maximum area to area
row 1 histogram 2 0 2 1 1 area = 3, maximum area becomes 3
row 2 histogram 3 1 3 2 2 area = 6, maximum area becomes 6
row 3 histogram 4 0 0 3 0 area = 4, maximum area remains 6
let m = number of row elements (number of columns of matrix)
to calculate the sizes of the histogram i need to traverse the previous row and current because if the current row value is zero at certain position the value of histogram should be zero irrespective of the previous row so i cant add both the prev and current rows…so ‘m’ times
and to calculate the areas of rectangle in the histogram we need m^2 time.
we need to check for certain histogram how many consecutive histograms are there with height greater than or equal to the current histogram. so a decrementing loop and incrementing loop traversing left and right of the current histogram from the position of the histogram both decrementing loop and incrementing loop runs in ‘m’ time because in the worst case if we are the center of histogram we need traverse m/2 to back(left) and m/2 to front(right). and we need to loop through all the histogram in row so ‘m*m’.
therefore for updating rows and finding areas of the row histograms it take m^3 time.
and we need to do this for all rows if n is number of rows in matrix then O(n*m^3) time complexity
if there is a better way can you please! provide me the code.
When updating the histogram for the rows you only need to traverse each row once. As you traverse the row, the value for the previous row is the current row index - 1 and the column index. Since the data structure is a matrix the time to access the elements is O(1) which means the overall complexity for traversing the row is still O(n) for that row.
You can solve the area of the histogram using the algorithm found here: Largest Rectangular Area in a Histogram | Set 2 - GeeksforGeeks which also has O(n) time complexity. You will end up traversing the row a maximum of 3 times which would be O(3n) which since BIgO notation ignores constants is still a complexity of O(n)