Skip to main content
Talentd

Construct the Rectangle - Solution & Explanation

EasyMath11 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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:

  1. The area of the rectangular web page you designed must equal to the given target area.
  2. The width W should not be larger than the length L, which means L >= W.
  3. 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 <= 107

Approach Overview

Problem 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 1: Brute Force Factorization

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.

Code

PythonJavaScriptJavaC#C++C

Python

JavaScript

Java

C#

C++

C

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Factor Search

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.

Code

PythonJavaScriptJavaC#C++C

Python

JavaScript

Java

C#

C++

C

Complexity

Time Complexity: O(sqrt(n)), due to the similar bounds of iteration depending on the size of 'area'.
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Factorization

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.

Optimized Factor Search

Time Complexity: O(sqrt(n)), due to the similar bounds of iteration depending on the size of 'area'.
Space Complexity: O(1)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force FactorizationO(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

Video Solution

Construct the Rectangle | Leet code 492 | Theory explained + Python code • Sai Anish Malla • 2,458 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Construct the Rectangle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer