What is an O(n) algorithm for finding bottom largest square?

Revision en2, by duckladydinh, 2021-01-30 21:47:19


Recently I came across a problem like this:

Given h[1..n] where h[i] denotes the height of column i, find the largest x such that there exists some i where h[i..i+x-1] >= x.

The best I could think of is O(nlogn): binary search for the value of x and do a linear check. However, this problem reminds me of finding the largest rectangle which could be done in O(n). So I wonder if there also exists a linear solution to this problem?



  Rev. Lang. By When Δ Comment
en2 English duckladydinh 2021-01-30 21:47:19 2 Tiny change: 'i..i+x-1] <= x.\n\nTh' -> 'i..i+x-1] >= x.\n\nTh'
en1 English duckladydinh 2021-01-30 21:01:25 516 Initial revision (published)