3380. Maximum Area Rectangle With Point Constraints I - Detailed Explanation

Problem Statement

You are given:

• Two integers, width and height, representing the dimensions of a rectangle. The rectangle's bottom-left corner is at (0, 0) and its top-right corner is at (width, height).

• A list of points, where each point is represented as (x, y). Each point lies strictly inside the rectangle (i.e., 0 < x < width and 0 < y < height).

Your goal is to determine the area of the largest axis-aligned rectangle (with sides parallel to the axes) that can be chosen inside the given rectangle such that no point lies strictly inside the chosen rectangle (points are allowed on the boundary).

Example 1

• Input: width = 5, height = 5, points = [(2, 2)]
• Output: 15
• Explanation: One optimal solution is to take the rectangle with corners at (0, 2) and (5, 5). The point (2, 2) lies exactly on the bottom boundary, which is allowed. Its area is 5 × 3 = 15.

Example 2

• Input: width = 10, height = 8, points = [(4, 3), (6, 5)]
• Output: 32
• Explanation: An optimal rectangle is from (0, 0) to (4, 8) with an area of 4 × 8 = 32. Here, (4, 3) lies on the right boundary and (6, 5) is outside the rectangle.

Example 3

• Input: width = 8, height = 8, points = [(1, 1), (3, 7), (7, 4)]
• Output: 20
• Explanation: One optimal rectangle is from (3, 4) to (8, 8). All points lie either on the boundary or outside this rectangle, and its area is 5 × 4 = 20.

Constraints

• 1 ≤ width, height ≤ 10⁹
• 0 ≤ number of points ≤ 10⁵
• For every point (x, y): 0 < x < width and 0 < y < height
• All points are distinct

Hints

• Boundary Alignment: Notice that the optimal rectangle's boundaries will always align with either the rectangle’s borders (0 or width/height) or with one of the given point’s coordinates.
• Candidate Rectangles: Only candidate rectangles with boundaries from {0} ∪ {each point’s coordinate} ∪ {width or height} need to be considered.
• Validation: A candidate rectangle is valid if no point lies strictly inside it (points on the boundary are allowed).

Approaches

Brute Force Approach

Idea

• Candidate Boundaries: Create candidate rectangles by choosing two distinct x-coordinates and two distinct y-coordinates from the set consisting of the rectangle’s borders and all the point coordinates.
• Validation: For each candidate rectangle, check if any point lies strictly inside (i.e., if x_left < x < x_right and y_bottom < y < y_top).
• Area Calculation: If the candidate is valid, compute its area and update the maximum area found.

Step-by-Step Walkthrough

1. Collect Unique Boundaries:
   • x boundaries: {0} ∪ {each point’s x} ∪ {width}
   • y boundaries: {0} ∪ {each point’s y} ∪ {height}
2. Enumerate Candidates:
   For every pair of x boundaries and every pair of y boundaries:
   • Check every point to see if it lies strictly within the candidate rectangle.
   • If valid, calculate the area: (x_right - x_left) * (y_top - y_bottom) and update the maximum.
3. Return the Maximum Area.

Complexity Analysis

• Let Uₓ be the number of unique x boundaries and Uᵧ be the number of unique y boundaries.
• There are O(Uₓ² × Uᵧ²) candidate rectangles.
• Checking each candidate against n points gives a worst-case complexity of O(Uₓ² × Uᵧ² × n).
• This method is practical for small input sizes but becomes inefficient as the number of points increases.

Brute Force – Python Code