#3000

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Maximum Area of Longest Diagonal Rectangle

Find the rectangle with the longest diagonal in a 2D array and return its area, prioritizing maximum area on ties.

Problem Statement

Given a 2D 0-indexed array dimensions, where each element dimensions[i] contains exactly two integers representing the length and width of rectangle i, determine the rectangle with the longest diagonal.

Return the area of this rectangle. If multiple rectangles share the longest diagonal length, return the area of the rectangle with the largest area. Each dimension value is guaranteed to be between 1 and 100, and there is at least one rectangle.

Examples

Example 1

Input: dimensions = [[9,3],[8,6]]

Output: 48

For index = 0, length = 9 and width = 3. Diagonal length = sqrt(9 * 9 + 3 * 3) = sqrt(90) ≈ 9.487. For index = 1, length = 8 and width = 6. Diagonal length = sqrt(8 * 8 + 6 * 6) = sqrt(100) = 10. So, the rectangle at index 1 has a greater diagonal length therefore we return area = 8 * 6 = 48.

Example 2

Input: dimensions = [[3,4],[4,3]]

Output: 12

Length of diagonal is the same for both which is 5, so maximum area = 12.

Constraints

1 <= dimensions.length <= 100
dimensions[i].length == 2
1 <= dimensions[i][0], dimensions[i][1] <= 100

Solution Approach

Compute Diagonals Using Pythagoras

Iterate over each rectangle and calculate its diagonal using sqrt(length^2 + width^2). Store both the diagonal length and corresponding area for comparison.

Track Maximum Diagonal and Area

Maintain variables for the longest diagonal found and the largest area seen at that diagonal. Update these values whenever a longer diagonal or equal diagonal with larger area is found.

Return the Area of Selected Rectangle

After scanning all rectangles, return the area stored for the rectangle with the longest diagonal. This ensures ties are resolved in favor of maximum area.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each rectangle is processed once. Space complexity is O(1) extra space because only a few variables track maximums.

What Interviewers Usually Probe

Check that you are correctly computing diagonal lengths using the formula sqrt(length^2 + width^2).
Clarify how you resolve ties when multiple rectangles have the same diagonal length.
Consider edge cases with minimal or maximal rectangle dimensions to ensure correctness.

Common Pitfalls or Variants

Common pitfalls

Comparing areas without considering diagonal lengths first can lead to incorrect results.
Using integer division instead of floating point sqrt can cause precision errors when comparing diagonals.
Failing to update the maximum area for rectangles with equal diagonal lengths will return the wrong rectangle.

Follow-up variants

Find the rectangle with the shortest diagonal instead, prioritizing minimal area on ties.
Return both the dimensions and area of the rectangle with the longest diagonal for additional output clarity.
Compute diagonals without using sqrt by comparing squares of diagonals to avoid floating point calculations.

FAQ

How is the longest diagonal determined in Maximum Area of Longest Diagonal Rectangle?

Calculate each rectangle's diagonal using sqrt(length^2 + width^2) and identify the maximum value. Ties are resolved using the largest area.

Can two rectangles have the same diagonal length?

Yes, when this happens, the rectangle with the larger area is returned according to problem rules.

Is there a way to avoid using floating point sqrt?

Compare squares of the diagonals instead of computing sqrt to maintain integer comparisons and improve precision.

What is the time complexity for this array-driven approach?

It is O(n) because each rectangle is scanned once and constant space is used for tracking maximums.

What common mistakes should I avoid for this diagonal comparison problem?

Do not prioritize area before diagonal length, avoid integer division rounding errors, and ensure tie-breaking logic is applied correctly.

terminal

Solution

Solution 1: Mathematics

According to the Pythagorean theorem, the square of the diagonal of a rectangle is $l^2 + w^2$, where $l$ and $w$ are the length and width of the rectangle, respectively.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        ans = mx = 0
        for l, w in dimensions:
            t = l**2 + w**2
            if mx < t:
                mx = t
                ans = l * w
            elif mx == t:
                ans = max(ans, l * w)
        return ans

Continue Practicing

#3002 maximum size of a set after removals #2997 minimum number of operations to make array xor equal to k #2996 smallest missing integer greater than sequential prefix sum