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:
W should not be larger than the length L, which means L >= W.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 <= 107Problem Overview: You are given an integer area representing the area of a rectangle. The task is to return dimensions [L, W] such that L * W = area, L ≥ W, and the difference L - W is minimized.
Approach 1: Brute Force Factorization (O(n) time, O(1) space)
The straightforward idea is to iterate through all possible widths from 1 up to area. For each value, check if it divides the area using area % w == 0. If it does, compute the corresponding length L = area / w. Track the pair where L ≥ W and the difference L - W is smallest. This method directly tests every factor pair but wastes work once values exceed the square root.
This approach relies purely on arithmetic factor checks and works for small inputs or when simplicity matters more than performance. The algorithm uses constant extra memory because it only stores the best pair found so far.
Approach 2: Optimized Factor Search (O(√n) time, O(1) space)
A rectangle with the smallest difference between length and width occurs when the sides are as close as possible. That happens near the square root of the area. Start from floor(sqrt(area)) and iterate downward until you find a value that divides the area. The first valid divisor w gives the optimal pair [area / w, w].
This works because factor pairs mirror around the square root. Searching downward ensures the width stays as large as possible while still dividing the area, which minimizes L - W. The loop runs at most √area iterations, making it significantly faster for large inputs. The algorithm uses constant extra space since only a few integer variables are maintained.
Problems like this rely on number properties and factor relationships, which commonly appear in math, number theory, and brute force problem patterns.
Recommended for interviews: The optimized square-root factor search is the expected solution. It demonstrates awareness of factor symmetry and reduces the search space from n to √n. Mentioning the brute force approach first shows you understand the baseline, but implementing the optimized search shows stronger algorithmic thinking.
The brute force approach involves iterating over all possible width values starting from 1 up to the square root of the area. For each width that is a divisor of the area, calculate the length as area divided by this width. Since the width increases and we're calculating length from it, L >= W condition is inherently satisfied. The pair with the smallest difference between L and W is the result.
The solution starts by iterating from the square root of the area down to 1. For each potential width, it checks if it divides the area perfectly. If it does, it computes the corresponding length and returns the pair since it assures L >= W by starting from a high width and going down.
Time Complexity: O(sqrt(n)), where n is the area because we only check divisors up to the square root.
Space Complexity: O(1), as no additional space dependent on input size is used.
We optimize the brute force by reducing unnecessary checks. Instead of starting from a width value of 1, directly jump to sqrt(area) and move inwards. This ensures that we're only exploring potential dimensions that are likely close together, thereby reducing unnecessary loops. Utilize integer calculations which grant more consistent performance on larger numbers.
Improveys the initial search space by starting specifically at sqrt(area) and uses a decremental loop. This assures the detection of the closest dimension pair while reducing iteration count.
Time Complexity: O(sqrt(n)), due to the similar bounds of iteration depending on the size of 'area'.
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Brute Force Factorization | Time Complexity: O(sqrt(n)), where n is the area because we only check divisors up to the square root. |
| Optimized Factor Search | Time Complexity: O(sqrt(n)), due to the similar bounds of iteration depending on the size of 'area'. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Factorization | O(n) | O(1) | When implementing the simplest approach or demonstrating baseline factor enumeration |
| Optimized Factor Search (Square Root) | O(√n) | O(1) | Best general solution when you need minimal difference between rectangle sides |
Construct the Rectangle | Leet code 492 | Theory explained + Python code • Sai Anish Malla • 2,427 views views
Watch 9 more video solutions →Practice Construct the Rectangle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor