Stokastik

Machine Learning, AI and Programming

LeetCode : Largest Rectangle in Histogram

Problem Statement

Solution :

At first glance, one can say that a brute force approach would take O(N^2) time complexity. That is correct. Let me begin first with the brute force approach explanation. In order to find the largest rectangle possible, scan each of the unit one rectangle (i.e. the heights given in the input array) and then for each such rectangle i compute the maximum possible width it can be extended towards the left and the right side. When I say can be extended towards left or right side, I mean that we do not encounter any rectangle with smaller height than the current rectangle. The maximum width possible for this rectangle of height h[i], is :

width = w_left[i] + w_right[i] - 1

Area = h[i] * (w_left[i] + w_right[i] - 1)

Subtracting 1 because the width of the current rectangle i is counted twice, once in w_left[i] and once in w_right[i]. For example, given the following histogram :

Source : LeetCode

For i = 0, the height of rectangle is h[0] = 2. It cannot be extended to left, and also cannot be extended towards right because the next rectangle h[1] = 1 has height less than 2. So w_left[0] = 1 and w_right[0] = 1, and thus area = 2 * (1 + 1 - 1) = 2.

Similarly for i = 1, the height of rectangle is h[0] = 1. This rectangle can be extended towards left till h[0] because h[0] = 2 is greater than h[1] = 1. Similarly, it can also be extended towards right till the end, because all rectangles towards right h[2:6] is greater in height than h[1] = 1. Thus w_left[1] = 2, w_right[1] = 5, and area = 1 * (2 + 5 - 1) = 6.

For h[2] = 5, w_left[2] = 1 (because h[1] = 1 < 5) and w_right[2] = 2 (because h[3] = 6 > 5, but h[4] = 2 < 5), thus area = 5 * (1 + 2 - 1) = 10. This is the largest area of rectangle possible among all rectangles.

Coding the solution in python :

class Solution(object):
def largestRectangleArea(self, heights):
if len(heights) == 0:
return 0
maximum_area = -float("Inf")
for idx in range(len(heights)):
height = heights[idx]
w_left, w_right = 1, 1
for left_idx in reversed(range(idx)):
if heights[left_idx] >= height:
w_left += 1
else:
break
for right_idx in range(idx + 1, len(heights)):
if heights[right_idx] >= height:
w_right += 1
else:
break
area = height * (w_left + w_right - 1)
maximum_area = max(maximum_area, area)
return maximum_area

Clearly, the time complexity is O(N^2).

Can we do better ? Can we somehow reduce our scan towards the left and right side by using some observations ?

Note that, on either side of a rectangle, we scan till we find a rectangle of smaller height than the current rectangle. Take the scenario for the left side first. For each height h[i], we maintain a running array, increasing_heights[], which stores all the heights, seen in non-decreasing order till i - 1 on the left side, then we can do a binary search on this array to find the point :

0 <= p <= i - 1 such that h[p] < h[i]

Once we get this point, we can compute the maximum width possible w_left[i] = i - p, for the current rectangle using the same method as shown above. Let's take the example of h[4] = 2. When we reach h[4], the increasing_heights array will contain the elements [1, 5, 6]. Using binary search we will find the point p = 1 (h[1] = 1). Then w_left[4] = 4 - 1 = 3.

But what about the increasing_heights[] array ?

To maintain the non-decreasing property of the increasing_heights[] array, we remove all the entries from p + 1 to i - 1, that has heights greater than h[i] and then insert the new height h[i] into the increasing_heights[] array. This restores the property of the increasing_heights array and we can continue the scan for the next height. Similar approach will also be used for the right side of the current rectangle i, to find the widths w_right[i].

This approach solves the problem in O(N*log(N)) time complexity.

Below is the python code to do the same :

class Solution(object):
def get_lower_height_index(self, increasing_heights, curr_height):
left, right = 0, len(increasing_heights) - 1
while left <= right:
mid = int((left + right) / 2)
if increasing_heights[mid][0] <= curr_height:
left = mid + 1
else:
right = mid - 1
return left - 1
def largestRectangleArea_w(self, heights):
increasing_heights = []
widths = [0] * len(heights)
for idx in range(len(heights)):
height = heights[idx]
if idx == 0:
increasing_heights.append((height, 0))
else:
if height >= heights[idx - 1]:
increasing_heights.append((height, idx))
else:
lower_index = self.get_lower_height_index(increasing_heights, height)
for pos in range(lower_index + 1, len(increasing_heights)):
width = increasing_heights[-1][1] - increasing_heights[pos][1] + 1
widths[increasing_heights[pos][1]] += width
increasing_heights = increasing_heights[:lower_index + 1]
increasing_heights.append((height, idx))
for pos in range(len(increasing_heights)):
width = increasing_heights[-1][1] - increasing_heights[pos][1] + 1
widths[increasing_heights[pos][1]] += width
return widths
def largestRectangleArea(self, heights):
if len(heights) == 0:
return 0
w_left = self.largestRectangleArea_w(heights)
w_right = self.largestRectangleArea_w(heights[::-1])[::-1]
w = [w_left[x] + w_right[x] - 1 for x in range(len(a))]
areas = [heights[idx] * w[idx] for idx in range(len(heights))]
return max(areas)

Instead of separately computing the widths w_left and w_right, we use the same function that scans the left side, but by reversing the array.

Note that in the function 'largestRectangleArea_w' it might look that we are running one for loop for increasing_heights, inside another for-loop and that the time complexity is O(N^2). But in reality, each element h[i] is either inserted into increasing_heights or deleted from increasing_heights or both,

i.e. on each h[i] we are doing maximum of 2 operations, i.e. the complexity is O(2N*log(N)) which is O(N*log(N)). Try to convince yourself.

Categories: PROBLEM SOLVING

Tags: , , , ,