Is Construct the Rectangle easy or hard?

Construct the Rectangle is classified as an Easy problem on LeetCode. The main idea is recognizing that the best rectangle dimensions come from factors closest to the square root of the area.

Construct the Rectangle Python/Java solution

Most implementations compute sqrt(area), loop downward until a divisor is found, and return the pair [area / w, w]. The logic is identical in Python, Java, C++, and JavaScript because it relies only on arithmetic operations and a loop.

How to solve Construct the Rectangle in O(√n)?

Compute floor(sqrt(area)) and iterate downward until a value divides the area. Once a divisor w is found, return [area / w, w]. This guarantees the width is as close as possible to the length, minimizing the difference while keeping L ≥ W.

What is the best approach for Construct the Rectangle?

The optimal solution searches for factors starting from the square root of the given area. By moving downward from √area until a divisor is found, you immediately get the pair with the smallest difference between length and width. This runs in O(√n) time and uses O(1) extra space.

Is Construct the Rectangle asked at Google/Amazon/Meta?

Construct the Rectangle is a common easy-level screening problem focused on factorization and mathematical reasoning. Similar math and divisor problems appear in interviews at companies like Amazon and Google during early technical rounds.

What data structure is used in Construct the Rectangle?

No special data structures are required. The solution relies on mathematical factorization and simple integer variables while iterating through possible divisors of the area.

What is the time complexity of Construct the Rectangle?

The optimized solution runs in O(√n) time because it checks possible divisors starting from the square root of the area and moves downward until a valid factor is found. Space complexity is O(1) since only a few integer variables are used.

Description Hints 1 Solution Video 9:39

492. Construct the Rectangle

Easy65.2% acceptance2 companies

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 W should not be larger than the length L, which means L >= W.
The difference between length 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 <= 10⁷

Asked at 2 companies

Google Amazon

Topics

Math

Hints open one at a time

Hint 1

The W is always less than or equal to the square root of the area, so we start searching at sqrt(area) till we find the result.

9:39

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def constructRectangle(self, area: int) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution