Maximum Area of Longest Diagonal Rectangle
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's requirements into code. It iterates through each rectangle, calculates the actual length of its diagonal using the Pythagorean theorem (d = sqrt(l^2 + w^2)), and keeps track of the rectangle that satisfies the conditions. It's a straightforward, single-pass solution.
Algorithm
- Initialize
maxDiagonalto-1.0andmaxAreato0. - Iterate through each rectangle
[length, width]in thedimensionsarray. - For each rectangle, calculate its diagonal
d = Math.sqrt(length * length + width * width). - If
dis greater thanmaxDiagonal:- Update
maxDiagonaltod. - Update
maxAreato the current arealength * width.
- Update
- Else if
dis equal tomaxDiagonal:- Update
maxAreatoMath.max(maxArea, length * width).
- Update
- After the loop, return
maxArea.
Walkthrough
We initialize two variables: maxDiagonal to store the longest diagonal found so far (initialized to a very small number like -1.0) and maxArea to store the corresponding area (initialized to 0).
We then loop through each rectangle [length, width] in the input dimensions array.
For each rectangle, we calculate its diagonal d using Math.sqrt(length * length + width * width). We then compare this d with our tracked maxDiagonal.
- If
dis greater thanmaxDiagonal, it means we've found a new rectangle with a longer diagonal. We must updatemaxDiagonaltodand, importantly, updatemaxAreato the area of this new rectangle (length * width). - If
dis exactly equal tomaxDiagonal, we have a tie in diagonal length. The problem states that in case of a tie, we should choose the rectangle with the maximum area. Therefore, we updatemaxAreato be the maximum of its current value and the area of the current rectangle.
After iterating through all the rectangles, the maxArea variable will hold the area of the rectangle with the longest diagonal, correctly handling any ties by area.
class Solution { public int areaOfMaxDiagonal(int[][] dimensions) { double maxDiagonal = -1.0; int maxArea = 0; for (int[] dim : dimensions) { int length = dim[0]; int width = dim[1]; double currentDiagonal = Math.sqrt(length * length + width * width); if (currentDiagonal > maxDiagonal) { maxDiagonal = currentDiagonal; maxArea = length * width; } else if (currentDiagonal == maxDiagonal) { maxArea = Math.max(maxArea, length * width); } } return maxArea; }}Complexity
Time
O(N), where N is the number of rectangles in `dimensions`. We perform a single pass through the array, and each step inside the loop takes constant time.
Space
O(1), as we only use a few variables to store the maximum diagonal and area, regardless of the input size.
Trade-offs
Pros
Simple and easy to understand as it's a direct implementation of the problem statement.
Cons
Uses floating-point arithmetic (
Math.sqrt), which is generally slower than integer arithmetic.Comparing floating-point numbers for exact equality (
==) can be risky due to precision issues, although it is acceptable under the given problem constraints.
This is the most efficient approach. It improves upon the previous method by avoiding floating-point calculations entirely. The key insight is that comparing the lengths of two diagonals is equivalent to comparing the squares of their lengths. If d1 > d2, then it must be true that d1^2 > d2^2. This allows us to work exclusively with integers, which is faster and avoids any potential floating-point precision issues.
Algorithm
- Initialize
maxDiagonalSqto-1andmaxAreato0. - Iterate through each rectangle
[length, width]in thedimensionsarray. - For each rectangle, calculate the square of its diagonal
currentDiagonalSq = length * length + width * width. - If
currentDiagonalSqis greater thanmaxDiagonalSq:- Update
maxDiagonalSqtocurrentDiagonalSq. - Update
maxAreato the current arealength * width.
- Update
- Else if
currentDiagonalSqis equal tomaxDiagonalSq:- Update
maxAreatoMath.max(maxArea, length * width).
- Update
- After the loop, return
maxArea.
Walkthrough
Instead of tracking the maximum diagonal itself, we track the square of the maximum diagonal. This is a common optimization to avoid computationally expensive square root operations and floating-point inaccuracies.
We initialize maxDiagonalSq to -1 and maxArea to 0.
We iterate through each rectangle [length, width]. For each one, we calculate the square of its diagonal: currentDiagonalSq = length * length + width * width. This calculation only involves integer multiplication and addition.
We then compare currentDiagonalSq with maxDiagonalSq:
- If
currentDiagonalSq > maxDiagonalSq, we have found a new longest diagonal. We updatemaxDiagonalSqtocurrentDiagonalSqand setmaxAreato the current rectangle's area (length * width). - If
currentDiagonalSq == maxDiagonalSq, we have a tie. We apply the tie-breaking rule by updatingmaxAreato be the maximum of its current value and the current area.
After the loop finishes, maxArea will correctly hold the desired result. This method is superior as it is faster and more robust by relying solely on integer arithmetic.
class Solution { public int areaOfMaxDiagonal(int[][] dimensions) { int maxDiagonalSq = -1; int maxArea = 0; for (int[] dim : dimensions) { int length = dim[0]; int width = dim[1]; int currentDiagonalSq = length * length + width * width; if (currentDiagonalSq > maxDiagonalSq) { maxDiagonalSq = currentDiagonalSq; maxArea = length * width; } else if (currentDiagonalSq == maxDiagonalSq) { maxArea = Math.max(maxArea, length * width); } } return maxArea; }}Complexity
Time
O(N), where N is the number of rectangles. The algorithm performs a single pass over the input array with constant time operations inside the loop.
Space
O(1). We use a constant amount of extra space for our tracking variables.
Trade-offs
Pros
Most efficient solution due to the use of integer-only arithmetic.
Avoids
Math.sqrt()and floating-point numbers, making it faster and eliminating potential precision errors.
Cons
The logic is slightly less direct than the problem statement because it compares squared values instead of the actual diagonal lengths.
Solutions
Solution
class Solution {public int areaOfMaxDiagonal(int[][] dimensions) { int ans = 0, mx = 0; for (var d : dimensions) { int l = d[0], w = d[1]; int 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; }}class Solution {public: int areaOfMaxDiagonal(vector<vector<int>> &dimensions) { int ans = 0, mx = 0; for (auto &d : dimensions) { int l = d[0], w = d[1]; int t = l * l + w * w; if (mx < t) { mx = t; ans = l * w; } else if (mx == t) { ans = max(ans, l * w); } } return ans; }};class Solution: def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int: ans = mx = 0 for l, w in dimensions: t = l ** 2 + w ** 2 if mx < t: mx = t ans = l * w elif mx == t: ans = max(ans, l * w) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.