Problem Description

You are given an integer area representing the area of a rectangle. Your task is to find the rectangle's length L and width W such that:

• L * W == area
• L ≥ W (length is not less than width)
• The difference L - W is minimized (i.e., the rectangle should be as close to a square as possible)

Thought Process

At first glance, you might think to check every possible pair of factors (L, W) that multiply to area and pick the pair with the smallest difference. However, this could be inefficient for large numbers.

To optimize, notice that the closer two numbers multiply to a given product, the closer they are to each other. For a rectangle with minimal difference between length and width, both should be as close as possible to the square root of area. So, starting from sqrt(area) and moving downwards, the first integer W that divides area evenly gives the optimal solution.

Solution Approach

Here’s a step-by-step guide to solving the problem efficiently:

1. Start at the square root:
   • Compute the integer part of sqrt(area). This is the largest possible width such that the rectangle is as close to a square as possible.
2. Find the largest divisor:
   • Iterate from this value down to 1. For each W, check if area % W == 0.
   • The first such W you find is the width of the rectangle; L = area / W is the corresponding length.
3. Return the result:
   • Return [L, W] as specified.

This method is efficient because it avoids unnecessary checks and leverages the mathematical property that the rectangle closest to a square will have its sides near the square root.

Example Walkthrough

Let’s walk through an example with area = 37:

• Compute sqrt(37) ≈ 6.08. Start checking from W = 6 down to 1.
• 37 % 6 != 0 (6 doesn't divide 37)
• 37 % 5 != 0
• 37 % 4 != 0
• 37 % 3 != 0
• 37 % 2 != 0
• 37 % 1 == 0 (1 divides 37)
• So, W = 1, L = 37 / 1 = 37
• Return [37, 1]

For a square area, say area = 36:

• sqrt(36) = 6. 36 % 6 == 0
• W = 6, L = 36 / 6 = 6
• Return [6, 6]

Time and Space Complexity

Brute-force approach:

• Check every possible width from 1 up to area.
• Time Complexity: O(area)
• Space Complexity: O(1)

• Only check widths from sqrt(area) down to 1.
• Time Complexity: O(sqrt(area)), since in the worst case you check all numbers down to 1 from sqrt(area).
• Space Complexity: O(1)

The optimization is significant for large values of area.

Summary

The key insight is to find the rectangle with area area whose sides are as close as possible. By starting the search at the integer square root of area and moving downward, we quickly find the dimensions with the minimal difference. This approach is efficient and leverages mathematical properties, making the solution both simple and elegant.

Code Implementation

import math

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

#include <vector>
#include <cmath>

class Solution {
public:
    std::vector<int> constructRectangle(int area) {
        int w = static_cast<int>(sqrt(area));
        while (area % w != 0) {
            --w;
        }
        return {area / w, w};
    }
};
      

class Solution {
    public int[] constructRectangle(int area) {
        int w = (int)Math.sqrt(area);
        while (area % w != 0) {
            w--;
        }
        return new int[]{area / w, w};
    }
}
      

var constructRectangle = function(area) {
    let w = Math.floor(Math.sqrt(area));
    while (area % w !== 0) {
        w--;
    }
    return [area / w, w];
};