Scale Engineer

Construct the Rectangle

Easy
#0479Time: O(area). The loop runs up to `area` times. This is very inefficient for the given constraints (area up to 10^7) and will likely result in a Time Limit Exceeded error.Space: O(1). We only use a constant amount of extra space for variables to store the best pair and the loop counter.
Patterns
Math

Prompt

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:

  1. The area of the rectangular web page you designed must equal to 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.

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 <= 107

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, exhaustive search. We check every possible integer for the width W, starting from 1 up to the given area. For each potential width, we determine if it's a valid divisor. If it is, we calculate the corresponding length L and check if it forms a valid rectangle (L >= W). We keep track of the pair [L, W] that has the smallest difference L - W found so far.

Algorithm

  • Initialize best_L to area and best_W to 1.
  • Iterate through possible widths w from 1 up to area.
  • For each w, check if it is a divisor of area (i.e., area % w == 0).
  • If it is a divisor, calculate the corresponding length l = area / w.
  • Check if the condition l >= w is met.
  • If it is, compare the current difference l - w with the best difference found so far, best_L - best_W.
  • If l - w is smaller, update best_L = l and best_W = w.
  • After the loop, return [best_L, best_W].

Walkthrough

The algorithm begins by initializing a variable to store the minimum difference found, setting it to a very large value. It also initializes an array to hold the best [L, W] pair, which can be seeded with [area, 1]. Then, it iterates with a width w from 1 up to area. In each iteration, it checks if w divides area evenly. If it does, it calculates the length l = area / w. The condition l >= w is then verified. If this holds, the difference l - w is compared to the stored minimum difference. If the new difference is smaller, the minimum difference is updated, and the result array is set to [l, w]. After checking all possible widths up to area, the stored result array will contain the optimal dimensions.

class Solution {    public int[] constructRectangle(int area) {        int minDiff = Integer.MAX_VALUE;        int[] result = new int[2];         for (int w = 1; w <= area; w++) {            if (area % w == 0) {                int l = area / w;                if (l >= w) {                    if (l - w < minDiff) {                        minDiff = l - w;                        result[0] = l;                        result[1] = w;                    }                }            }        }        return result;    }}

Complexity

Time

O(area). The loop runs up to `area` times. This is very inefficient for the given constraints (area up to 10^7) and will likely result in a Time Limit Exceeded error.

Space

O(1). We only use a constant amount of extra space for variables to store the best pair and the loop counter.

Trade-offs

Pros

    • Simple to conceptualize and implement.
    • Guaranteed to find the correct answer, given enough time.

Cons

    • Extremely inefficient for large inputs.
    • The search space is unnecessarily large and will not pass the time limits for this problem.

Solutions

class Solution {public  int[] constructRectangle(int area) {    int w = (int)Math.sqrt(area);    while (area % w != 0) {      --w;    }    return new int[]{area / w, w};  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem