LeetCode 492: Construct the Rectangle

Problem Restatement

We are given a positive integer area.

We need to find two positive integers:

They must satisfy three rules:

Return:

[L, W]

The constraint is 1 <= area <= 10^7.

Input and Output

Function shape:

def constructRectangle(area: int) -> list[int]:
    ...

Examples

Example 1:

area = 4

Possible factor pairs are:

1 * 4
2 * 2
4 * 1

The pair [1, 4] is invalid because L < W.

Between [2, 2] and [4, 1], the pair [2, 2] has the smaller difference.

Answer:

[2, 2]

Example 2:

area = 37

37 is prime, so the only valid rectangle is:

37 * 1

Answer:

[37, 1]

Example 3:

area = 122122

The optimal dimensions are:

[427, 286]

First Thought: Check Every Width

A direct solution is to try every possible width from 1 to area.

Whenever width divides area, compute:

length = area // width

Then keep the valid pair with the smallest difference.

class Solution:
    def constructRectangle(self, area: int) -> list[int]:
        best = [area, 1]

        for width in range(1, area + 1):
            if area % width != 0:
                continue

            length = area // width

            if length >= width and length - width < best[0] - best[1]:
                best = [length, width]

        return best

This works, but it checks too many values.

Problem With Brute Force

The brute force loop may check up to area values.

Since area can be as large as 10^7, this is still possible but wasteful.

We can use the structure of factor pairs to search much less.

Key Insight

To minimize L - W, the rectangle should be as close to a square as possible.

A square with area area would have side length:

sqrt(area)

So the best width should be the largest divisor of area that is less than or equal to sqrt(area).

Why?

If W is larger, then L = area / W becomes smaller than W, violating L >= W.

So valid widths only need to be checked from:

floor(sqrt(area)) down to 1

The first divisor found gives the largest possible width, and therefore the smallest difference between L and W.

Algorithm

1. Start with:

width = int(sqrt(area))

2. While width does not divide area, decrement it:

width -= 1

3. Once width divides area, compute:

length = area // width

4. Return:

[length, width]

Correctness

Every valid rectangle corresponds to a factor pair:

L * W = area

with:

L >= W

This implies:

W <= sqrt(area)

because if W > sqrt(area), then L = area / W < sqrt(area), so L < W.

Therefore, every valid width is at most floor(sqrt(area)).

The algorithm checks possible widths from floor(sqrt(area)) downward. The first width that divides area is the largest valid width.

For fixed area, increasing W while keeping L * W = area makes L smaller and brings the two sides closer together. Therefore, the largest valid width gives the minimum possible difference L - W.

Thus the returned pair satisfies the area rule, the order rule, and the minimum difference rule.

Complexity

Implementation

import math

class Solution:
    def constructRectangle(self, area: int) -> list[int]:
        width = int(math.sqrt(area))

        while area % width != 0:
            width -= 1

        length = area // width
        return [length, width]

Code Explanation

Start near the square shape:

width = int(math.sqrt(area))

If area is a perfect square, this width immediately works.

Otherwise, move downward until we find a divisor:

while area % width != 0:
    width -= 1

Once we have the best width, compute the matching length:

length = area // width

Then return the dimensions in the required order:

return [length, width]

Testing

def run_tests():
    s = Solution()

    assert s.constructRectangle(4) == [2, 2]
    assert s.constructRectangle(37) == [37, 1]
    assert s.constructRectangle(122122) == [427, 286]
    assert s.constructRectangle(1) == [1, 1]
    assert s.constructRectangle(12) == [4, 3]
    assert s.constructRectangle(16) == [4, 4]

    print("all tests passed")

run_tests()

Test meaning: