492. Construct the Rectangle - Solution

The problem

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⁷

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.

Python

def constructRectangle(area):
    for width in range(int(area**0.5), 0, -1):
        if area % width == 0:
            return [area // width, width]

Java

public int[] constructRectangle(int area) {
    for (int width = (int) Math.sqrt(area); width > 0; width--) {
        if (area % width == 0) {
            return new int[] {area / width, width};
        }
    }
    return new int[] {area, 1};
}

C++

#include <vector>
#include <cmath>
using namespace std;

vector<int> constructRectangle(int area) {
    for (int width = sqrt(area); width > 0; --width) {
        if (area % width == 0) {
            return {area / width, width};
        }
    }
    return {area, 1};
}

JavaScript

function constructRectangle(area) {
    for (let width = Math.floor(Math.sqrt(area)); width > 0; width--) {
        if (area % width === 0) {
            return [area / width, width];
        }
    }
}

#include <math.h>
#include <stdio.h>

void constructRectangle(int area, int *L, int *W) {
    for (int width = (int)sqrt(area); width > 0; --width) {
        if (area % width == 0) {
            *L = area / width;
            *W = width;
            return;
        }
    }
    *L  = area;
    *W = 1;
}

public int[] ConstructRectangle(int area) {
    for (int width = (int)Math.Sqrt(area); width > 0; width--) {
        if (area % width == 0) {
            return new int[] {area / width, width};
        }
    }
    return new int[] {area, 1};
}

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.

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.

Python

def constructRectangle(area):
    width = int(area ** 0.5)
    while width > 0:
        if area % width == 0:
            return [area // width, width]
        width -= 1

Java

public int[] constructRectangle(int area) {
    int width = (int) Math.sqrt(area);
    while (width > 0) {
        if (area % width == 0) {
            return new int[] {area / width, width};
        }
        width--;
    }
    return new int[] {area, 1};
}

C++

#include <vector>
#include <cmath>
using namespace std;

vector<int> constructRectangle(int area) {
    int width = sqrt(area);
    while (width > 0) {
        if (area % width == 0) {
            return {area / width, width};
        }
        --width;
    }
    return {area, 1};
}

JavaScript

function constructRectangle(area) {
    let width = Math.floor(Math.sqrt(area));
    while (width > 0) {
        if (area % width === 0) {
            return [area / width, width];
        }
        width--;
    }
}

#include <math.h>
#include <stdio.h>

void constructRectangle(int area, int *L, int *W) {
    int width = (int)sqrt(area);
    while (width > 0) {
        if (area % width == 0) {
            *L = area / width;
            *W = width;
            return;
        }
        --width;
    }
    *L = area;
    *W = 1;
}

public int[] ConstructRectangle(int area) {
    int width = (int)Math.Sqrt(area);
    while (width > 0) {
        if (area % width == 0) {
            return new int[] {area / width, width};
        }
        width--;
    }
    return new int[] {area, 1};
}

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.

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

func constructRectangle(area int) []int {
	w := int(math.Sqrt(float64(area)))
	for area%w != 0 {
		w--
	}
	return []int{area / w, w}
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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	–

Complexity analysis

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

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.

Construct the Rectangle solution and explanation

The problem

Approach overview

Approach 1: Brute Force Factorization

Approach 2: Optimized Factor Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Construct the Rectangle solution and explanation

The problem

Approach overview

Approach 1: Brute Force Factorization

Approach 2: Optimized Factor Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems