Construct the Rectangle

Easy

Asked by:

4 views

Topics:

Arrays

A web developer needs 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:

The area of the rectangular web page you designed must equal to the given target area.
The width W should not be larger than the length L, which means L >= W.
The difference between length L and width W should be as small as possible.

Return an array [L, W] where L and W are the length and width of the web page you designed in sequence.

Example 1:

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.

Example 2:

Input: area = 37
Output: [37,1]

Example 3:

Input: area = 122122
Output: [427,286]

Constraints:

1 <= area <= 10⁷

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the area `area`, specifically its maximum and minimum possible values?
If there are multiple valid rectangle dimensions (L, W) that satisfy the area, which one should I return? Should I return the one where L is minimized?
Is the input `area` guaranteed to be a positive integer? What should I return if it is zero or negative?
Are there any memory constraints I should be aware of, especially if the input `area` is very large?
Can you clarify what 'closest to square' means precisely? Should I prioritize minimizing the absolute difference |L-W|?

Brute Force Solution

Approach

The brute force approach to this problem is all about trying every possible combination. We essentially test every possible width and length to see which one works, checking to make sure their product matches the given area.

Here's how the algorithm would work step-by-step:

Start with the largest possible number that could be the length.
Then go through every number smaller than that, one at a time.
For each number, check if it perfectly divides the area.
If it does, then you've found a possible width and length combination.
If it doesn't, move on to the next smaller number.
Once you find a valid combination, that's your answer because you started searching from the largest possible length, which ensures the difference between length and width is minimized.

Code Implementation

def construct_the_rectangle_brute_force(area):
    largest_possible_length = int(area**0.5)

    # Iterate backwards from the largest possible length
    for current_length in range(largest_possible_length, area + 1):
        # We check if the area is evenly divisible by the length
        if area % current_length == 0:

            width = area // current_length
            length = current_length

            # Ensure length is greater than or equal to width
            if length < width:
                length, width = width, length

            return [length, width]

    #If no perfect divisors found, return area, 1
    return [area, 1]

Big(O) Analysis

Time Complexity

O(sqrt(area)) – The outer loop iterates from the square root of the area down to 1, checking potential lengths. The inner part of the loop (division and check) takes constant time, O(1). Since the outer loop iterates a maximum of sqrt(area) times, where area is the input, the time complexity is O(sqrt(area)). Therefore, the overall time complexity is driven by the square root of the input area.

Space Complexity

O(1) – The described algorithm operates by iterating through possible length values and checking divisibility. It only uses a few constant space variables to store the potential width and length values, along with the input area. The amount of extra memory used does not depend on the size of the input area N. Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to find two numbers whose product equals a given area, with one number being as close to the square root of the area as possible. This minimizes the difference between the length and width of the rectangle. We can find these numbers by checking downwards from the square root.

Here's how the algorithm would work step-by-step:

Calculate the square root of the area.
Starting from the integer part of the square root, count downwards.
For each number, check if it divides the area evenly.
If a number divides the area evenly, then the other factor is the area divided by that number.
Return the two factors found, with the larger factor listed first.

Code Implementation

import math

def constructRectangle(area):
    side_length = int(math.sqrt(area))

    # Iterate downwards to find a valid length.
    while side_length > 0:
        # Check if side_length is a factor of area.
        if area % side_length == 0:

            width = side_length
            length = area // side_length

            # Ensure the larger value is first
            if length > width:
                return [length, width]
            else:
                return [width, length]

        side_length -= 1

    return []

Big(O) Analysis

Time Complexity

O(sqrt(area)) – The algorithm calculates the square root of the input area. The dominant operation is the loop that starts from the integer part of the square root and counts downwards. In the worst case, it may have to iterate close to the square root of area times before finding a factor. Hence, the time complexity depends on the square root of the area. Therefore, the time complexity is O(sqrt(area)).

Space Complexity

O(1) – The algorithm's space complexity is determined by the extra memory used beyond the input area. Only a few constant-sized variables (the square root of the area, and potentially the two factors found) are stored. The number of variables doesn't scale with the input area, N. Thus the space used is constant.

Edge Cases

Case	How to Handle
Area is zero	Return [0, 0] since this is a valid rectangle with area zero.
Area is a prime number	Iterate only up to the square root to check for divisibility, and then assign width and length appropriately.
Area is a perfect square	Width and length will be the same, so return [sqrt(area), sqrt(area)].
Area is very large (close to max int)	Use long to avoid potential integer overflow during calculations, and ensure values are within constraints upon return.
Area equals 1	The width and length are both 1, so return [1, 1].
Area is a very large number but it factors into small numbers	Check divisors up to the square root to efficiently find factors.
Area is a negative number	Throw an IllegalArgumentException or return null, as area cannot be negative.
Area is near the maximum integer value, and the square root may cause issues with integer precision.	Use Math.sqrt and cast to long to handle large numbers safely and check that the result of squaring the sides equals the input area.

Area is zero

How to Handle:

Return [0, 0] since this is a valid rectangle with area zero.

Area is a prime number

How to Handle:

Iterate only up to the square root to check for divisibility, and then assign width and length appropriately.

Area is a perfect square

How to Handle:

Width and length will be the same, so return [sqrt(area), sqrt(area)].

Area is very large (close to max int)

How to Handle:

Use long to avoid potential integer overflow during calculations, and ensure values are within constraints upon return.

Area equals 1

How to Handle:

The width and length are both 1, so return [1, 1].

Area is a very large number but it factors into small numbers

How to Handle:

Check divisors up to the square root to efficiently find factors.

Area is a negative number

How to Handle:

Throw an IllegalArgumentException or return null, as area cannot be negative.

Area is near the maximum integer value, and the square root may cause issues with integer precision.

How to Handle:

Use Math.sqrt and cast to long to handle large numbers safely and check that the result of squaring the sides equals the input area.