LeetCode Problem 3000

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 3000 - Maximum Area of Longest Diagonal Rectangle

Problem Understanding

The input consists of a 2D array dimensions, where each element represents a rectangle. For a rectangle dimensions[i], the value dimensions[i][0] is its length and dimensions[i][1] is its width.

For every rectangle, we can compute the length of its diagonal using the Pythagorean theorem:

$$\text{diagonal} = \sqrt{length^2 + width^2}$$

The problem asks us to find the rectangle with the longest diagonal and return its area.

There is an additional tie-breaking rule. If multiple rectangles have the same diagonal length, we must choose the one with the largest area. The area of a rectangle is:

$$\text{area} = length \times width$$

The constraints are very small:

• At most 100 rectangles.
• Each dimension is at most 100.

This means we can easily examine every rectangle individually without worrying about performance.

A key observation is that we do not actually need to compute square roots. Since the square root function is strictly increasing, comparing diagonal lengths is equivalent to comparing:

$$length^2 + width^2$$

This avoids floating point arithmetic and makes the solution simpler and more precise.

Important edge cases include situations where multiple rectangles share the same diagonal length, where only one rectangle exists, and where different rectangles have equal diagonals but different areas.

Approaches

Brute Force Approach

A straightforward approach is to compute the actual diagonal length of every rectangle using the square root formula. While iterating through the rectangles, we keep track of the largest diagonal seen so far and the corresponding area.

If we encounter a rectangle with a larger diagonal, we update our answer. If we encounter a rectangle with the same diagonal, we compare areas and keep the larger one.

This approach is correct because it explicitly evaluates every rectangle and applies the problem's selection rules.

The only drawback is that it performs unnecessary square root calculations. Although the constraints are tiny and the solution is still fast enough, we can simplify the implementation further.

Key Insight

To compare diagonals, we do not need their actual lengths.

Since:

$$\sqrt{a} > \sqrt{b}$$

if and only if

$$a > b$$

we can compare the squared diagonal values:

$$length^2 + width^2$$

instead of the actual diagonals.

This eliminates floating point operations while preserving exactly the same ordering of rectangles.

We then apply the same tie-breaking rule using the rectangle area.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Computes actual diagonals using square roots
Optimal	O(n)	O(1)	Compares squared diagonals and avoids floating point arithmetic

Algorithm Walkthrough

1. Initialize max_diagonal_squared to 0.
2. Initialize best_area to 0.
3. Iterate through every rectangle in dimensions.
4. For the current rectangle, extract its length and width.
5. Compute its squared diagonal as:

$$diagonalSquared = length^2 + width^2$$ 6. Compute its area:

$$area = length \times width$$ 7. If diagonalSquared is greater than max_diagonal_squared, update both:

• max_diagonal_squared
• best_area

This rectangle now has the longest diagonal seen so far. 8. If diagonalSquared equals max_diagonal_squared, compare the areas and keep the larger one. 9. After processing all rectangles, return best_area.

Why it works

The algorithm maintains the invariant that after processing any prefix of the input, max_diagonal_squared stores the largest squared diagonal encountered and best_area stores the largest area among all rectangles having that diagonal.

Because every rectangle is examined exactly once and the update rules exactly match the problem statement, the final value of best_area is the area of the rectangle with the longest diagonal, breaking ties by maximum area.

Python Solution

from typing import List

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        max_diagonal_squared = 0
        best_area = 0

        for length, width in dimensions:
            diagonal_squared = length * length + width * width
            area = length * width

            if diagonal_squared > max_diagonal_squared:
                max_diagonal_squared = diagonal_squared
                best_area = area
            elif diagonal_squared == max_diagonal_squared:
                best_area = max(best_area, area)

        return best_area

The implementation follows the algorithm directly.

The variables max_diagonal_squared and best_area track the best rectangle encountered so far. For each rectangle, we compute its squared diagonal and area.

When a larger squared diagonal is found, both tracking variables are updated. When the diagonal ties with the current maximum, only the area is compared. At the end of the loop, best_area contains the required answer.

Using squared diagonals avoids floating point arithmetic entirely while preserving correct comparisons.

Go Solution

func areaOfMaxDiagonal(dimensions [][]int) int {
    maxDiagonalSquared := 0
    bestArea := 0

    for _, rect := range dimensions {
        length := rect[0]
        width := rect[1]

        diagonalSquared := length*length + width*width
        area := length * width

        if diagonalSquared > maxDiagonalSquared {
            maxDiagonalSquared = diagonalSquared
            bestArea = area
        } else if diagonalSquared == maxDiagonalSquared {
            if area > bestArea {
                bestArea = area
            }
        }
    }

    return bestArea
}

The Go implementation mirrors the Python solution closely. Since all dimensions are at most 100, the largest squared diagonal is only 100² + 100² = 20000, which easily fits within Go's int type. No special overflow handling is required.

The input is guaranteed to contain at least one rectangle, so no additional empty-input checks are necessary.

Worked Examples

Example 1

Input:

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

Rectangle	Diagonal Squared	Area	max_diagonal_squared	best_area
[9,3]	81 + 9 = 90	27	90	27
[8,6]	64 + 36 = 100	48	100	48

The second rectangle has the larger diagonal.

Result:

48

Example 2

Input:

dimensions = [[3,4],[4,3]]

Rectangle	Diagonal Squared	Area	max_diagonal_squared	best_area
[3,4]	9 + 16 = 25	12	25	12
[4,3]	16 + 9 = 25	12	25	12

Both rectangles have the same diagonal and the same area.

Result:

12

Additional Example

Input:

dimensions = [[1,7],[5,5]]

Rectangle	Diagonal Squared	Area
[1,7]	50	7
[5,5]	50	25

The diagonals are equal, so we choose the larger area.

Result:

25

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each rectangle is processed exactly once
Space	O(1)	Only a few variables are maintained

The algorithm performs a single pass through the input. Every iteration does a constant amount of work, consisting of a few arithmetic operations and comparisons. No auxiliary data structures are used, so the space usage remains constant.

Test Cases

from typing import List

s = Solution()

assert s.areaOfMaxDiagonal([[9, 3], [8, 6]]) == 48  # Example 1
assert s.areaOfMaxDiagonal([[3, 4], [4, 3]]) == 12  # Example 2

assert s.areaOfMaxDiagonal([[5, 5]]) == 25  # Single rectangle
assert s.areaOfMaxDiagonal([[1, 7], [5, 5]]) == 25  # Same diagonal, larger area wins
assert s.areaOfMaxDiagonal([[10, 1], [8, 6]]) == 48  # Larger diagonal wins despite area
assert s.areaOfMaxDiagonal([[2, 8], [8, 2], [4, 7]]) == 28  # Later rectangle has larger diagonal
assert s.areaOfMaxDiagonal([[100, 100]]) == 10000  # Maximum dimensions
assert s.areaOfMaxDiagonal([[6, 8], [10, 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0]]) == 150  # Different diagonals
assert s.areaOfMaxDiagonal([[1, 1], [2, 2], [3, 3]]) == 9  # Increasing diagonals
assert s.areaOfMaxDiagonal([[8, 15], [15, 8], [12, 16]]) == 192  # Equal diagonals, largest area

Test Summary

Test	Why
[[9,3],[8,6]]	Validates basic comparison of diagonals
[[3,4],[4,3]]	Validates tie on diagonal and area
[[5,5]]	Single rectangle input
[[1,7],[5,5]]	Tie on diagonal, choose larger area
[[10,1],[8,6]]	Longer diagonal beats smaller one regardless of area
[[2,8],[8,2],[4,7]]	Best rectangle appears later in input
[[100,100]]	Maximum dimension values
Large diagonal comparison case	Confirms diagonal comparison logic
[[1,1],[2,2],[3,3]]	Continuously improving diagonals
[[8,15],[15,8],[12,16]]	Multiple equal diagonals with different areas

Edge Cases

Only One Rectangle

When the input contains exactly one rectangle, that rectangle automatically has the longest diagonal. A buggy implementation might assume comparisons are always needed. This solution correctly initializes the tracking variables and updates them during the first iteration, returning the single rectangle's area.

Multiple Rectangles With Identical Diagonals

Different rectangles can have the same diagonal length. For example, [1,7] and [5,5] both have a squared diagonal of 50. The problem requires selecting the rectangle with the larger area. The equality branch explicitly handles this case by comparing areas.

Equal Dimensions in Different Orders

Rectangles such as [3,4] and [4,3] represent the same geometric rectangle and therefore have the same diagonal and area. The algorithm treats them independently but arrives at the correct result because both calculations produce identical values.

Maximum Constraint Values

The largest possible dimensions are 100 × 100. The squared diagonal becomes 10000 + 10000 = 20000, which is safely within the range of standard integer types in both Python and Go. Therefore, no overflow concerns exist under the given constraints.

Avoiding Floating Point Precision Issues

A common implementation computes diagonals using square roots and compares floating point numbers. Although the constraints are small, comparing squared diagonals is cleaner and avoids any possibility of precision-related bugs. The solution relies entirely on integer arithmetic while producing identical ordering of rectangles.