Maximum Area of Longest Diagonal Rectangle solution and explanation
Google
9 more videos on this problem
Maximum Area of Longest Diagonal Rectangle | Easy | Leetcode 3000 | codestorywithMIKcodestorywithMIK · 7:02 · 3K views
Leetcode | 3000. Maximum Area of Longest Diagonal Rectangle | Easy | Java SolutionDeveloper Docs · 5:26 · 523 views
3000. Maximum Area of Longest Diagonal Rectangle | Leetcode Daily - PythonLeetcode Daily · 4:58 · 441 views
Daily Leetcode #1974: Aug 26, 2025 - 3000. Maximum Area of Longest Diagonal RectangleProgramming Live with Larry · 3:29 · 341 views
3000. Maximum Area of Longest Diagonal Rectangle (Leetcode Easy)Programming Live with Larry · 3:47 · 252 views
Leetcode 3000. Maximum Area of Longest Diagonal Rectangle | Geometry & Math | Python SolutionStatLearn Tech · 4:44 · 149 views
Maximum Area of Longest Diagonal Rectangle | LeetCode 3000 | Array | Math | AtlassianCode Harmony · 11:04 · 124 views
Maximum Area of Longest Diagonal Rectangle | LeetCode 3000 - Pythonimpoldev · 5:14 · 102 views
Maximum Area of Longest Diagonal Rectangle | Leetcode 3000 (Easy) | Codeminttcodemintt · 6:28 · 66 views
Maximum Area of Longest Diagonal Rectangle | LeetCode 3000 | Simple Iteration ExplainedSanyam IIT Guwahati · 7:31 · 66 views
The problem
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 <= 100dimensions[i].length == 21 <= 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.
import math
def max_area_longest_diagonal(dimensions):
max_diagonal_length = 0.0
max_area = 0
for length, width in dimensions:
diagonal_length = math.sqrt(length ** 2 + width ** 2)
area = length * width
if diagonal_length > max_diagonal_length or (diagonal_length == max_diagonal_length and area > max_area):
max_diagonal_length = diagonal_length
max_area = area
return max_area
# Example usage:
dimensions = [[9, 3], [8, 6]]
print(max_area_longest_diagonal(dimensions))import java.util.*;
public class MaxAreaDiagonal {
public static int maxAreaLongestDiagonal(int[][] dimensions) {
double maxDiagonalLength = 0.0;
int maxArea = 0;
for (int[] dim : dimensions) {
int length = dim[0];
int width = dim[1];
double diagonalLength = Math.sqrt(length * length + width * width);
int area = length * width;
if (diagonalLength > maxDiagonalLength || (diagonalLength == maxDiagonalLength && area > maxArea)) {
maxDiagonalLength = diagonalLength;
maxArea = area;
}
}
return maxArea;
}
public static void main(String[] args) {
int[][] dimensions = {{9, 3}, {8, 6}};
System.out.println(maxAreaLongestDiagonal(dimensions));
}
}#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int maxAreaLongestDiagonal(const vector<vector<int>>& dimensions) {
double maxDiagonalLength = 0.0;
int maxArea = 0;
for (const auto& dim : dimensions) {
int length = dim[0];
int width = dim[1];
double diagonalLength = sqrt(length * length + width * width);
int area = length * width;
if (diagonalLength > maxDiagonalLength || (diagonalLength == maxDiagonalLength && area > maxArea)) {
maxDiagonalLength = diagonalLength;
maxArea = area;
}
}
return maxArea;
}
int main() {
vector<vector<int>> dimensions = {{9, 3}, {8, 6}};
cout << maxAreaLongestDiagonal(dimensions) << endl;
return 0;
}function maxAreaLongestDiagonal(dimensions) {
let maxDiagonalLength = 0.0;
let maxArea = 0;
dimensions.forEach(([length, width]) => {
const diagonalLength = Math.sqrt(length * length + width * width);
const area = length * width;
if (diagonalLength > maxDiagonalLength || (diagonalLength === maxDiagonalLength && area > maxArea)) {
maxDiagonalLength = diagonalLength;
maxArea = area;
}
});
return maxArea;
}
// Example usage:
const dimensions = [[9, 3], [8, 6]];
console.log(maxAreaLongestDiagonal(dimensions));#include <stdio.h>
#include <math.h>
int maxAreaLongestDiagonal(int dimensions[][2], int size) {
double maxDiagonalLength = 0.0;
int maxArea = 0;
for (int i = 0; i < size; i++) {
int length = dimensions[i][0];
int width = dimensions[i][1];
double diagonalLength = sqrt(length * length + width * width);
int area = length * width;
if (diagonalLength > maxDiagonalLength || (diagonalLength == maxDiagonalLength && area > maxArea)) {
maxDiagonalLength = diagonalLength;
maxArea = area;
}
}
return maxArea;
}
int main() {
int dimensions[][2] = {{9, 3}, {8, 6}};
int size = sizeof(dimensions) / sizeof(dimensions[0]);
printf("%d\n", maxAreaLongestDiagonal(dimensions, size));
return 0;
}using System;
public class MaxAreaDiagonal {
public static int MaxAreaLongestDiagonal(int[][] dimensions) {
double maxDiagonalLength = 0.0;
int maxArea = 0;
foreach (var dim in dimensions) {
int length = dim[0];
int width = dim[1];
double diagonalLength = Math.Sqrt(length * length + width * width);
int area = length * width;
if (diagonalLength > maxDiagonalLength || (diagonalLength == maxDiagonalLength && area > maxArea)) {
maxDiagonalLength = diagonalLength;
maxArea = area;
}
}
return maxArea;
}
public static void Main() {
int[][] dimensions = new int[][] { new int[] { 9, 3 }, new int[] { 8, 6 } };
Console.WriteLine(MaxAreaLongestDiagonal(dimensions));
}
}This Python code employs the math module for square root calculation and iterates through the list of rectangle dimensions to calculate diagonal lengths and compare areas.
Time Complexity: O(n) where n is the number of rectangles.
Space Complexity: O(1).
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).
def max_area_longest_diagonal(dimensions):
max_diagonal_square = 0
max_area = 0
for length, width in dimensions:
diagonal_square = length ** 2 + width ** 2
area = length * width
if diagonal_square > max_diagonal_square or (diagonal_square == max_diagonal_square and area > max_area):
max_diagonal_square = diagonal_square
max_area = area
return max_area
# Example usage:
dimensions = [[9, 3], [8, 6]]
print(max_area_longest_diagonal(dimensions))import java.util.*;
public class MaxAreaDiagonal {
public static int maxAreaLongestDiagonal(int[][] dimensions) {
int maxDiagonalSquare = 0;
int maxArea = 0;
for (int[] dim : dimensions) {
int length = dim[0];
int width = dim[1];
int diagonalSquare = length * length + width * width;
int area = length * width;
if (diagonalSquare > maxDiagonalSquare || (diagonalSquare == maxDiagonalSquare && area > maxArea)) {
maxDiagonalSquare = diagonalSquare;
maxArea = area;
}
}
return maxArea;
}
public static void main(String[] args) {
int[][] dimensions = {{9, 3}, {8, 6}};
System.out.println(maxAreaLongestDiagonal(dimensions));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxAreaLongestDiagonal(const vector<vector<int>>& dimensions) {
int maxDiagonalSquare = 0;
int maxArea = 0;
for (const auto& dim : dimensions) {
int length = dim[0];
int width = dim[1];
int diagonalSquare = length * length + width * width;
int area = length * width;
if (diagonalSquare > maxDiagonalSquare || (diagonalSquare == maxDiagonalSquare && area > maxArea)) {
maxDiagonalSquare = diagonalSquare;
maxArea = area;
}
}
return maxArea;
}
int main() {
vector<vector<int>> dimensions = {{9, 3}, {8, 6}};
cout << maxAreaLongestDiagonal(dimensions) << endl;
return 0;
}function maxAreaLongestDiagonal(dimensions) {
let maxDiagonalSquare = 0;
let maxArea = 0;
dimensions.forEach(([length, width]) => {
const diagonalSquare = length * length + width * width;
const area = length * width;
if (diagonalSquare > maxDiagonalSquare || (diagonalSquare === maxDiagonalSquare && area > maxArea)) {
maxDiagonalSquare = diagonalSquare;
maxArea = area;
}
});
return maxArea;
}
// Example usage:
const dimensions = [[9, 3], [8, 6]];
console.log(maxAreaLongestDiagonal(dimensions));#include <stdio.h>
int maxAreaLongestDiagonal(int dimensions[][2], int size) {
int maxDiagonalSquare = 0;
int maxArea = 0;
for (int i = 0; i < size; i++) {
int length = dimensions[i][0];
int width = dimensions[i][1];
int diagonalSquare = length * length + width * width;
int area = length * width;
if (diagonalSquare > maxDiagonalSquare || (diagonalSquare == maxDiagonalSquare && area > maxArea)) {
maxDiagonalSquare = diagonalSquare;
maxArea = area;
}
}
return maxArea;
}
int main() {
int dimensions[][2] = {{9, 3}, {8, 6}};
int size = sizeof(dimensions) / sizeof(dimensions[0]);
printf("%d\n", maxAreaLongestDiagonal(dimensions, size));
return 0;
}using System;
public class MaxAreaDiagonal {
public static int MaxAreaLongestDiagonal(int[][] dimensions) {
int maxDiagonalSquare = 0;
int maxArea = 0;
foreach (var dim in dimensions) {
int length = dim[0];
int width = dim[1];
int diagonalSquare = length * length + width * width;
int area = length * width;
if (diagonalSquare > maxDiagonalSquare || (diagonalSquare == maxDiagonalSquare && area > maxArea)) {
maxDiagonalSquare = diagonalSquare;
maxArea = area;
}
}
return maxArea;
}
public static void Main() {
int[][] dimensions = new int[][] { new int[] { 9, 3 }, new int[] { 8, 6 } };
Console.WriteLine(MaxAreaLongestDiagonal(dimensions));
}
}This Python version precomputes diagonal squares instead of computing square roots, enhancing performance by keeping operations in integer space, thus avoiding floating-point arithmetic.
Time Complexity: O(n) where n is the number of rectangles.
Space Complexity: O(1).
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).
function areaOfMaxDiagonal(dimensions: number[][]): number {
let [ans, mx] = [0, 0];
for (const [l, w] of dimensions) {
const t = l * l + w * w;
if (mx < t) {
mx = t;
ans = l * w;
} else if (mx === t) {
ans = Math.max(ans, l * w);
}
}
return ans;
}func areaOfMaxDiagonal(dimensions [][]int) (ans int) {
mx := 0
for _, d := range dimensions {
l, w := d[0], d[1]
t := l*l + w*w
if mx < t {
mx = t
ans = l * w
} else if mx == t {
ans = max(ans, l*w)
}
}
return
}impl Solution {
pub fn area_of_max_diagonal(dimensions: Vec<Vec<i32>>) -> i32 {
let mut ans = 0;
let mut mx = 0;
for d in dimensions {
let l = d[0];
let w = d[1];
let t = l * l + w * w;
if mx < t {
mx = t;
ans = l * w;
} else if mx == t {
ans = ans.max(l * w);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Naive Linear Search | Time Complexity: O(n) where n is the number of rectangles. |
| Approach 2: Precompute Diagonal Squares | Time Complexity: O(n) where n is the number of rectangles. |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Linear Search (with sqrt) | O(n) | O(1) | Simple implementation when readability matters more than micro‑optimizations. |
| Precompute Diagonal Squares | O(n) | O(1) | Preferred approach in interviews to avoid floating‑point sqrt operations while comparing diagonals. |
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.