Construct the Rectangle
EasyPrompt
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:
- The area of the rectangular web page you designed must equal to the given target area.
- The width
Wshould not be larger than the lengthL, which meansL >= W. - The difference between length
Land widthWshould 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
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
best_Ltoareaandbest_Wto1. - Iterate through possible widths
wfrom 1 up toarea. - For each
w, check if it is a divisor ofarea(i.e.,area % w == 0). - If it is a divisor, calculate the corresponding length
l = area / w. - Check if the condition
l >= wis met. - If it is, compare the current difference
l - wwith the best difference found so far,best_L - best_W. - If
l - wis smaller, updatebest_L = landbest_W = w. - After the loop, return
[best_L, best_W].
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Calculate the integer part of the square root of
area. Let this bew. - Start a loop that continues as long as
wis not a divisor ofarea. - In each iteration of the loop, decrement
wby 1. - The loop will terminate when a
wis found such thatarea % w == 0. - This
wis the optimal widthW. - Calculate the length
L = area / w. - Return the result as an array
[L, W].
Walkthrough
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.
class Solution { public int[] constructRectangle(int area) { int w = (int) Math.sqrt(area); while (area % w != 0) { w--; } return new int[]{area / w, w}; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
class Solution {public int[] constructRectangle(int area) { int w = (int)Math.sqrt(area); while (area % w != 0) { --w; } return new int[]{area / w, w}; }}class Solution {public: vector<int> constructRectangle(int area) { int w = sqrt(1.0 * area); while (area % w != 0) --w; return {area / w, w}; }};class Solution: def constructRectangle(self, area: int) -> List[int]: w = int(sqrt(area)) while area % w != 0: w -= 1 return [area // w, w]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.