492. Construct the Rectangle

Problem Description

A web developer is tasked with designing a rectangular web page, where the challenge lies in determining the length (L) and width (W) of the page. These dimensions must meet three specific conditions:

The rectangular web page's area, that is, L * W, must be exactly equal to a given target area.
The width (W) should not exceed the length (L), which means the layout should either be a square or a landscape-oriented rectangle (L >= W).
The absolute difference between the length and width should be minimized to make the dimensions as close to a square as possible, which usually is aesthetically pleasing and often a desired trait in web page design.

The final output should be presented as an array [L, W], indicating the length and width of the website's page, respectively.

Intuition

To solve this problem, we can leverage the mathematical fact that for any given rectangular area, if we're trying to minimize the difference between length and width, the best approach is to aim for a shape that is as close to a square as possible. This is because, for a fixed area, a square has the smallest perimeter out of all possible rectangles.

By that logic, we should start looking for the optimal width W by considering the largest possible square that could fit in the given area, which would be a square whose sides are equal to the square root of the area. However, since the area may not be a perfect square, we look for the greatest divisor of the area that is less than or equal to the square root because this would give us the width that is closest to the length, thereby minimizing their difference.

Here's how the code reflects this intuition:

Compute an initial width W by taking the integer square root of the area, since decimals aren't permissible for the height or width of a web page.
Verify if this width is indeed a divisor of the area by checking the remainder of the division of the area by W.
If it's not, decrement the width W by 1, and repeat this step until a divisor is found.
Once the proper width W is found (where area % W == 0), calculate the corresponding length L by dividing the area by W.
Return the pair [L, W] as the result, with L being the larger value and W being the smaller or equal value.

This approach ensures that the shape of the rectangle will be as close to a square as possible, adhering to the web developer's needs.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The implementation of the solution is quite straightforward, with no need for advanced data structures or complex algorithms. Here is the breakdown of the code provided in the solution:

