How do you solve Construct the Rectangle on LeetCode?

Construct the Rectangle (LeetCode #492) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The optimal solution leverages the square root to minimize the number of checks.

What is the time complexity of Construct the Rectangle?

The optimal solution for Construct the Rectangle runs in O(n) time and uses O(1) space. The time complexity is O(n) in the worst case, but we usually find a solution much faster since we start from the square root.

What is the brute force solution for Construct the Rectangle?

The brute force approach for Construct the Rectangle is Brute Force, with O(n²) time complexity and O(1) space complexity. We can find all possible pairs of dimensions (L, W) by iterating through all possible widths W from 1 to area. For each width, we calculate the corresponding length L and check if it meets the conditions. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Construct the Rectangle?

Construct the Rectangle uses the following concepts: Math. The recommended patterns to study are: Math, Greedy.

What are the interview tips for Construct the Rectangle?

Always clarify the constraints and requirements before jumping into coding. Consider edge cases like perfect squares and very large areas. Explain your thought process clearly while coding to demonstrate your understanding.

What are common mistakes when solving Construct the Rectangle?

Forgetting to check if L >= W when calculating dimensions. Not considering the integer division when calculating L.

#492

Construct the Rectangle

Easy

MathMathGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Instead of checking all widths, we can start from the square root of the area and work downwards. This way, we find the closest dimensions with the smallest difference more efficiently.

⚙️

Algorithm

5 steps

1Step 1: Calculate the integer square root of the area.
2Step 2: Loop from this square root down to 1.
3Step 3: For each width W, calculate L as area / W.
4Step 4: Check if L * W equals area and if L >= W.
5Step 5: Return the first valid pair [L, W] found.

solution.py7 lines

1import math
2
3def constructRectangle(area):
4    for W in range(int(math.sqrt(area)), 0, -1):
5        L = area // W
6        if L * W == area:
7            return [L, W]

ℹ

Complexity note: The time complexity is O(n) in the worst case, but we usually find a solution much faster since we start from the square root.

1The optimal solution leverages the square root to minimize the number of checks.
2The conditions ensure that we only consider valid rectangles.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.