Watch 10 video solutions for Construct the Rectangle, a easy level problem involving Math. This walkthrough by Sai Anish Malla has 2,427 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |