1077MediumArrayHash TableMathGeometrySorting

The Smallest Upright Frame

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Pins are placed at the positions pins, where pins[i] = [x, y], and no two pins share a position.

A frame is a rectangle whose four corners are pins and whose sides run parallel to the axes.

Return the smallest area any frame encloses, or 0 when no four pins form one.

Examples

Example 1

Input: pins = [[0, 0], [0, 2], [2, 0], [2, 2]]
Output: 4

The four pins are the corners of a square two wide and two tall, enclosing four.

Example 2

Input: pins = [[0, 0], [1, 1]]
Output: 0

Two pins cannot make four corners, so there is no frame at all.

Example 3

Input: pins = [[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]]
Output: 1

Three columns each hold a pin at both heights, and the closest two columns are one apart, giving a frame one wide and one tall.

Constraints

1 <= pins.length <= 500
pins[i].length == 2
0 <= pins[i][0] <= 40000
0 <= pins[i][1] <= 40000
No two pins share a position.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_area_rect(pins: list[list[int]]) -> int:

Java

public int minAreaRect(int[][] pins)

The intended approach

Time O(n^2) at worst over the pairs of heights within columns.Space O(n^2) at worst for the remembered pairs.

A frame is settled by its left and right columns and its bottom and top rows, so its left column holds two pins at the frame's two heights and its right column holds two pins at those same heights. So group the pins by column and sweep the columns from left to right. Within a column, take every pair of heights it holds and remember, for each such pair, the most recent column that also held it. Meeting that pair again gives a frame at once: its width is the gap between the two columns and its height the gap between the two heights. Remembering only the most recent column is enough, because a nearer partner always gives a narrower frame for the same pair of heights, and the height is fixed by the pair. Reporting nothing when no pair is ever met twice is the case with no frame at all.

Pythonentry point: min_area_rect

def min_area_rect(pins):
    by_column = {}
    for pin in pins:
        by_column.setdefault(pin[0], []).append(pin[1])
    seen = {}
    best = None
    for column in sorted(by_column):
        heights = sorted(by_column[column])
        for i in range(len(heights)):
            for j in range(i + 1, len(heights)):
                key = (heights[i], heights[j])
                if key in seen:
                    area = (column - seen[key]) * (heights[j] - heights[i])
                    if best is None or area < best:
                        best = area
                seen[key] = column
    return 0 if best is None else best

The obvious version

Try every ordered pair of pins as the bottom-left and top-right corners of a frame, and check whether the other two corners are pins too by looking them up in a set of all the positions. Keep the smallest area found. Costs every pair of pins rather than a sweep by column.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_area_rect(pins):
    have = set()
    for pin in pins:
        have.add((pin[0], pin[1]))
    best = None
    n = len(pins)
    for i in range(n):
        for j in range(n):
            x1 = pins[i][0]
            y1 = pins[i][1]
            x2 = pins[j][0]
            y2 = pins[j][1]
            if x1 >= x2 or y1 >= y2:
                continue
            if (x1, y2) in have and (x2, y1) in have:
                area = (x2 - x1) * (y2 - y1)
                if best is None or area < best:
                    best = area
    return 0 if best is None else best

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in