Construct the Rectangle

Difficulty: Easy | Acceptance: 63.70% | Paid: No Topics: Math

A web developer needs to know how to design a rectangular page that looks good on any screen. The specific requirement is that the length $L$ of the page must be greater than or equal to the width $W$, and the difference between $L$ and $W$ should be as small as possible.

Given a specific rectangular web page’s area, your job 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 must equal the given target area.
2. The width $W$ should not be larger than the length $L$.
3. The difference between $L$ and $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 that order.

Examples

Example 1:

Input: area = 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to form 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] because the difference between 4 and 1 is larger than the difference between 2 and 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 <= 10⁷

Table of Contents

• Examples
• Constraints
• Brute Force Iteration
• Optimal Square Root Search

Brute Force Iteration

Intuition We can iterate through all possible widths from 1 up to the square root of the area. For each width that divides the area evenly, we keep track of it. Since we are iterating upwards, the last valid width we find will be the largest possible width less than or equal to the square root, which minimizes the difference between length and width.

Steps

• Initialize a variable w to 1.
• Iterate i from 1 to sqrt(area).
• If area is divisible by i (i.e., area % i == 0), update w to i.
• After the loop, calculate l as area / w.
• Return the array [l, w].

import math

class Solution:
    def constructRectangle(self, area: int) -> list[int]:
        w = 1
        for i in range(1, int(math.sqrt(area)) + 1):
            if area % i == 0:
                w = i
        return [area // w, w]

Complexity

• Time: O(sqrt(n)), where $n$ is the area. We iterate up to the square root of the area.
• Space: $O(1)$, we only use a few variables for storage.
• Notes: This approach is efficient enough given the constraint $area \le 10^7$.

Optimal Square Root Search

Intuition The optimal width W will be the largest integer less than or equal to sqrt(area) that divides the area evenly. Instead of iterating from 1 upwards, we can start directly at floor(sqrt(area)) and decrement until we find a divisor. This finds the solution faster on average.

Steps

• Calculate the integer square root of area and assign it to w.
• While area is not divisible by w, decrement w by 1.
• Once a divisor is found, calculate l as area / w.
• Return the array [l, w].

import math

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

Complexity

• Time: O(sqrt(n)) in the worst case (e.g., when area is a prime number), but often faster than the brute force approach for composite numbers.
• Space: $O(1)$, constant space is used.
• Notes: This is the most efficient approach for this problem.