# Construct the Rectangle
**Difficulty:** EASY
[External](https://leetcode.com/problems/construct-the-rectangle)
Canonical: https://scaleengineer.com/dsa/problems/construct-the-rectangle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
A web developer needs to know how to design a web page's size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1. The area of the rectangular web page you designed must equal to the given target area.
2. The width `W` should not be larger than the length `L`, which means `L >= W`.
3. The difference between length `L` and width `W` should be as small as possible.

Return _an array `[L, W]` where `L` and `W` are the length and width of the web page you designed in sequence._

**Example 1:**

**Input:** area = 4
**Output:** [2,2]
**Explanation:** The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. 
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.

**Example 2:**

**Input:** area = 37
**Output:** [37,1]

**Example 3:**

**Input:** area = 122122
**Output:** [427,286]

**Constraints:**

* `1 <= area <= 107`

# Approaches
## Brute Force Iteration
This approach involves a straightforward, exhaustive search. We check every possible integer for the width `W`, starting from 1 up to the given `area`. For each potential width, we determine if it's a valid divisor. If it is, we calculate the corresponding length `L` and check if it forms a valid rectangle (`L >= W`). We keep track of the pair `[L, W]` that has the smallest difference `L - W` found so far.
**Time:** O(area). The loop runs up to `area` times. This is very inefficient for the given constraints (area up to 10^7) and will likely result in a Time Limit Exceeded error. · **Space:** O(1). We only use a constant amount of extra space for variables to store the best pair and the loop counter.
**Pros:** *   Simple to conceptualize and implement.; *   Guaranteed to find the correct answer, given enough time.
**Cons:** *   Extremely inefficient for large inputs.; *   The search space is unnecessarily large and will not pass the time limits for this problem.
### Explanation
The algorithm begins by initializing a variable to store the minimum difference found, setting it to a very large value. It also initializes an array to hold the best `[L, W]` pair, which can be seeded with `[area, 1]`. Then, it iterates with a width `w` from 1 up to `area`. In each iteration, it checks if `w` divides `area` evenly. If it does, it calculates the length `l = area / w`. The condition `l >= w` is then verified. If this holds, the difference `l - w` is compared to the stored minimum difference. If the new difference is smaller, the minimum difference is updated, and the result array is set to `[l, w]`. After checking all possible widths up to `area`, the stored result array will contain the optimal dimensions.

```java
class Solution {
    public int[] constructRectangle(int area) {
        int minDiff = Integer.MAX_VALUE;
        int[] result = new int[2];

        for (int w = 1; w <= area; w++) {
            if (area % w == 0) {
                int l = area / w;
                if (l >= w) {
                    if (l - w < minDiff) {
                        minDiff = l - w;
                        result[0] = l;
                        result[1] = w;
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize `best_L` to `area` and `best_W` to `1`.
*   Iterate through possible widths `w` from 1 up to `area`.
*   For each `w`, check if it is a divisor of `area` (i.e., `area % w == 0`).
*   If it is a divisor, calculate the corresponding length `l = area / w`.
*   Check if the condition `l >= w` is met.
*   If it is, compare the current difference `l - w` with the best difference found so far, `best_L - best_W`.
*   If `l - w` is smaller, update `best_L = l` and `best_W = w`.
*   After the loop, return `[best_L, best_W]`.

## Optimized Search from Square Root
A much more efficient solution is based on a key mathematical insight: to minimize the difference `L - W` for a fixed product `L * W = area`, the values of `L` and `W` must be as close to each other as possible. This means they should both be near the square root of the `area`. Since we require `L >= W`, the optimal width `W` must be less than or equal to `sqrt(area)`. This allows us to drastically reduce the search space.
**Time:** O(sqrt(area)). In the worst case (e.g., when `area` is a prime number), the loop starts from `sqrt(area)` and decrements down to 1. · **Space:** O(1). Constant extra space is used for the variables `w` and `l`.
**Pros:** *   Very efficient and optimal for the given constraints.; *   The implementation is simple and concise.; *   Leverages a mathematical property to significantly reduce computation.
**Cons:** *   Requires a small mathematical insight to come up with the approach.
### Explanation
The core idea is that for any pair of factors `(W, L)` of `area` where `W <= L`, it must be that `W <= sqrt(area)`. To minimize the difference `L - W`, we need to find the largest possible `W` that satisfies this condition. A larger `W` will result in a smaller `L` (`L = area / W`), bringing them closer together.

Therefore, the most effective algorithm is to start searching for a valid width `w` from `floor(sqrt(area))` downwards to 1. The very first integer `w` we find that divides `area` evenly will be the largest factor of `area` that is less than or equal to `sqrt(area)`. This `w` is our optimal width `W`. The corresponding length `L` is then `area / W`. The pair `[L, W]` is the solution.

```java
class Solution {
    public int[] constructRectangle(int area) {
        int w = (int) Math.sqrt(area);
        while (area % w != 0) {
            w--;
        }
        return new int[]{area / w, w};
    }
}
```
### Algorithm
*   Calculate the integer part of the square root of `area`. Let this be `w`.
*   Start a loop that continues as long as `w` is not a divisor of `area`.
*   In each iteration of the loop, decrement `w` by 1.
*   The loop will terminate when a `w` is found such that `area % w == 0`.
*   This `w` is the optimal width `W`.
*   Calculate the length `L = area / w`.
*   Return the result as an array `[L, W]`.

# Solutions
### Java

```java
class Solution {
public
  int[] constructRectangle(int area) {
    int w = (int)Math.sqrt(area);
    while (area % w != 0) {
      --w;
    }
    return new int[]{area / w, w};
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> constructRectangle(int area) {
    int w = sqrt(1.0 * area);
    while (area % w != 0)
      --w;
    return {area / w, w};
  }
};

```

### Python

```python
class Solution:
    def constructRectangle(self, area: int) -> List[int]: w = int(sqrt(area)) while area % w != 0: w -= 1 return [area // w, w]

```