#939

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Area Rectangle

Find the minimum area of a rectangle formed by given points on a 2D plane with sides parallel to axes.

Problem Statement

You are given an array of points on a 2D plane, where each point is represented as a pair of integers. You need to find the minimum area of a rectangle formed by these points with sides parallel to the X and Y axes. If no such rectangle can be formed, return 0.

For example, given the points [[1,1],[1,3],[3,1],[3,3],[2,2]], a rectangle can be formed between the points (1,1), (1,3), (3,1), and (3,3). The minimum area of the rectangle is 4. Your solution should consider efficient strategies for finding the rectangle with minimal area.

Examples

Example 1

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output: 4

Example details omitted.

Example 2

Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]

Output: 2

Example details omitted.

Constraints

1 <= points.length <= 500
points[i].length == 2
0 <= xi, yi <= 4 * 104
All the given points are unique.

Solution Approach

Array Scanning and Hash Lookup

First, scan through all point pairs, checking if two points can form a diagonal of a rectangle. Use a hash table to store all points for fast lookups. If both diagonal points are found, calculate the area of the rectangle.

Efficient Rectangle Area Calculation

For each valid rectangle, calculate the area using the formula (width * height) and track the minimum area. Update the result when a smaller area is found.

Avoiding Duplicate Rectangles

Since the points are unique, you don't need to worry about duplicates. However, make sure to consider only the pairs that form valid rectangles, avoiding any unnecessary checks for invalid configurations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach, but an optimized solution with hash lookups and array scanning can bring it down to O(n^2), where n is the number of points. Space complexity is O(n) due to the hash table used for fast lookups.

What Interviewers Usually Probe

Assessing the candidate's understanding of hashing and geometric properties of the points.
Check if the candidate efficiently handles the edge case of no valid rectangle being possible.
Determine if the candidate can optimize time complexity and avoid unnecessary computations.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly check for diagonal corners forming a valid rectangle.
Overcomplicating the solution by not using hash lookups to speed up the search.
Not considering the case where no rectangle can be formed, which should return 0.

Follow-up variants

Finding the largest area rectangle instead of the smallest.
Handling different sets of points with varying coordinates for efficiency.
Implementing the algorithm with a different data structure (e.g., sorted arrays instead of hash tables).

FAQ

What is the minimum area rectangle problem in LeetCode?

The Minimum Area Rectangle problem asks you to find the smallest rectangle formed by given points on a 2D plane, with sides parallel to the axes.

How does array scanning help in the Minimum Area Rectangle problem?

Array scanning helps by iterating over pairs of points to identify possible diagonal corners of a rectangle, optimizing the search process.

What is the role of hash lookup in the Minimum Area Rectangle problem?

Hash lookup speeds up the process of checking if the other diagonal corners of a rectangle exist, reducing the time complexity of the solution.

How do you avoid unnecessary computations in this problem?

By using a hash table to check for valid rectangle corners, you can avoid repeatedly scanning all points, improving efficiency.

What is the time complexity of the Minimum Area Rectangle problem?

The optimized time complexity is O(n^2), where n is the number of points, due to the need to check pairs of points for potential diagonals.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        d = defaultdict(list)
        for x, y in points:
            d[x].append(y)
        pos = {}
        ans = inf
        for x in sorted(d):
            ys = d[x]
            ys.sort()
            n = len(ys)
            for i, y1 in enumerate(ys):
                for y2 in ys[i + 1 :]:
                    if (y1, y2) in pos:
                        ans = min(ans, (x - pos[(y1, y2)]) * (y2 - y1))
                    pos[(y1, y2)] = x
        return 0 if ans == inf else ans

Continue Practicing

#710 random pick with blacklist #268 missing number #954 array of doubled pairs