Construct The Rectangle - Leetcode Solution

The problem "Construct The Rectangle" on LeetCode asks you to create a function that takes an integer argument area and returns a list of two integers that represent the length and width of a rectangle whose area equals the input value.

Problem Statement

Given an integer area, construct a rectangle with an equal area to the given integer. The aspect ratio of the rectangle should be as close to a square as possible, and the length and width of the rectangle should both be integers.

Return a list of two integers that represent the length and width of the rectangle.

Example

Input: area = 4
Output: [2,2]
Explanation: The rectangle has an area of 4 (2 * 2). 

Input: area = 37
Output: [37, 1]
Explanation: The rectangle has an area of 37 (37 * 1). 

Solution

The first step in solving this problem is to find the factors of the input area. We can then iterate through all the factors and determine which two factors have a difference that is as small as possible, as this will give us a rectangle that is as close to a square as possible.

The following Python code demonstrates this approach:

class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        factors = []
        
        # Find all factors of the input number
        for i in range(1, int(area ** 0.5) + 1):
            if area % i == 0:
                factors.append(i)
                factors.append(area // i)
                
        # Iterate through the factors and find the smallest difference
        min_diff = float('inf')
        for i in range(len(factors)):
            for j in range(i+1, len(factors)):
                if factors[j] - factors[i] < min_diff:
                    length = factors[j]
                    width = factors[i]
                    min_diff = factors[j] - factors[i]
                    
        return [length, width]

First, we create an empty list called factors to store all the factors of the input area. We iterate through all numbers from 1 to the square root of the input area and append each factor to the list if it evenly divides the input area. We also append the corresponding factor obtained by dividing the input area by the current factor.

Next, we initialize a variable called min_diff to infinity. We then iterate through all pairs of factors in the factors list and calculate the difference between them. If the difference is smaller than the current minimum difference, we update the min_diff, length, and width variables accordingly.

Finally, we return the list [length, width] that represents the dimensions of the rectangle with an area equal to the input area.

This solution has a time complexity of O(sqrt(area)) and a space complexity of O(sqrt(area)) to store the list of factors.

1