Leetcode 492. Construct the Rectangle

Problem

The task here is to design a webpage with specific dimensions given certain requirements. The webpage should have a specific area, with width and length so designed that the difference between length L and width W should be as small as possible and length L should always be equal to or greater than width W.

If we are given the area of the webpage, we need to return the dimensions of the webpage i.e., the length L and width W such that the difference between them is as small as possible and length is always larger or equal to width.

For example,

If the given area is 4, the possible dimensions could be [1,4], [2,2], [4,1]. But, [1,4] is not valid as per the requirement that length should be greater than or equal to width. And even though [4,1] is valid, [2,2] is more optimal as the difference is closer to 0. So, the output would be [2,2].

Solution

Let's discuss the approach to the solution:

1. First, we calculate the square root of the given area. This gives us an optimal starting point to check for the width of the page as the length and width of a square (which has the least difference between length and width) is equal to the square root of the area.

2. Next, we loop from the calculated width towards 1 decrementing each time to find a width that can perfectly divide the given area. This would ensure that we find the maximum possible width.

3. The length can be deduced by dividing the area by the width and the result of width and length is then returned.

This is a straight forward solution that doesn't require any sophisticated algorithms or data structures.

Let's follow the algorithm through an example:

Say we are given an area of 4. The square root of 4 is 2 and we can start from this point. Checking if 4 is divisible by 2, yes, and we can stop here. So, our width would be 2 and length, which is 4 divided by 2, also gives us 2. The output would be [2,2].

Now, writing the solutions in each of the required languages:

Python

1
2python
3import math
4class Solution:
5    def constructRectangle(self, area: int) -> list[int]:
6        width = math.isqrt(area)
7        while area%width:
8            width -= 1
9        return [area//width, width]

Java

1
2java
3class Solution {
4    public int[] constructRectangle(int area) {
5        int width = (int) Math.sqrt(area);
6        while (area%width != 0)
7            width--;
8        return new int[]{area/width, width};
9    }
10}

JavaScript

1
2javascript
3var constructRectangle = function(area) {
4    let width = Math.floor(Math.sqrt(area));
5    while(area%width !== 0) {
6        width--;
7    }
8    return [area/width,width]
9};

C++

1
2cpp
3class Solution {
4public:
5    vector<int> constructRectangle(int area) {
6        int width = sqrt(area);
7        while (area%width){
8            width--;
9        }
10        return {area/width, width};
11    }
12};

C#

1
2csharp
3public class Solution {
4    public int[] ConstructRectangle(int area) {
5        int width = (int)Math.Sqrt(area);
6        while (area%width != 0)
7            width--;
8        return new int[2]{area/width, width};
9    }
10}

The solutions in different programming languages above follow the same algorithm discussed above. Starting from the square root of the area, we keep decrementing the width until we find a width that can divide the area perfectly. The length is then the area divided by the width.This algorithm ensures that the difference between length and width is minimized since we start from the square root, which would give us equal length and width in the best-case scenario (if the area is a perfect square). If not, we try to get to the nearest perfect square less than the given area, which ensures that the difference between the length and width is minimized.

Note that Math.sqrt() in JavaScript, math.isqrt() in Python, (int) Math.sqrt() in Java methods are used to compute the square root of the given area in the respective languages. Also, math.isqrt() in python is used to get the integer square root of the number, it will ignore the values after the decimal.

For example, Math.sqrt(4) will return 2 because the square root of 4 is 2.

In the case of the Java solution, we are casting the answer to an integer (which floors the decimal) with (int) Math.sqrt(area) since in Java, Math.sqrt() returns a double.

The area is then divided by width, decrementing width until we find a width that perfectly divides the area. This is achieved by using a while loop that continues until area % width = 0 which implies that the area is divisible by the width.

Finally, the width and length are returned in an array with the length always being greater than or equal to the width. These solutions have a time complexity of O(sqrt(n)) because in the worst-case scenario we might have to iterate till 1 starting from the square root of n, where n is the area of the rectangle. This is much better than starting from n and going till 1 which would have had a time complexity of O(n).