Menu
I have an array of points, and my goal is to pick two so that I maximize the area of the rectangle formed by the two points (one representing the low left corner and the other one the right top corner).
I could do this in O(n^2) by just doing two for loops and calculating every single possible area, but I think there must be a more efficient solution:
max_area = 0
for p1 in points:
for p2 in points:
area = p2[0]p2[1] + p1[0]p1[1] - p2[1]p1[0] - p2[0]p1[1]
if area > max_area:
max_area = area
It's clear that I want to maximize the area of the second point with the origin (0,0) (so p2[0]p2[1]), but I'm not sure how to go forward with that.
887
Approach 2: Divide and Conquer The rectangle with the widest possible width and height equal to the shortest bar. The area of the rectangle formed on the left side of the minimum height. The area of the rectangle formed on the right side of the minimum height.
Let the upper right corner of the rectangle has co-ordinates (x, y), Then the area of rectangle, A = 4*x*y. Setting this to 0 and simplifying, we have y2 = b2x2/a2. Thus, y2=b2 – y2, 2y2=b2, and y2b2 = 1/2.
Finally, the area for the histogram equation is calculated by adding the product of all the frequency density and their corresponding class width.
The task is to find the area of the largest rectangle that can be formed using these coordinates. Print 0 if no rectangle can be formed. Explanation: The largest rectangle possible is { (1, 0), (1, 1), (4, 0), (4, 1)}. Explanation: No rectangle can be formed. Therefore, the answer is zero.
We know that the maximal rectangle must be one of the rectangles constructed in this manner (the max rectangle must have a point on its base where the next filled square is height above that point). These three variables uniquely define the rectangle at that point. We can compute the area of this rectangle with h * (r - l).
The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red) Recommended: Please solve it on “ PRACTICE ” first, before moving on to the solution.
For simplicity, assume that all bars have same width and the width is 1 unit. For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)
Yes, there's an O(n log n)-time algorithm (that should be matched by an element distinctness lower bound).
It suffices to find, for each p1, the p2 with which it has the largest rectangular area, then return the overall largest. This can be expressed as a 3D extreme point problem: each p2 gives rise to a 3D point (p2[0], p2[1], p2[0] p2[1]), and each p1 gives rise to a 3D vector (-p1[0], -p1[1], 1), and we want to maximize the dot product (technically plus p1[0] p1[1], but this constant offset doesn't affect the answer). Then we "just" have to follow Kirkpatrick's 1983 construction.
194
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
