939. Minimum Area Rectangle - Detailed Explanation

Problem Statement

You are given an array of points where each point is represented as [x, y]. The task is to find the minimum area of a rectangle formed by any four points from the list such that the rectangle’s sides are parallel to the x- and y-axes. If no rectangle can be formed, return 0.

Example 1

• Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
• Output: 4
• Explanation:
  The rectangle is formed by points (1,1), (1,3), (3,1), and (3,3). Its area is calculated as:
  [ \text{Area} = (3-1) \times (3-1) = 4 ]

Example 2

• Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
• Output: 2
• Explanation:
  Although one rectangle formed by (1,1), (1,3), (3,1), and (3,3) has area 4, a smaller rectangle is formed by (3,1), (3,3), (4,1), and (4,3). Its area is:
  [ \text{Area} = (4-3) \times (3-1) = 2 ]

Example 3

• Input: [[7,8],[7,10],[9,8],[9,10],[8,9]]
• Output: 4
• Explanation:
  The rectangle formed by (7,8), (7,10), (9,8), and (9,10) has an area of:
  [ \text{Area} = (9-7) \times (10-8) = 4 ]

Constraints

• The number of points is relatively small (e.g., between 1 and 500).
• Each point’s coordinate is an integer.
• All points are unique.
• Rectangle sides must be parallel to the axes.

Hints to Guide Your Approach

1. Axis-aligned Property:
   Since the rectangle must have sides parallel to the axes, a valid rectangle is fully determined by two distinct x-coordinates and two distinct y-coordinates. Think about how you can use pairs of x-coordinates (or y-coordinates) to define the boundaries.

2. Using a Set or Dictionary:
   To quickly check if a particular point exists, consider storing all points in a set (or a dictionary mapping x to a list of y values). This can help you verify the existence of the other two points that would complete a rectangle when you pick a pair of points.

Approaches to Solve the Problem

Approach 1: Brute Force Using Set Membership

Explanation

• Idea:
  Iterate through every pair of points. For each pair that has different x and y coordinates (so they can be diagonal corners), check whether the other two corresponding points exist in the set.

• Key Steps:

  1. Store all points in a set for constant-time lookups.
  2. For every pair (p1, p2) with p1 = (x1, y1) and p2 = (x2, y2), if x1 != x2 and y1 != y2, check if both (x1, y2) and (x2, y1) exist.
  3. If they do, calculate the area and update the minimum found so far.
  4. Return 0 if no rectangle is found.

Complexity Analysis

• Time Complexity: O(n²) – each pair of points is considered.
• Space Complexity: O(n) – for storing points in a set.

Visual Example

Imagine the points:

(1,1)    (3,1)
  ·--------·
  |        |
  |        |
  ·--------·
(1,3)    (3,3)

When you pick (1,1) and (3,3), you check for (1,3) and (3,1). Both exist, so you calculate the area as (3-1) * (3-1) = 4.

Approach 2: Optimal Approach Using Dictionary of Columns

Explanation

• Idea:
  Group points by their x-coordinate. For each x-column, sort the y-coordinates. Then, for each pair of y-coordinates in the same column, record the last x-coordinate seen for that pair. When the same y-pair appears in a new column, you have the potential to form a rectangle.

• Key Steps:

  1. Build a dictionary where each key is an x-coordinate and the corresponding value is a sorted list of y-coordinates.
  2. Use another dictionary to remember the last x-coordinate where a particular pair of y-coordinates was seen.
  3. For each x-coordinate (in sorted order) and for each pair (y1, y2) in that column, if the pair was seen before, calculate the area using the difference between the current x and the previous x.
  4. Update the minimum area accordingly.

Complexity Analysis

• Time Complexity:
  • Grouping points: O(n)
  • For each x, if there are k y-coordinates, checking each pair is O(k²). In the worst-case (many points with the same x), the overall time is O(n²), which is acceptable for n ≤ 500.
• Space Complexity: O(n) for the dictionaries.

Visual Example

Imagine two vertical columns:

• Column at x = 1 has y-coordinates [1, 3]
• Column at x = 3 has y-coordinates [1, 3]

For the pair (1, 3), record that it was seen at x = 1. When processing column x = 3, the pair (1, 3) is seen again, so calculate the area as: [ \text{Area} = (3 - 1) \times (3 - 1) = 4 ]

Detailed Code Implementations

Python Code

Below are both the brute force and optimal implementations in Python.