We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Area of Longest Diagonal Rectangle

Number: 3251

Difficulty: Easy

Paid? No

Companies: Adobe, Accenture

Problem Description

Given a list of rectangles with specified length and width, determine the rectangle that has the longest diagonal. If multiple rectangles have the same diagonal length, choose the rectangle with the larger area. Return the area of that rectangle.

Key Insights

  • Diagonal length of a rectangle can be computed using the Pythagorean theorem: diagonal = sqrt(length² + width²).
  • To avoid unnecessary floating point operations, the square of the diagonal (length² + width²) can be used for comparisons.
  • Track both the maximum diagonal squared value and the maximum area encountered for that diagonal.
  • Only one pass through the list is required, leading to an efficient solution.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of rectangles. Space Complexity: O(1) - only a few variables are used for tracking the maximums.

Solution

The solution involves iterating over each rectangle in the input list and computing the square of its diagonal (length² + width²) to compare lengths without computing the square root. Along with this, calculate the area (length * width). During iteration, maintain two variables: one for the best (largest) diagonal squared value and one for the best area corresponding to that diagonal length. If a rectangle has a larger diagonal squared value, update both variables. If a rectangle has the same diagonal squared value, update the best area if its area is larger than the current best area. Finally, return the best area found.

Code Solutions

# Python solution for Maximum Area of Longest Diagonal Rectangle
def max_area_of_longest_diagonal_rectangle(dimensions):
    # Initialize the maximum diagonal squared value and maximum area for that diagonal.
    max_diagonal_sq = 0
    max_area = 0
    
    # Iterate through each rectangle.
    for dimension in dimensions:
        length = dimension[0]  # Get length
        width = dimension[1]   # Get width
        
        # Compute diagonal squared (avoid floating point sqrt for comparison)
        current_diagonal_sq = length * length + width * width
        
        # Compute area of the rectangle.
        current_area = length * width
        
        # Check if the current diagonal is larger than the max found so far.
        if current_diagonal_sq > max_diagonal_sq:
            max_diagonal_sq = current_diagonal_sq
            max_area = current_area
        # If diagonal is equal, choose the rectangle with the greater area.
        elif current_diagonal_sq == max_diagonal_sq:
            max_area = max(max_area, current_area)
    
    return max_area

# Example usage:
dimensions = [[9,3],[8,6]]
print(max_area_of_longest_diagonal_rectangle(dimensions))  # Output: 48
← Back to All Questions