Leetcode – Construct the Rectangle Solution in Python

Spread the love

The Construct the Rectangle is a common mathematical algorithmic problem found on Leetcode. This particular problem tests the ability to perform mathematical calculations and to think algorithmically about optimization problems. In this article, we will delve deep into the problem statement, explore different methods to solve it in Python, and analyze their complexities.

Problem Statement:

For a web developer, it is very important 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 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.

You need to output the length and width of the web page in an array.

Example:

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.

Brute Force Approach:

The simplest approach is to start with W = 1 and keep increasing it until W*W is greater than the given area. For each W, calculate L as area / W and check if it satisfies L * W == area and L >= W. Keep track of the pair that minimizes L - W.

def constructRectangle(area):
    min_diff = float('inf')
    result = [0, 0]
    
    for W in range(1, int(area ** 0.5) + 1):
        L = area // W
        if L * W == area and L >= W:
            if L - W < min_diff:
                min_diff = L - W
                result = [L, W]
                
    return result

This approach has a time complexity of O(sqrt(n)), where n is the given area.

Optimized Approach:

We can optimize the above approach by starting with W equal to the square root of the area and decreasing it. This way, we can find the optimal pair sooner because as W decreases, L increases, and the first pair that satisfies L * W == area and L >= W is guaranteed to have the smallest difference between L and W.

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

This optimized approach still has a time complexity of O(sqrt(n)), but in practice, it will find the solution faster.

Mathematical Insight:

For a given area, the pair [L, W] that minimizes the difference L - W is the pair that is closest to the square root of the area. This is because the difference L - W is minimized when L and W are as close to each other as possible. In mathematical terms, this corresponds to finding the factors of the area that are closest to each other.

Conclusion:

The Construct the Rectangle is a practical and interesting problem that combines mathematics with algorithmic thinking. Through this problem, we observe how an efficient solution can be derived from understanding the underlying mathematics and properties of the problem domain. While the brute force approach is a good starting point, optimizing the solution requires thinking about the characteristics of the area and the relationships between the length and width. Such problems not only enhance mathematical thinking but also develop algorithmic problem-solving skills, which are essential for coding interviews and programming in general.

Leave a Reply