3000. Maximum Area of Longest Diagonal Rectangle
Problem Description
The given problem requires us to find the area of a rectangle with the longest diagonal among all rectangles in the provided 2D integer array dimensions
. Each element of this array is itself an array of two elements; the first element represents the length and the second represents the width of a rectangle. If multiple rectangles have diagonals of the same maximum length, we need to find the area of the rectangle that has the maximum area among them.
Intuition
The primary step is to understand that the diagonal of a rectangle can be calculated using the Pythagorean theorem, where the diagonal is the hypotenuse of the right-angled triangle formed by the length and width of the rectangle. To find the longest diagonal, we will square the lengths and widths of the rectangles to avoid working with floating-point numbers that arise from square roots, which simplifies comparisons.
The solution iterates over each rectangle, calculating the square of its diagonal (l**2 + w**2
). We also track the maximum diagonal length found so far (mx
) and the area of the corresponding rectangle (ans
). If a rectangle's diagonal squared is greater than the current maximum, we update both mx
and ans
. If it's equal to the current maximum, we only update ans
if the rectangle's area is larger than the current largest area.
This approach allows us to find the area of the rectangle with the longest diagonal in a single pass through the dimensions
array.
Solution Approach
The implementation of the solution adopts a straightforward approach consistent with the intuition previously described:
-
We initialize two variables,
ans
andmx
, both set to0
.ans
will hold the maximum area found, andmx
will hold the square of the longest diagonal found so far. -
We then loop through each rectangle's dimensions in the
dimensions
list. For each rectangle, we calculatet
, the square of the length of the diagonal, using the formulal**2 + w**2
wherel
is the length andw
is the width of the rectangle. This step is equivalent to applying the Pythagorean theorem to find the diagonal length without taking the square root. -
Within the loop, we perform a check to see if the calculated
t
is greater than our current maximummx
. If it is, we have found a new rectangle with a longer diagonal, so we updatemx
to this new maximum, and we updateans
to the area of the current rectangle, which isl * w
. -
If
t
is equal to the currentmx
, it means we have found another rectangle with a diagonal equal to the longest one seen so far. Since the problem requires us to return the area of the rectangle with the maximum area in such cases, we updateans
with the larger of its current value or the current rectangle's area. -
After the loop has finished executing,
ans
contains the correct maximum area, which we return.
This approach ensures that the algorithm only passes through the array of rectangles once, making it efficient. The algorithm's time complexity is O(n), where n is the number of rectangles given.
In summary, this solution uses simple iteration and comparison, with no need for complex data structures or additional memory beyond the two tracking variables, making it a straightforward but effective approach to solve the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example with the dimensions
array containing the following dimensions of rectangles: [[3, 4], [5, 12], [8, 15]]
.
-
We start by initializing
ans = 0
(to keep track of the area with the maximum diagonal) andmx = 0
(to keep track of the square of the longest diagonal). -
Let's begin the loop:
- For the first rectangle
[3, 4]
, computet = 3**2 + 4**2 = 9 + 16 = 25
. - Compare
t
(25) withmx
(0). Since 25 is greater than 0, updatemx = 25
andans = 3 * 4 = 12
.
- For the first rectangle
-
Proceed to the second rectangle
[5, 12]
:- Compute
t = 5**2 + 12**2 = 25 + 144 = 169
. - Compare
t
(169) withmx
(25). Since 169 is greater, updatemx = 169
andans = 5 * 12 = 60
.
- Compute
-
Move to the third rectangle
[8, 15]
:- Compute
t = 8**2 + 15**2 = 64 + 225 = 289
. - Compare
t
(289) withmx
(169). Since 289 is greater, updatemx = 289
andans = 8 * 15 = 120
.
- Compute
-
The loop has finished. The final values are
mx = 289
andans = 120
. Thus, the maximum area of the rectangle with the longest diagonal is120
.
In this example walkthrough, we see how the algorithm successfully identifies the rectangle with the longest diagonal and, consequently, the largest area among the rectangles with such a diagonal.
Solution Implementation
1from typing import List
2
3class Solution:
4 def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
5 # Initialize the maximum diagonal length and area seen so far
6 max_diagonal_length = 0
7 max_area = 0
8
9 # Loop through each dimension pair in the dimensions list
10 for length, width in dimensions:
11 # Calculate the diagonal length's square based on Pythagorean theorem
12 diagonal_length_sq = length**2 + width**2
13
14 # If a new maximum diagonal length is found
15 if diagonal_length_sq > max_diagonal_length:
16 # Update maximum diagonal length and area
17 max_diagonal_length = diagonal_length_sq
18 max_area = length * width
19 # If current diagonal is equal to the maximum found but the area is larger
20 elif diagonal_length_sq == max_diagonal_length:
21 # Update the area to the larger one
22 max_area = max(max_area, length * width)
23
24 # Return the maximum area corresponding to the largest diagonal length
25 return max_area
26
1class Solution {
2 public int areaOfMaxDiagonal(int[][] dimensions) {
3 int maxArea = 0; // Holds the area of rectangle with largest diagonal so far
4 int maxDiagonalSquare = 0; // Square of the largest diagonal seen so far
5
6 // Loop through each dimensions array, where 'dimension' represents [length, width]
7 for (int[] dimension : dimensions) {
8 int length = dimension[0]; // Length of current rectangle
9 int width = dimension[1]; // Width of current rectangle
10
11 // Calculate the square of the diagonal for current rectangle
12 int diagonalSquare = length * length + width * width;
13
14 // If a larger diagonal is found, update maxDiagonalSquare and maxArea
15 if (maxDiagonalSquare < diagonalSquare) {
16 maxDiagonalSquare = diagonalSquare;
17 maxArea = length * width; // Update area to the area of the current rectangle
18 } else if (maxDiagonalSquare == diagonalSquare) {
19 // If the same diagonal is found, update maxArea if current area is larger
20 maxArea = Math.max(maxArea, length * width);
21 }
22 }
23
24 // Return the area of the rectangle with the largest diagonal encountered
25 return maxArea;
26 }
27}
28
1class Solution {
2public:
3 // Function to calculate the area of the rectangle with the maximum diagonal length
4 int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
5 int maxArea = 0; // Variable to store the maximum area found so far
6 int maxDiagonalSq = 0; // Variable to store the square of the maximum diagonal length
7
8 // Loop through the list of dimensions
9 for (auto& dimension : dimensions) {
10 int length = dimension[0]; // Store the length of the current rectangle
11 int width = dimension[1]; // Store the width of the current rectangle
12 int diagonalSq = length * length + width * width; // Calculate the square of the diagonal length
13
14 // If the current diagonal is greater than the maximum found so far,
15 // update the maximum diagonal and the maximum area accordingly
16 if (maxDiagonalSq < diagonalSq) {
17 maxDiagonalSq = diagonalSq;
18 maxArea = length * width;
19 // If the current diagonal equals the maximum diagonal found so far,
20 // update the maximum area if the current area is greater
21 } else if (maxDiagonalSq == diagonalSq) {
22 maxArea = max(maxArea, length * width);
23 }
24 }
25
26 // Return the maximum area found
27 return maxArea;
28 }
29};
30
1function areaOfLargestDiagonal(dimensions: number[][]): number {
2 let maxArea = 0; // Initialize maxArea to store the largest area found
3 let maxDiagonalSquared = 0; // Initialize maxDiagonalSquared to store the square of the longest diagonal found
4
5 // Iterate through each dimension pair in the dimensions array
6 for (const [length, width] of dimensions) {
7 const diagonalSquared = length * length + width * width; // Calculate the square of the diagonal for current dimensions
8
9 // Compare the squared diagonal length with the maximum found so far
10 if (maxDiagonalSquared < diagonalSquared) {
11 maxDiagonalSquared = diagonalSquared; // Update maxDiagonalSquared
12 maxArea = length * width; // Update maxArea with the area of the current dimensions
13 } else if (maxDiagonalSquared === diagonalSquared) {
14 maxArea = Math.max(maxArea, length * width); // If diagonals are equal, choose the larger area
15 }
16 }
17
18 // Return the area of the rectangle with the longest diagonal
19 return maxArea;
20}
21
Time and Space Complexity
Time Complexity
The provided function areaOfMaxDiagonal
processes each pair of dimensions in the input list exactly once. In each iteration, the function calculates the square of the length and width (l**2 + w**2
) and compares it to the maximum diagonal length found so far (mx < t
and mx == t
). The calculations and comparisons inside the loop are constant time operations.
Let n
be the number of pairs in the input list dimensions
. Since the loop iterates over all pairs, the time complexity is O(n), where n is the length of the input list.
Space Complexity
The function uses a fixed number of variables (ans
, mx
, t
, l
, w
) that do not depend on the size of the input list. Therefore, the space complexity is O(1), meaning it requires a constant amount of additional space.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!