algoadvance

Leetcode 492. Construct the Rectangle

Problem Statement

Given an area area, design a rectangular web page, whose length L and width W satisfy the following requirements:

  1. The area of the rectangle must be equal to the given area.
  2. The width W should not be larger than the length L, meaning L >= W.
  3. The difference between L and W should be as small as possible.

Return an array [L, W] where L and W are the length and width of the rectangle.

Clarifying Questions

  1. Is the area guaranteed to be a positive integer?
    • Yes.
  2. Can the length and width be the same?
    • Yes, if a perfect square root exists.
  3. Are we guaranteed that there will be a pair (L, W) such that L * W = area and L >= W?
    • Yes, since the area is a positive integer, there will always exist at least one valid pair.

Strategy

To solve this problem, we need to find two integers L and W such that L * W = area, L >= W, and the difference (L - W) is minimized.

Steps:

  1. Start from the integer closest to the square root of the area and iterate downwards to find the first factor of the area.
  2. For any factor W found, calculate L as L = area / W.
  3. Store the pair (L, W) and return it as soon as we find a valid pair, since we are moving downwards from the square root, this ensures that (L - W) is minimized.

The reason for iterating from the square root downwards is that the factors closest to the square root will have the smallest difference.

Code

#include <cmath>
#include <vector>
#include <iostream>

std::vector<int> constructRectangle(int area) {
    int w = static_cast<int>(std::sqrt(area));
    while (area % w != 0) {
        w--;
    }
    
    int l = area / w;
    return {l, w};
}

int main() {
    int area = 4;
    std::vector<int> result = constructRectangle(area);
    
    std::cout << "Length: " << result[0] << ", Width: " << result[1] << std::endl;
    return 0;
}

Time Complexity

This solution provides a balanced, minimal and efficient way to find the desired dimensions for the rectangle.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI