492. Construct the Rectangle

Problem Description

You need to design a rectangular web page with a specific area. Given a target area value, find the dimensions (length L and width W) of a rectangle that satisfies these conditions:

The rectangle's area must equal the given target area (i.e., L × W = area)
The width must not exceed the length (L ≥ W)
The difference between length and width (L - W) should be minimized

The goal is to find a rectangle that's as close to a square as possible while maintaining the exact area. Return the dimensions as an array [L, W] where L is the length and W is the width.

For example, if the area is 4, possible rectangles include [4, 1] and [2, 2]. Since [2, 2] has a smaller difference (0) compared to [4, 1] (difference of 3), the answer would be [2, 2].

The solution starts from the square root of the area (which would give a perfect square if possible) and works downward to find the largest width that divides the area evenly. This ensures the minimum difference between length and width.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To minimize the difference between length and width while maintaining a fixed area, we want the rectangle to be as close to a square as possible. For a perfect square, both dimensions would be equal to √area.

Since we need L × W = area and want to minimize L - W, the optimal dimensions would have W as large as possible (which makes L as small as possible, bringing them closer together). The largest possible value for W that still satisfies L ≥ W would be when both dimensions are equal, giving us W = L = √area.

However, √area might not be an integer, or even if it is, it might not divide the area evenly. So we start from W = floor(√area) and check if it divides the area. If not, we decrease W by 1 and check again. We continue this process until we find a width that divides the area evenly.

Why does this work? Consider that for any factorization of the area into L × W, if W > √area, then L < √area, violating our constraint that L ≥ W. Therefore, the valid range for W is from 1 to floor(√area). By starting from the upper bound and working downward, we find the largest valid W, which gives us the smallest difference L - W.

For example, with area = 12:

√12 ≈ 3.46, so we start with W = 3
Check if 12 % 3 = 0? Yes! So W = 3 and L = 12/3 = 4
Result: [4, 3] with difference of 1 (optimal)

Solution Approach

The implementation follows a straightforward approach based on finding the optimal width:

Calculate the starting point: We begin by computing w = int(sqrt(area)). This gives us the floor of the square root, which represents the largest possible width if the area were a perfect square or close to it.
Find a valid divisor: We use a while loop to check if the current width w divides the area evenly:
```
while area % w != 0:
    w -= 1
```
- If area % w != 0, it means w doesn't divide the area evenly, so we can't use it as a width
- We decrement w by 1 and check again
- This continues until we find a w that divides the area with no remainder
Calculate the length: Once we find a valid width, we calculate the corresponding length using integer division:
```
L = area // w
```
Return the result: We return [area // w, w], which gives us [L, W] where L ≥ W is guaranteed.

The algorithm guarantees correctness because:

Starting from √area and moving downward ensures we find the largest valid W
Any valid divisor w of the area will eventually be found
Since we're searching from large to small values of W, the first valid divisor we find minimizes L - W
The constraint L ≥ W is automatically satisfied since w ≤ √area implies area/w ≥ √area ≥ w

Time complexity: O(√n) in the worst case, where we might need to check all values from √area down to 1. Space complexity: O(1) as we only use a constant amount of extra space.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with area = 24 to find the optimal rectangle dimensions.

Step 1: Calculate starting point

First, we compute w = int(sqrt(24))
Since √24 ≈ 4.899, we get w = 4

Step 2: Find a valid divisor

Check if w = 4 divides 24 evenly: 24 % 4 = 0 ✓
Since the remainder is 0, we found our width!

Step 3: Calculate the length

L = 24 // 4 = 6

Step 4: Return result

Return [6, 4]

Let's verify this is optimal:

Area check: 6 × 4 = 24 ✓
Constraint check: 6 ≥ 4 ✓
Difference: 6 - 4 = 2

Other possible rectangles for area 24 include [24, 1], [12, 2], and [8, 3], but these have differences of 23, 10, and 5 respectively. Our solution [6, 4] with difference 2 is indeed optimal.

Another example with area = 37 (prime number):

Step 1: w = int(sqrt(37)) = 6

Step 2: Check divisors:

37 % 6 = 1 (not 0, decrement)
37 % 5 = 2 (not 0, decrement)
37 % 4 = 1 (not 0, decrement)
37 % 3 = 1 (not 0, decrement)
37 % 2 = 1 (not 0, decrement)
37 % 1 = 0 ✓

Step 3: L = 37 // 1 = 37

Step 4: Return [37, 1]

Since 37 is prime, the only factorization is 37 × 1, giving us the expected result.

Solution Implementation

1from math import sqrt
2from typing import List
3
4class Solution:
5    def constructRectangle(self, area: int) -> List[int]:
6        # Start with width as the square root of area (rounded down)
7        # This ensures we find the closest L and W values where L >= W
8        width = int(sqrt(area))
9      
10        # Decrease width until we find a value that divides the area evenly
11        # This guarantees width is a factor of area
12        while area % width != 0:
13            width -= 1
14      
15        # Calculate length using the found width
16        # Return [L, W] where L >= W as required
17        length = area // width
18        return [length, width]
19

1class Solution {
2    /**
3     * Constructs a rectangle with the given area.
4     * Returns [L, W] where L >= W and L * W = area, with L - W minimized.
5     * 
6     * @param area The target area for the rectangle
7     * @return An array containing [length, width] of the rectangle
8     */
9    public int[] constructRectangle(int area) {
10        // Start with width as the square root of area (rounded down)
11        // This ensures we find the closest L and W values
12        int width = (int) Math.sqrt(area);
13      
14        // Decrease width until we find a value that divides the area evenly
15        // This guarantees area % width == 0, meaning width is a valid divisor
16        while (area % width != 0) {
17            width--;
18        }
19      
20        // Calculate length using the valid width
21        // Since area = length * width, we have length = area / width
22        // This ensures length >= width as required
23        int length = area / width;
24      
25        // Return the rectangle dimensions as [length, width]
26        return new int[] {length, width};
27    }
28}
29

1class Solution {
2public:
3    vector<int> constructRectangle(int area) {
4        // Find the width starting from the square root of the area
5        // This ensures L >= W and minimizes |L - W|
6        int width = sqrt(static_cast<double>(area));
7      
8        // Decrease width until we find a divisor of the area
9        // This guarantees that area % width == 0
10        while (area % width != 0) {
11            --width;
12        }
13      
14        // Calculate length as area / width
15        // Return {length, width} where length >= width
16        int length = area / width;
17        return {length, width};
18    }
19};
20

1function constructRectangle(area: number): number[] {
2    // Find the width starting from the square root of the area
3    // This ensures L >= W and minimizes |L - W|
4    let width: number = Math.floor(Math.sqrt(area));
5  
6    // Decrease width until we find a divisor of the area
7    // This guarantees that area % width == 0
8    while (area % width !== 0) {
9        width--;
10    }
11  
12    // Calculate length as area / width
13    // Return [length, width] where length >= width
14    const length: number = area / width;
15    return [length, width];
16}
17

Time and Space Complexity

Time Complexity: O(√area)

The algorithm starts with w = int(sqrt(area)) and decrements w in a while loop until it finds a divisor of area. In the worst case, when area is a prime number, the loop will iterate from √area down to 1. Since we start at approximately √area and decrement by 1 each iteration, the maximum number of iterations is O(√area).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. It stores:

Variable w to track the current width candidate
The result list containing two integers [L, W]

Since these variables don't scale with the input size, the space complexity is constant.

Common Pitfalls

1. Integer Overflow in Square Root Calculation

In some programming languages or with very large area values, computing the square root might lead to precision issues or overflow. For instance, if using integer arithmetic exclusively, the square root calculation could be problematic.

Solution: Use appropriate data types and libraries that handle large numbers correctly. In Python, this is generally not an issue due to arbitrary precision integers, but in languages like C++ or Java, ensure you're using appropriate types (like long long in C++ or long in Java).

2. Starting from the Wrong Initial Value

A common mistake is starting from width = area or width = 1 instead of width = int(sqrt(area)). This would either make the algorithm inefficient or produce incorrect results.

Solution: Always start from int(sqrt(area)) and work downward. This ensures:

You find the optimal width quickly
The constraint L >= W is naturally satisfied
The difference L - W is minimized

3. Forgetting to Handle Edge Cases

While the algorithm handles most cases well, developers might forget to consider edge cases like:

area = 1 (should return [1, 1])
Perfect squares (e.g., area = 9 should return [3, 3])
Prime numbers (e.g., area = 13 should return [13, 1])

Solution: The current implementation actually handles these cases correctly, but it's important to test them explicitly:

# Test edge cases
assert constructRectangle(1) == [1, 1]    # Minimum area
assert constructRectangle(9) == [3, 3]    # Perfect square
assert constructRectangle(13) == [13, 1]  # Prime number

4. Incorrect Return Order

Returning [width, length] instead of [length, width] is a subtle but critical error that violates the problem requirements.

Solution: Always double-check that you're returning [L, W] where L >= W. The correct return statement should be:

return [area // width, width]  # NOT [width, area // width]

5. Infinite Loop Risk

If the decrement logic is incorrect (e.g., forgetting to decrement width or using the wrong condition), the while loop could run indefinitely.

Solution: Ensure the loop condition and decrement are correct:

while area % width != 0:
    width -= 1  # Must decrement to avoid infinite loop

Additionally, you could add a safety check (though not necessary for this problem):

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

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know