# LeetCode 492: Construct the Rectangle

## Problem Restatement

We are given a positive integer `area`.

We need to find two positive integers:

| Name | Meaning |
|---|---|
| `L` | Length |
| `W` | Width |

They must satisfy three rules:

| Rule | Meaning |
|---|---|
| `L * W == area` | The rectangle area must match exactly |
| `L >= W` | Length must be at least width |
| `L - W` is minimized | The rectangle should be as close to a square as possible |

Return:

```python
[L, W]
```

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `area` |
| Output | A list `[L, W]` |
| Area rule | `L * W == area` |
| Order rule | `L >= W` |
| Optimization rule | Minimize `L - W` |

Function shape:

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

## Examples

Example 1:

```python
area = 4
```

Possible factor pairs are:

```text
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:

```python
[2, 2]
```

Example 2:

```python
area = 37
```

`37` is prime, so the only valid rectangle is:

```text
37 * 1
```

Answer:

```python
[37, 1]
```

Example 3:

```python
area = 122122
```

The optimal dimensions are:

```python
[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:

```python
length = area // width
```

Then keep the valid pair with the smallest difference.

```python
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:

```text
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:

```text
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:

```python
width = int(sqrt(area))
```

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

```python
width -= 1
```

3. Once `width` divides `area`, compute:

```python
length = area // width
```

4. Return:

```python
[length, width]
```

## Correctness

Every valid rectangle corresponds to a factor pair:

```text
L * W = area
```

with:

```text
L >= W
```

This implies:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(sqrt(area))` | We may scan downward from `sqrt(area)` to `1` |
| Space | `O(1)` | Only a few integer variables are used |

## Implementation

```python
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:

```python
width = int(math.sqrt(area))
```

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

Otherwise, move downward until we find a divisor:

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

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

```python
length = area // width
```

Then return the dimensions in the required order:

```python
return [length, width]
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `4` | Perfect square example |
| `37` | Prime area |
| `122122` | Larger official example |
| `1` | Smallest area |
| `12` | Best pair is near square: `[4, 3]` |
| `16` | Perfect square larger than `1` |