Construct the Rectangle: Finding the Closest Square

Construct the Rectangle is LeetCode 492. You are given an integer area representing the total area of a web page. Your job is to find the length L and width W of a rectangle such that L * W = area, L >= W, and the difference L - W is as small as possible. Return [L, W].

In other words, you want the rectangle that is closest to being a square.

The first instinct might be to enumerate all factor pairs and pick the one with the smallest difference. That works but is slow for large inputs. A much better approach is to start from the square root and search downward.

The key insight

The rectangle that is closest to a square always has its width as close to sqrt(area) as possible. Think about it: a perfect square has L = W = sqrt(area), which gives a difference of zero. If the area is not a perfect square, you want the largest W that is still at or below sqrt(area) and divides area evenly.

So the algorithm is:

1. Compute W = floor(sqrt(area)).
2. While area % W != 0, decrement W by 1.
3. Return [area // W, W].

You are guaranteed to find a valid W because W = 1 always divides any positive integer. In the worst case (when area is prime), you end up at W = 1 and L = area.

The solution

import math

def constructRectangle(area: int) -> list[int]:
    w = int(math.sqrt(area))
    while area % w != 0:
        w -= 1
    return [area // w, w]

The function starts by computing floor(sqrt(area)). Then it steps W downward one at a time until it finds a value that divides area with no remainder. Once it does, L is simply area // W. Because W started at or below the square root, L is guaranteed to be at least as large as W, satisfying the L >= W constraint automatically.

Notice how the loop does very little work for most inputs. Composite numbers tend to have a factor close to the square root, so the loop terminates quickly. Only prime numbers force the loop all the way down to 1.

Complexity analysis

The square root approach is much faster. In the worst case (a prime number), you iterate from sqrt(n) down to 1, which is O(sqrt(n)) steps. For composite numbers the loop usually terminates in just a few iterations. The space is O(1) since you only store two variables.

The building blocks

This problem is a clean application of the mathematical insight that factors come in pairs, and the pair closest to each other always straddles the square root. If d divides n, then n / d is also a factor, and one of them is at most sqrt(n) while the other is at least sqrt(n).

You will see this same pattern in problems like Sqrt(x), which asks you to compute the integer square root itself. Valid Perfect Square asks whether an exact integer root exists. Count Primes uses the square root bound for a different purpose: you only need to check factors up to sqrt(n) to determine primality.

The underlying idea - "search near the square root for factor-related questions" - recurs across many math problems on LeetCode.

Edge cases to watch for

• Perfect squares like area = 16: sqrt(16) = 4, and 16 % 4 == 0 on the first check. Returns [4, 4]. The loop body never executes.
• Prime numbers like area = 23: No factor exists between 2 and sqrt(23), so the loop runs all the way down to W = 1. Returns [23, 1].
• area = 1: sqrt(1) = 1, and 1 % 1 == 0. Returns [1, 1]. This is the smallest valid input.
• Large composites like area = 1000000: sqrt(1000000) = 1000, and 1000000 % 1000 == 0. Returns [1000, 1000]. Even large inputs resolve instantly when a factor sits right at the square root.

From understanding to recall

The entire solution fits in three lines once you know the trick: start at sqrt(area), walk down until you find a divisor, divide. The part worth committing to memory is the starting point. It is tempting to start from 1 and work up, but starting from the square root and working down guarantees you find the best answer first.

When you practice writing this from scratch, focus on the sequence: compute the square root, floor it, decrement until divisible, return the pair. That mental model covers the whole solution. Spaced repetition helps make it automatic so you spend your interview time on harder problems.

Related posts

• Sqrt(x) - computing the integer square root with binary search
• Valid Perfect Square - checking if an exact integer root exists
• Arranging Coins - another math problem using the square root bound