LeetCode 492 - Construct the Rectangle

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem gives us a single integer, area, which represents the area of a rectangle. Our task is to find two integers:

L, the length
W, the width

such that:

L * W == area
L >= W
L - W is as small as possible

In other words, among all valid factor pairs of area, we want the pair that is closest together.

For example, if area = 36, the possible factor pairs are:

(36, 1)
(18, 2)
(12, 3)
(9, 4)
(6, 6)

The pair (6, 6) has the smallest difference between the two values, so it is the optimal answer.

The input is a single positive integer between 1 and 10^7. This upper bound is important because it tells us that a naive approach checking every possible number up to area could still work in theory, but there is a much more efficient mathematical observation available.

The expected output is an array [L, W] containing the chosen dimensions in that order.

Several edge cases are important:

When area is a perfect square, the optimal rectangle is a square itself.
When area is prime, the only valid dimensions are [area, 1].
When area = 1, the answer is [1, 1].

The problem guarantees that the input is always a positive integer, so we do not need to handle invalid or negative values.

Approaches

Brute Force Approach

The most direct solution is to check every possible width from 1 up to area.

For each candidate width W:

Check whether area % W == 0
If it divides evenly, compute L = area // W
Ensure L >= W
Track the pair with the smallest difference

This approach is correct because it evaluates every possible factor pair and therefore cannot miss the optimal answer.

However, it is inefficient because it may perform up to area iterations. Since area can be as large as 10^7, this becomes unnecessarily expensive.

Key Insight for the Optimal Solution

The important mathematical observation is that the factor pair with the smallest difference is always the pair closest to the square root of the number.

Consider a rectangle with area A.

If:

$$L \times W = A$$

then:

When W is small, L becomes very large
As W approaches sqrt(A), the two values become closer together

Therefore, instead of searching from 1 upward, we can start from:

$$\lfloor \sqrt{A} \rfloor$$

and move downward until we find the first divisor.

The first divisor we encounter gives the optimal pair immediately because it is the closest factor to the square root.

For example, with area = 122122:

$$\sqrt{122122} \approx 349$$

We start checking downward from 349 until we find a divisor:

286 divides evenly
122122 / 286 = 427

So the answer is [427, 286].

This reduces the time complexity from O(area) to O(sqrt(area)).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(area)	O(1)	Checks every possible divisor
Optimal	O(sqrt(area))	O(1)	Starts near square root and finds closest factor pair

Algorithm Walkthrough

Compute the integer square root of area.

The square root represents the point where the rectangle dimensions are closest together. Starting here maximizes the chance of finding the optimal factor pair quickly. 2. Iterate downward from the square root to 1.

For each candidate width W, check whether area % W == 0. 3. When a divisor is found, compute:

$$L = \frac{area}{W}$$

Since we are searching downward from the square root, this is the factor pair with the smallest possible difference. 4. Return [L, W].

The problem guarantees at least one valid pair because every positive integer is divisible by 1.

Why it works

The algorithm relies on the fact that factor pairs become farther apart as we move away from the square root. By starting at the square root and searching downward, the first divisor found necessarily produces the closest factor pair. Since L * W = area and W <= sqrt(area) <= L, the returned pair satisfies all problem requirements.

Python Solution

from typing import List
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]

The implementation begins by computing the integer square root of area. This gives the largest possible candidate width that could produce the minimum difference between dimensions.

The while loop moves downward until it finds a divisor of area. Because we search from the square root downward, the first valid divisor is automatically the optimal width.

After finding the width, the corresponding length is computed using integer division. The method finally returns [length, width].

The solution uses constant extra space and performs at most sqrt(area) iterations.

Go Solution

package main

import "math"

func constructRectangle(area int) []int {
	width := int(math.Sqrt(float64(area)))

	for area%width != 0 {
		width--
	}

	length := area / width

	return []int{length, width}
}

The Go implementation follows the same logic as the Python version. The main difference is that Go's math.Sqrt function operates on float64, so we convert the integer before taking the square root and then cast the result back to int.

The result is returned as a slice of integers using []int{length, width}.

Because the input constraint is only 10^7, integer overflow is not a concern in Go for standard int types.

Worked Examples

Example 1

Input:

area = 4

Initial square root:

$$\sqrt{4} = 2$$

Step	width	area % width	Action
1	2	0	Divisor found

Now compute:

$$length = 4 / 2 = 2$$

Return:

[2, 2]

Example 2

Input:

area = 37

Initial square root:

$$\sqrt{37} \approx 6$$

Step	width	area % width	Action
1	6	1	Decrement
2	5	2	Decrement
3	4	1	Decrement
4	3	1	Decrement
5	2	1	Decrement
6	1	0	Divisor found

Now compute:

$$length = 37 / 1 = 37$$

Return:

[37, 1]

Example 3

Input:

area = 122122

Initial square root:

$$\sqrt{122122} \approx 349$$

The algorithm checks downward until it reaches 286.

Step	width	area % width	Action
...	...	...	Continue searching
Final	286	0	Divisor found

Now compute:

$$length = 122122 / 286 = 427$$

Return:

[427, 286]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(sqrt(area))	At worst, we search downward from the square root to 1
Space	O(1)	Only a few integer variables are used

The key improvement comes from limiting the search space to values near the square root. Since factors always occur in pairs, checking beyond the square root would duplicate work.

The algorithm stores only a constant number of variables regardless of input size, so the space complexity remains constant.

Test Cases

from typing import List
import math

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

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

        return [area // width, width]

solution = Solution()

assert solution.constructRectangle(4) == [2, 2]       # perfect square
assert solution.constructRectangle(37) == [37, 1]     # prime number
assert solution.constructRectangle(122122) == [427, 286]  # large composite number
assert solution.constructRectangle(1) == [1, 1]       # minimum input
assert solution.constructRectangle(2) == [2, 1]       # smallest non-square
assert solution.constructRectangle(36) == [6, 6]      # larger perfect square
assert solution.constructRectangle(45) == [9, 5]      # uneven factor pair
assert solution.constructRectangle(10000000) == [3200, 3125]  # upper constraint stress test

Test	Why
`area = 4`	Validates perfect square handling
`area = 37`	Validates prime number behavior
`area = 122122`	Tests large composite input
`area = 1`	Tests minimum boundary
`area = 2`	Tests smallest non-square value
`area = 36`	Ensures exact square pair is returned
`area = 45`	Verifies closest factor pair selection
`area = 10000000`	Stress test near upper constraint

Edge Cases

Perfect Square Inputs

When the area is a perfect square, the optimal rectangle is a square itself. A buggy implementation might continue searching unnecessarily or return reversed dimensions.

For example:

area = 36

The algorithm starts at sqrt(36) = 6, immediately finds a divisor, and returns [6, 6].

Prime Numbers

Prime numbers only have two divisors: 1 and themselves. A naive implementation might incorrectly assume a larger factor pair exists.

For example:

area = 37

The algorithm checks downward from 6 until it reaches 1, producing [37, 1], which is the only valid rectangle.

Minimum Input Value

The smallest allowed input is:

area = 1

Some implementations fail here because they assume the width search starts from at least 2.

This solution correctly computes:

$$\sqrt{1} = 1$$

Since 1 % 1 == 0, it immediately returns [1, 1].