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] <= 100Problem 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.
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.
Time Complexity: O(n) where n is the number of rectangles.
Space Complexity: O(1) as no additional data structures are used.
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.
Time Complexity: O(n) where n is the number of rectangles. This avoids costly sqrt calculations.
Space Complexity: O(1).
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).
| 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. This avoids costly sqrt calculations. |
| Mathematics | — |
| 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. |
Maximum Area of Longest Diagonal Rectangle | Easy | Leetcode 3000 | codestorywithMIK • codestorywithMIK • 3,657 views views
Watch 9 more video solutions →Practice Maximum Area of Longest Diagonal Rectangle with our built-in code editor and test cases.
Practice on FleetCode