1class Solution:
2    def constructRectangle(self, area: int) -> List[int]:
3        w = int(sqrt(area))  # Starting from the largest possible square
4        while area % w != 0: # Continue until a divisor is found
5            w -= 1           # Decrement width by 1
6        return [area // w, w] # Calculate length and return result

Finding the Width (W): The initial width is guessed by taking the integer part of the square root of the area (int(sqrt(area))). This is based on the idea that for a rectangle with a given area, the configuration closest to a square will minimize the difference between length and width.
Validating Width (W): Since the initial guess may not be the exact width (unless the area itself is a perfect square), a while loop verifies if the current width exactly divides the area (area % w == 0).
Iterative Approach: If the current width isn't a divisor of the area (meaning area % w != 0), decrement the width (w) by one, and recheck. Continue this process until you find the largest divisor of the area that is less than or equal to the square root of the area.
Calculating Length (L): Once a suitable width (W) is found, calculate the corresponding length by dividing the area by this width (area // w).
Returning the Result: The resulting L and W are packed into a list in the correct order ([L, W]), since by definition, L must be equal to or larger than W.

The simplicity of this solution lies in the fact that for a given area, as W decreases, L increases proportionally because area = L * W. Thus, starting from the square root of the area and going downwards ensures we're approaching the smallest potential difference between the L and W.

The use of iteration and simple arithmetic operations make the algorithm effective and efficient with a time complexity of approximately O(√n), where n is the given area. It stops as soon as a divisor is found, and no additional space is necessary, hence space complexity is O(1).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Example Walkthrough

Let's consider a small example where the target area of our web page is 20. We want to find the dimensions [L, W] that satisfy our three conditions:

The area equals 20 (i.e., L * W = 20).
The width W is less than or equal to the length L (L >= W).
The absolute difference between length and width is minimized.

Following the solution approach:

We start by finding the initial guess for the width W through the square root of the area. The square root of 20 is approximately 4.47. Taking the integer part gives us 4.
We must verify if 4 is a divisor of 20 by checking if 20 % 4 == 0. Indeed it is, as 20 divided by 4 leaves no remainder.
Since 4 is a divisor, there's no need for the iterative approach to decrement the width and check for other possible divisors.
We calculate the corresponding length L by dividing the area by the width: 20 // 4 = 5.
We then pack our dimensions [L, W] into an array. In this case, [5, 4].

The dimensions of the web page that satisfy the given requirements are a length of 5 and a width of 4, which gives us the smallest possible difference between length and width (minimizing the absolute difference), and also L * W equals the target area of 20. Hence, the final output for this example is [5, 4].

This example illustrates on a smaller scale, how the algorithm effectively finds the ideal dimensions for the web page by starting from the largest possible square root and verifying if it's an exact divisor of the given area. If not, it systematically explores smaller values of width to find the optimal dimensions, satisfying all three conditions.

Solution Implementation

1from math import sqrt
2from typing import List
3
4class Solution:
5    def constructRectangle(self, area: int) -> List[int]:
6        # Find the square root of the given area and cast it to an integer.
7        # This is the starting point to search for the width because the largest
8        # possible width (w) that's less than or equal to the length (l)
9        # is when l == w (i.e., a square).
10        width = int(sqrt(area))
11
12        # Iterate by decreasing width to find the largest possible width
13        # that evenly divides the given area (i.e., area % width == 0).
14        # This is done to ensure the length is at least as large as the width,
15        # as per problem constraints.
16        while area % width != 0:
17            width -= 1
18
19        # Calculate the corresponding length by dividing the area by width.
20        length = area // width
21
22        # Return the dimensions [length, width] as a list, where length >= width.
23        return [length, width]
24

1class Solution {
2
3    // Method to construct a rectangle with a given area that is as close to a square as possible
4    public int[] constructRectangle(int area) {
5        // Start with the largest possible square root of the area as the width
6        int width = (int) Math.sqrt(area);
7
8        // Decrease the width until we find a value that perfectly divides the area
9        while (area % width != 0) {
10            --width;
11        }
12      
13        // Since width is the smaller dimension, it is placed second in the array
14        // The corresponding length is calculated by dividing the area by width
15        return new int[] {area / width, width};
16    }
17}
18

1#include <vector>
2#include <cmath> // Include cmath for using the sqrt function
3
4class Solution {
5public:
6    // This function constructs a rectangle of the given area.
7    // The rectangle's length is greater than or equal to its width,
8    // and the difference between length and width is minimized.
9    vector<int> constructRectangle(int area) {
10        // Use integer sqrt function to find the square root of the area,
11        // which is the best starting point for the width (w).
12        int width = static_cast<int>(sqrt(area));
13      
14        // Loop to find the largest width which divides the area with no remainder.
15        while (area % width != 0) {
16            --width; // Reduce the width by one and check again.
17        }
18      
19        // Width found, calculate length by dividing the area by width.
20        // Return the pair {length, width} as the result.
21        return {area / width, width};
22    }
23};
24

1function constructRectangle(area: number): number[] {
2    // Find the square root of the area, which serves as the starting point for the possible width of the rectangle.
3    let width: number = Math.floor(Math.sqrt(area));
4  
5    // Loop to find the greatest width that evenly divides the area
6    while (area % width !== 0) {
7        width--; // Decrement the width and verify again
8    }
9  
10    // Once the width is found, calculate the length by dividing the area by this width
11    const length: number = area / width;
12  
13    // Return an array containing the length and width of the rectangle
14    return [length, width];
15}
16

Not Sure What to Study? Take the 2-min Quiz：

What's the relationship between a tree and a graph?

A graph is a special treeA tree is a special graphNo relationshipThey are the same thing

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code largely depends on the number of iterations in the while loop. Initially, it finds the square root of the area, which is executed in constant time, i.e., O(1). After that, it decrements w until it finds a divisor of the area. In the worst case, this will occur when the area is a prime number, and w will be decremented down to 1, which would make the total number of iterations approximately sqrt(area) in the worst case. Therefore, the time complexity is O(sqrt(area)).

Space Complexity

The space complexity is O(1) because only a fixed amount of extra space is used, regardless of the input size. The variables w and the array that is returned do not increase with the size of the input area.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

492. Construct the Rectangle

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings