#492

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Construct the Rectangle

Given an area, design a rectangle with integer length and width optimizing L >= W and minimal difference, using math.

Problem Statement

A web developer needs to create a rectangular webpage given a specific area. You must return integer dimensions [L, W] such that L >= W and L * W equals the given area.

Your goal is to construct a rectangle that minimizes the difference L - W. Return the dimensions as an array [L, W] satisfying these constraints for any input area, ensuring the solution efficiently leverages mathematical reasoning rather than brute-force enumeration.

Examples

Example 1

Input: area = 4

Output: [2,2]

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 details omitted.

Example 3

Input: area = 122122

Output: [427,286]

Example details omitted.

Constraints

1 <= area <= 107

Solution Approach

Start from Square Root

Compute the integer square root of the area as the initial candidate for width W. This ensures the first factor considered is closest to a square, minimizing L - W.

Iterate Down to Find Factor

Check integers from sqrt(area) down to 1 to see if they divide the area evenly. The first valid W found gives L = area / W, guaranteeing L >= W.

Return Optimal Dimensions

Once the factor is found, return [L, W]. This approach ensures the rectangle meets the constraints and minimizes the difference using direct math reasoning without unnecessary loops.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(sqrt(area)) because we only check factors down from sqrt(area) until one divides evenly. Space complexity is O(1) since only two variables store L and W.

What Interviewers Usually Probe

Expecting recognition that width cannot exceed sqrt(area) for optimal L-W difference.
Looking for iterative factor search starting at sqrt(area) rather than brute-force factorization.
Candidates should justify why L >= W and why minimal difference occurs at the first factor found from sqrt(area).

Common Pitfalls or Variants

Common pitfalls

Forgetting to ensure L >= W, which violates problem constraints.
Testing all possible pairs instead of leveraging the math-driven approach, leading to slower solutions.
Stopping iteration too early without checking proper division, causing incorrect dimensions.

Follow-up variants

Return all possible rectangles sorted by L-W difference instead of just the optimal one.
Handle non-integer areas by rounding to nearest integers while maintaining L >= W.
Optimize for largest width under additional design constraints, altering the search order from sqrt(area).

FAQ

What is the optimal way to start searching for W in Construct the Rectangle?

Begin at the integer square root of the area and iterate downward to find the first factor that divides the area evenly.

Why must L >= W in the solution?

This ensures the returned rectangle matches the problem constraints and minimizes the difference L - W for a visually balanced design.

Can this approach handle large area values efficiently?

Yes, because checking factors only down from sqrt(area) reduces time complexity to O(sqrt(area)) without testing every pair.

Are there common mistakes when implementing this problem?

Common errors include reversing L and W, using brute-force factor checks, or stopping iteration before finding a valid factor.

Does this problem follow a specific pattern?

Yes, Construct the Rectangle uses a math-driven solution pattern, focusing on factorization starting at sqrt(area) for optimal rectangle dimensions.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        w = int(sqrt(area))
        while area % w != 0:
            w -= 1
        return [area // w, w]

Continue Practicing

#497 random point in non overlapping rectangles #486 predict the winner #483 smallest good base