LeetCode 492: Construct the Rectangle Solution in Python – A Step-by-Step Guide

What Is LeetCode 492: Construct the Rectangle?

In LeetCode 492: Construct the Rectangle, you’re given an integer area, representing the total area of a rectangle, and your task is to return a list [L, W] where L (length) and W (width) are positive integers whose product equals area, and L is as close as possible to W while L ≥ W. For example, with area = 12, possible pairs include [12, 1], [6, 2], and [4, 3], and [4, 3] is the closest pair, so you return [4, 3]. It’s like designing a rectangular room with a fixed floor space, aiming for a shape that’s nearly square for balance.

Problem Statement

• Input: area (int)—desired area of the rectangle.
• Output: List[int]—[L, W] where L × W = area, L ≥ W, and L - W is minimized.
• Rules:
• L and W are positive integers.
• L × W = area.
• Among valid pairs, choose L, W where L is closest to W.

Constraints

• \( 1 \leq area \leq 10^7 \).

Examples to Get Us Started

• Input: area = 4
• Output: [2,2] (Pairs: [4,1], [2,2]; [2,2] is closest).
• Input: area = 12
• Output: [4,3] (Pairs: [12,1], [6,2], [4,3]; [4,3] is closest).
• Input: area = 1
• Output: [1,1] (Only pair: [1,1]).

Understanding the Problem: Shaping the Space

To solve LeetCode 492: Construct the Rectangle in Python, we need to find two positive integers L and W whose product equals area, with L ≥ W, and the difference L - W minimized—essentially, the pair closest to a square. A naive approach—testing all factor pairs—could be O(n), slow for area = 10^7. The key? Start from the square root of the area and search downward for the first valid width, ensuring efficiency with O(√n) time. We’ll explore:

• Best Solution (Square Root Optimization with Factor Search): O(√n) time, O(1) space—fast and optimal (n = area).
• Alternative Solution (Brute Force Factor Enumeration): O(n) time, O(1) space—simple but less efficient.

Let’s dive into the square root solution—it’s the architect’s precise ruler we need.

Best Solution: Square Root Optimization with Factor Search

Why This Is the Best Solution

The square root optimization with factor search is the top pick because it’s O(√n) time (n = area) and O(1) space, efficiently finding the closest L and W by starting at the square root of area—the ideal balance point for a square—and adjusting downward to the first valid width, calculating the corresponding length. It avoids checking all factors, leveraging the fact that the closest pair is near √n. It’s like measuring from the middle of the blueprint, tweaking until the perfect fit snaps into place—smart and swift!

How It Works

Here’s the strategy:

• Step 1: Compute initial width \( W = \lfloor \sqrt{area} \rfloor \).
• Step 2: Search downward:
• While \( W > 0 \):
• If area % W == 0 (W is a factor):
• \( L = area / W \).
• If \( L \geq W \), return [L, W].
• Decrement W.
• Step 3: Return [area, 1] as fallback (always valid, but not closest unless area = 1).
• Why It Works:
• \( \sqrt{area} \) is the point where L ≈ W for a square.
• Decreasing W from √area finds the largest W ≤ √area, ensuring L ≥ W and minimal L - W.

Step-by-Step Example

Example: area = 12

• Init: \( W = \lfloor \sqrt{12} \rfloor = 3 \) (since \( \sqrt{12} \approx 3.464 \)).
• W = 3: \( 12 % 3 = 0 \), \( L = 12 / 3 = 4 \), \( L \geq W \), return [4, 3].
• Result: [4, 3] (L - W = 1, closest pair).

Example: area = 4

• W = 2: \( 4 % 2 = 0 \), \( L = 4 / 2 = 2 \), [2, 2].
• Result: [2, 2] (L - W = 0, perfect square).

Example: area = 7

• W = 2: \( 7 % 2 = 1 \), no factor.
• W = 1: \( 7 % 1 = 0 \), \( L = 7 \), [7, 1].
• Result: [7, 1] (prime, widest gap).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeimport math

class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        # Step 1: Start with square root
        w = int(math.sqrt(area))

        # Step 2: Search downward for valid width
        while w > 0:
            if area % w == 0:  # W is a factor
                l = area // w
                if l >= w:  # Ensure L >= W
                    return [l, w]
            w -= 1

        # Step 3: Fallback (won’t reach due to area >= 1)
        return [area, 1]

• Line 6: Compute initial \( W = \lfloor \sqrt{area} \rfloor \).
• Line 9-13: Loop downward:
• If \( area % w == 0 \), compute \( L = area / w \).
• If \( L \geq W \), return [L, W] (first valid pair is closest).
• Decrement W.
• Line 16: Fallback [area, 1] (not needed, area ≥ 1 ensures W = 1 works).
• Time Complexity: O(√n)—searches from √n to 1.
• Space Complexity: O(1)—few variables.

It’s like a blueprint optimizer!

Alternative Solution: Brute Force Factor Enumeration

Why an Alternative Approach?

The brute force factor enumeration—O(n) time, O(1) space—tests all possible widths from 1 to area, computes the corresponding length, and tracks the pair with the smallest L - W difference. It’s slower but intuitive, like measuring every possible room size by hand. Good for small areas or learning!

How It Works

• Step 1: Iterate W from 1 to area.
• Step 2: If W is a factor (area % W == 0):
• Compute L = area / W.
• If L ≥ W, update min difference pair.
• Step 3: Return best [L, W].
• Why It Works:
• Checks all factors, finds closest pair by exhaustive search.

Step-by-Step Example

Example: area = 12

• W = 1: L = 12, diff = 11, pair = [12, 1].
• W = 2: L = 6, diff = 4, pair = [6, 2].
• W = 3: L = 4, diff = 1, pair = [4, 3].
• W = 4: L = 3, L < W, skip.
• Result: [4, 3] (min diff = 1).

Code for Brute Force

Copy codeclass Solution:
    def constructRectangle(self, area: int) -> List[int]:
        min_diff = float('inf')
        best_pair = [area, 1]

        # Step 1-2: Enumerate all factors
        for w in range(1, area + 1):
            if area % w == 0:
                l = area // w
                if l >= w:
                    diff = l - w
                    if diff < min_diff:
                        min_diff = diff
                        best_pair = [l, w]
            if w > l:  # Early break if W exceeds L
                break

        # Step 3: Return best pair
        return best_pair

• Line 4-5: Init min_diff and default pair.
• Line 8-15: Check each W, update if better diff found.
• Line 18: Return best pair.
• Time Complexity: O(n)—tests all numbers up to area.
• Space Complexity: O(1)—few variables.

It’s a slow blueprint drafter!

Comparing the Two Solutions

• Square Root Optimization (Best):
• Pros: O(√n), fast, efficient.
• Cons: Requires math insight.
• Brute Force (Alternative):
• Pros: O(n), intuitive.
• Cons: Much slower for large n.

Square root wins for efficiency.

Edge Cases and Examples

• Input: area=1 → [1,1].
• Input: area=2 → [2,1].
• Input: area=100 → [10,10].

Square root handles all perfectly.

Complexity Recap

• Square Root: Time O(√n), Space O(1).
• Brute Force: Time O(n), Space O(1).

Square root’s the champ.

Key Takeaways

• Square Root: Optimize with math.
• Brute Force: Test all pairs.
• Python Tip: Math speeds—see [Python Basics](/python/basics).

Final Thoughts: Craft That Rectangle

LeetCode 492: Construct the Rectangle in Python is a blueprint-drafting number quest. Square root optimization is your fast ruler, while brute force is a slow sketcher. Want more number challenges? Try LeetCode 509: Fibonacci Number or LeetCode 204: Count Primes. Ready to design some rectangles? Head to Solve LeetCode 492 on LeetCode and craft it today—your coding skills are design-ready!