Problem Description

You are given a 2D array called dimensions where each element represents a rectangle. For each rectangle at index i, dimensions[i][0] is the length and dimensions[i][1] is the width.

Your task is to find the rectangle with the longest diagonal. The diagonal of a rectangle can be calculated using the Pythagorean theorem: diagonal = √(length² + width²).

If there are multiple rectangles that share the same longest diagonal length, you should return the area of the rectangle with the maximum area among them.

The area of a rectangle is calculated as length × width.

For example, if you have rectangles with dimensions [3, 4] and [5, 12], their diagonals would be √(9 + 16) = 5 and √(25 + 144) = 13 respectively. The second rectangle has the longer diagonal, so you would return its area: 5 × 12 = 60.

If two rectangles have the same diagonal length, like [3, 4] (diagonal = 5, area = 12) and [4, 3] (diagonal = 5, area = 12), you return the maximum area, which is 12 in this case.

Intuition

To find the rectangle with the longest diagonal, we need to compare diagonals of all rectangles. Since the diagonal of a rectangle forms the hypotenuse of a right triangle with its length and width as the two sides, we can use the Pythagorean theorem: diagonal² = length² + width².

A key observation is that we don't actually need to calculate the exact diagonal length using square root. Since square root is a monotonically increasing function, if a² > b², then √a² > √b². This means we can simply compare length² + width² values directly without taking the square root, which saves computation and avoids floating-point precision issues.

As we iterate through each rectangle, we need to track two things:

1. The maximum diagonal squared value we've seen so far
2. The area of the rectangle with that maximum diagonal

When we encounter a new rectangle:

• If its diagonal squared is greater than our current maximum, we update both the maximum diagonal squared and store this rectangle's area as our answer
• If its diagonal squared equals our current maximum (meaning multiple rectangles have the same longest diagonal), we compare areas and keep the larger one
• If its diagonal squared is less than our maximum, we simply skip it

This single-pass approach ensures we find the rectangle with the longest diagonal, and among those with equal longest diagonals, we select the one with maximum area.

Solution Approach

We implement a single-pass solution that iterates through all rectangles once, maintaining two variables:

• mx: tracks the maximum diagonal squared value seen so far
• ans: stores the area of the rectangle with the longest diagonal

For each rectangle with length l and width w:

1. Calculate the diagonal squared: t = l² + w²

   • We compute l**2 + w**2 instead of taking the square root to avoid unnecessary computation and maintain precision

2. Compare with current maximum diagonal:

   • If t > mx: We found a rectangle with a longer diagonal
     • Update mx = t to store the new maximum diagonal squared
     • Update ans = l * w to store this rectangle's area
   • If t == mx: We found another rectangle with the same diagonal length
     • Keep mx unchanged since the diagonal is the same
     • Update ans = max(ans, l * w) to keep the larger area between the current answer and this rectangle's area
   • If t < mx: This rectangle's diagonal is shorter than our current maximum, so we skip it

3. Return the result: After checking all rectangles, ans contains the area of the rectangle with the longest diagonal (or the maximum area if multiple rectangles share the longest diagonal)

The algorithm runs in O(n) time where n is the number of rectangles, and uses O(1) extra space since we only maintain two variables regardless of input size.

Example Walkthrough

Let's walk through the solution with a small example: dimensions = [[4, 3], [3, 4], [4, 5], [5, 12]]

Initial state:

• mx = 0 (maximum diagonal squared seen so far)
• ans = 0 (area of rectangle with longest diagonal)

Rectangle 1: [4, 3]

• Calculate diagonal squared: t = 4² + 3² = 16 + 9 = 25
• Since t (25) > mx (0), we found our first rectangle:
  • Update mx = 25
  • Update ans = 4 × 3 = 12

Rectangle 2: [3, 4]

• Calculate diagonal squared: t = 3² + 4² = 9 + 16 = 25
• Since t (25) == mx (25), same diagonal length as current maximum:
  • Keep mx = 25
  • Compare areas: ans = max(12, 3 × 4) = max(12, 12) = 12

Rectangle 3: [4, 5]

• Calculate diagonal squared: t = 4² + 5² = 16 + 25 = 41
• Since t (41) > mx (25), we found a longer diagonal:
  • Update mx = 41
  • Update ans = 4 × 5 = 20

Rectangle 4: [5, 12]

• Calculate diagonal squared: t = 5² + 12² = 25 + 144 = 169
• Since t (169) > mx (41), we found an even longer diagonal:
  • Update mx = 169
  • Update ans = 5 × 12 = 60

Result: Return 60, which is the area of the rectangle [5, 12] that has the longest diagonal (√169 = 13).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of rectangles in the dimensions list. The algorithm iterates through each rectangle exactly once, performing constant-time operations (calculating the diagonal squared with l**2 + w**2, computing area with l * w, and comparing values) for each rectangle.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space with variables ans, mx, l, w, and t, regardless of the input size. No additional data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Floating-Point Square Root Calculation

Pitfall: Computing the actual diagonal using sqrt(length**2 + width**2) and comparing floating-point values.

# Problematic approach
import math

max_diagonal = 0
max_area = 0

for length, width in dimensions:
    diagonal = math.sqrt(length**2 + width**2)  # Unnecessary and risky!
  
    if diagonal > max_diagonal:
        max_diagonal = diagonal
        max_area = length * width
    elif diagonal == max_diagonal:  # Floating-point equality comparison - dangerous!
        max_area = max(max_area, length * width)

Issues:

• Floating-point arithmetic can introduce precision errors
• Comparing floating-point numbers for equality is unreliable
• Square root calculation is computationally expensive and unnecessary

Solution: Compare squared values directly to avoid floating-point operations entirely.

# Correct approach - compare squared values
current_diagonal_squared = length**2 + width**2
if max_diagonal_squared < current_diagonal_squared:
    # Process without ever computing the actual diagonal

2. Forgetting to Update Area When Finding Equal Diagonals

Pitfall: Only updating the area when finding a strictly longer diagonal, ignoring rectangles with equal diagonal lengths.

# Incorrect - misses equal diagonal case
for length, width in dimensions:
    current_diagonal_squared = length**2 + width**2
  
    if current_diagonal_squared > max_diagonal_squared:
        max_diagonal_squared = current_diagonal_squared
        max_area = length * width
    # Missing the elif case for equal diagonals!

Solution: Always handle the equal diagonal case explicitly with an elif statement to compare areas.

# Correct - handles both greater and equal cases
if current_diagonal_squared > max_diagonal_squared:
    max_diagonal_squared = current_diagonal_squared
    max_area = length * width
elif current_diagonal_squared == max_diagonal_squared:
    max_area = max(max_area, length * width)  # Keep the larger area

3. Incorrect Initial Values

Pitfall: Initializing with non-zero values when the problem doesn't guarantee positive dimensions, or initializing with values that could be valid outputs.

# Potentially problematic if dimensions could be 0 or negative
max_diagonal_squared = -1  # What if all diagonals are 0?
max_area = -1  # Could mask edge cases

Solution: Initialize both tracking variables to 0, which works correctly since:

• All valid rectangles will have non-negative dimensions
• The first rectangle will always update both values appropriately
• Zero initialization handles edge cases naturally