Skip to main content
Talentd

Maximum Area of Longest Diagonal Rectangle - Solution & Explanation

EasyArray17 min readAsked at: Amazon, Meta, Accenture +2
Practice this problem

Problem Statement

You are given a 2D 0-indexed integer array dimensions.

For all indices i, 0 <= i < dimensions.length, dimensions[i][0] represents the length and dimensions[i][1] represents the width of the rectangle i.

Return the area of the rectangle having the longest diagonal. If there are multiple rectangles with the longest diagonal, return the area of the rectangle having the maximum area.

 

Example 1:

Input: dimensions = [[9,3],[8,6]]
Output: 48
Explanation: 
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
Explanation: 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

Approach Overview

Problem Overview: You receive a list of rectangles where each element contains the length and width. The task is to identify the rectangle with the longest diagonal. If multiple rectangles share the same diagonal length, return the one with the largest area.

The diagonal of a rectangle comes from the Pythagorean theorem: diagonal = sqrt(l^2 + w^2). Instead of building complex data structures, the solution simply iterates through the rectangles and keeps track of the best candidate based on diagonal length and area.

Approach 1: Naive Linear Search (O(n) time, O(1) space)

Scan the list once and compute the diagonal for each rectangle using sqrt(l*l + w*w). Maintain two variables while iterating: the longest diagonal seen so far and the corresponding maximum area. For each rectangle, compare its diagonal with the current maximum. If the diagonal is larger, update both the diagonal and area. If the diagonal is equal, update only when the rectangle’s area is larger. This approach is straightforward and works well because the problem requires only a single pass over the input array. It relies on basic iteration over an array and simple arithmetic from math.

Approach 2: Precompute Diagonal Squares (O(n) time, O(1) space)

Computing square roots repeatedly is unnecessary because comparing diagonals does not require the actual value. Instead, compare l*l + w*w directly. These squared values preserve ordering and eliminate the cost of sqrt. During the iteration, compute the diagonal square for each rectangle and compare it with the current maximum diagonal square. If a larger value appears, update the stored area. If the squared diagonal matches the current best, compare rectangle areas and keep the larger one. This approach improves efficiency slightly and avoids floating‑point operations. It still uses a single pass through the array and constant memory while applying basic geometry reasoning.

Recommended for interviews: Start with the linear scan idea because it shows you recognize the problem reduces to comparing diagonals. Then mention that square roots are unnecessary and replace them with diagonal squares. Interviewers typically expect the optimized comparison because it demonstrates awareness of numeric optimization while keeping the algorithm at O(n) time and O(1) space.

Approach 1: Approach 1: Naive Linear Search

In this approach, we will iterate through all the given rectangles, compute the diagonal for each rectangle using the Pythagorean theorem, and keep track of the longest diagonal and corresponding area. If a longer diagonal is found, or if the diagonal length is the same but the area is larger, we will update our result.

The program iterates over each rectangle in the dimensions array, computes the diagonal using the Pythagorean theorem, and measures the area by multiplying its length and width. It maintains the maximum diagonal and respective area found so far.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of rectangles.
Space Complexity: O(1) as no additional data structures are used.

Try this approach in the editor →

Approach 2: Approach 2: Precompute Diagonal Squares

Instead of calculating the square root for diagonal lengths during each comparison, precompute the square of the diagonals for all rectangles. This avoids the computational complexity of repeatedly taking square roots, making comparisons faster (using diagonal squares instead of actual lengths).

This C solution calculates the squared value of the diagonal lengths and avoids taking square roots during comparisons, improving performance by only utilizing integer operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of rectangles. This avoids costly sqrt calculations.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: 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.

We can iterate through all the rectangles, calculate the square of their diagonal lengths, and keep track of the maximum diagonal length and the corresponding area.

After the iteration, we return the recorded maximum area.

The time complexity is O(n), where n is the number of rectangles. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Naive Linear Search

Time Complexity: O(n) where n is the number of rectangles.
Space Complexity: O(1) as no additional data structures are used.

Approach 2: Precompute Diagonal Squares

Time Complexity: O(n) where n is the number of rectangles. This avoids costly sqrt calculations.
Space Complexity: O(1).

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Linear Search (with sqrt)O(n)O(1)Simple implementation when readability matters more than micro‑optimizations.
Precompute Diagonal SquaresO(n)O(1)Preferred approach in interviews to avoid floating‑point sqrt operations while comparing diagonals.

Video Solution

Maximum Area of Longest Diagonal Rectangle | Easy | Leetcode 3000 | codestorywithMIK • codestorywithMIK • 3,746 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Area of Longest Diagonal Rectangle easy or hard?
LeetCode classifies this problem as Easy. The solution only requires understanding the Pythagorean formula for diagonals and performing a linear scan with a tie‑breaking rule based on area.
Maximum Area of Longest Diagonal Rectangle Python/Java solution
Both Python and Java implementations follow the same pattern: loop through the rectangles, compute l*l + w*w, compare it with the current maximum diagonal square, and update the stored area if needed. The logic stays O(n) time and O(1) space regardless of language.
How to solve Maximum Area of Longest Diagonal Rectangle in O(n)?
Iterate through the rectangles once and compute the squared diagonal value l*l + w*w for each pair. Maintain the maximum diagonal square encountered so far and the area of that rectangle. Update the stored result whenever a larger diagonal appears or when the diagonal ties but the area is larger.
What is the best approach for Maximum Area of Longest Diagonal Rectangle?
The best approach is a single linear scan that compares the squared diagonals of each rectangle. For every pair (l, w), compute l*l + w*w and track the maximum value. If two rectangles share the same diagonal square, choose the one with the larger area. This runs in O(n) time with O(1) extra space.
Is Maximum Area of Longest Diagonal Rectangle asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving array traversal and mathematical comparison. Variants that involve comparing geometric properties like diagonals or areas appear in interviews at large companies because they test careful iteration and tie‑breaking logic.
What data structure is used in Maximum Area of Longest Diagonal Rectangle?
The problem primarily uses an array of rectangle dimensions. The algorithm performs a sequential scan of this array while maintaining a few variables for the current best diagonal and area. No additional data structures such as hash maps or trees are required.
What is the time complexity of Maximum Area of Longest Diagonal Rectangle?
The optimal solution runs in O(n) time because each rectangle is processed exactly once during a single pass through the array. Only constant additional variables are used to track the best diagonal and area, giving O(1) space complexity.

Ready to solve this problem?

Practice Maximum Area of Longest Diagonal Rectangle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays