Watch 10 video solutions for Maximum Area of Longest Diagonal Rectangle, a easy level problem involving Array. This walkthrough by codestorywithMIK has 3,657 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |