Category: math_and_geometry
-
LeetCode 3380: Maximum Area Rectangle With Point Constraints I
link For each pair of points we consider one as top-left (A) and the other as bottom-right (C) corner of an axis-aligned rectangle. Then, we try finding B and D. Once we have found all four corners, we check if other points lie on the rectangle, if not, we include it in max area computation.…
-
LeetCode 3102: Minimize Manhattan Distances
link Exclude each point We can find the max distance between pairs of points excluding each point and take the minimum. Time: , space: . Extreme points We want to remove one of the “extreme points” because extreme points are the furthest apart from each other. Say we have a pair of points: . The…
-
LeetCode 469. Convex Polygon
link For a not-convex polygon, the direction of travel changes: say, clockwise to counter-clockwise. If we have three consecutive points , the sign of the cross product between the two consecutive vectors: and gives us the direction of travel. If the direction changes, we declare the polygon to be not-convex. Time: , space: .
-
LeetCode 939: Minimum Area Rectangle
link For each pair of points we want to consider one as the top-left and the other as the bottom-right. Then, we want to find the other two corners: top-right and bottom-left. Since left two corners must have smaller x-coordinates than the right two corners, we first sort the points by x-coordinate. This reduces the…
-
LeetCode 7: Reverse Integer
link Like in atoi, we detect if there will be an overflow or an underflow before including the next digit. Time: , space: .
-
LeetCode 593: Valid Square
link We check side lengths and perpedicularity like below: Time: , space: .
-
LeetCode 2481: Minimum Cuts to Divide a Circle
link Each full cut adds two more regions. So, for even n’s we can use full cuts. For example, when n = 4, we have two full cuts which can be thought of as four aligned half-cuts. To go from n = 4 to n = 5, we need to adjust the angles between these…
-
LeetCode 1232: Check If It Is a Straight Line
link Say the line has slope . If a point’s slope with a point on the line is , the new point is also on the line. For each pair of consecutive points we check if they have the same slope. With points, time: , space: .
unreasonably effective 