Jobs

Interviews

Discussions

Maximum Area of Longest Diagonal Rectangle

#9 Most AskedEasy

Maximum Area of Longest Diagonal Rectangle #9 Most Asked

Easy

Accenture

2 views

Topics:

Arrays

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 <= 100
dimensions[i].length == 2
1 <= dimensions[i][0], dimensions[i][1] <= 100

Try coding it in LeetCode

Maximum Area of Longest Diagonal Rectangle

#9 Most AskedEasy

Maximum Area of Longest Diagonal Rectangle #9 Most Asked

Easy

Accenture

2 views

Topics:

Arrays

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 <= 100
dimensions[i].length == 2
1 <= dimensions[i][0], dimensions[i][1] <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of rectangles in the `dimensions` array and the values for length and width?
Can the length `li` or width `wi` be zero? If so, how should a rectangle with zero area be handled?
What should be returned if the input `dimensions` array is empty?
If multiple rectangles share the same longest diagonal and also have the same maximum area, does it matter which one's area is returned?
Are the lengths and widths guaranteed to be integers, or could they be floating-point numbers? And will the result (area) fit within a standard integer type?

Brute Force Solution

Approach

To solve this, we can look at every single rectangle provided. For each one, we'll figure out how long its diagonal is, and then we'll keep track of the rectangle with the longest diagonal we've seen so far, along with its area.

Here's how the algorithm would work step-by-step:

Start by looking at the very first rectangle in the list.
Calculate the length of its diagonal. You can think of this as the straight line distance from one corner to the opposite corner.
Let's assume this first rectangle is our best candidate so far. So, we'll remember the length of its diagonal and also its area.
Now, move on to the next rectangle in the list.
Calculate the diagonal length for this new rectangle.
Compare this new diagonal length to the one from our best candidate so far.
If the new rectangle's diagonal is longer, it becomes our new best candidate. We'll forget the old one and remember this new rectangle's diagonal length and its area instead.
If the new rectangle's diagonal is exactly the same length as our current best, we need a tie-breaker. We'll compare their areas and keep the one with the bigger area as our new best candidate.
If the new rectangle's diagonal is shorter, we just ignore it and move on.
Continue this process, examining every single rectangle one by one, and updating our best candidate whenever we find one with a longer diagonal, or one with the same diagonal length but a larger area.
After checking all the rectangles, the area of the final best candidate we're holding onto is the answer.

Code Implementation

def max_area_of_longest_diagonal_rectangle(dimensions):
    longest_diagonal_squared = 0
    max_area_for_longest_diagonal = 0

    # We will look at every single rectangle provided to find our answer.
    for current_rectangle in dimensions:
        length = current_rectangle[0]
        width = current_rectangle[1]

        current_diagonal_squared = length**2 + width**2

        # If the new rectangle's diagonal is longer, it becomes our new best candidate.
        if current_diagonal_squared > longest_diagonal_squared:
            longest_diagonal_squared = current_diagonal_squared
            max_area_for_longest_diagonal = length * width
        
        # If diagonals are equal, the tie-breaker is to keep the one with the larger area.
        elif current_diagonal_squared == longest_diagonal_squared:
            current_area = length * width
            if current_area > max_area_for_longest_diagonal:
                max_area_for_longest_diagonal = current_area

    return max_area_for_longest_diagonal

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the need to examine every rectangle in the input list. If the list contains 'n' rectangles, our approach involves a single pass through this list. For each of the 'n' rectangles, we perform a fixed number of calculations: finding the diagonal and the area, and comparing them. Since these calculations take constant time for each rectangle, the total time taken is directly proportional to the number of rectangles, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm iterates through the list of rectangles while only needing to store a few variables to track the state of the best candidate found so far. Specifically, it uses variables to hold the longest diagonal length and the maximum area corresponding to that diagonal. Since the number of these tracking variables does not change regardless of how many rectangles are in the input list, the auxiliary space used is constant.

Optimal Solution

Approach

The best way to solve this is to simply check each rectangle one by one, keeping track of the best one found so far. We will remember the longest diagonal seen and the largest area associated with that diagonal, updating our memory whenever we find a better rectangle.

Here's how the algorithm would work step-by-step:

First, imagine you have a special place to remember the longest diagonal you've seen and the area of that rectangle. Initially, you haven't seen any, so let's say the longest diagonal is zero and the area is zero.
Now, look at the first rectangle in the list. Figure out the length of its diagonal line using the Pythagorean theorem.
Compare this new rectangle's diagonal to the longest one you've remembered so far.
If the new diagonal is longer, this rectangle is now the best one. Update your memory to hold its diagonal length and its area.
If the new diagonal is exactly the same length as the one you've remembered, you have a tie. To break the tie, compare their areas and keep the one with the bigger area.
If the new diagonal is shorter, simply ignore this rectangle and move on.
Repeat this process for every single rectangle in the list.
After checking all the rectangles, the area you have remembered will be the final answer.

Code Implementation

def max_area_of_longest_diagonal_rectangle(dimensions):
    longest_diagonal_squared = 0
    max_area_for_longest_diagonal = 0

    # Iterate through each rectangle to find the one with the longest diagonal.
    for current_rectangle_dimensions in dimensions:
        length = current_rectangle_dimensions[0]
        width = current_rectangle_dimensions[1]

        current_diagonal_squared = length**2 + width**2

        # If we find a new longest diagonal, this rectangle becomes the best candidate so far.
        if current_diagonal_squared > longest_diagonal_squared:

            longest_diagonal_squared = current_diagonal_squared
            max_area_for_longest_diagonal = length * width

        # In case of a tie in diagonal length, the one with the larger area is preferred.
        elif current_diagonal_squared == longest_diagonal_squared:

            max_area_for_longest_diagonal = max(max_area_for_longest_diagonal, length * width)
    
    # The final stored area corresponds to the rectangle that met the criteria.
    return max_area_for_longest_diagonal

Big(O) Analysis

Time Complexity

O(n) – To determine the time complexity, we analyze the operations performed relative to the number of rectangles, which we'll call n. The provided solution involves a single pass through the list of rectangles. For each of the n rectangles, we perform a constant number of calculations: squaring two numbers, adding them, taking a square root, and multiplying two numbers for the area. Since these calculations take a fixed amount of time regardless of the input size, the total work is directly proportional to the number of rectangles. Therefore, the total operations are approximately c * n, where c is a constant, which simplifies to a time complexity of O(n).

Space Complexity

O(1) – The algorithm's space usage is constant because it only requires a few variables to store the longest diagonal seen so far and its corresponding maximum area. These variables occupy a fixed amount of memory, regardless of the number of rectangles, N, in the input list. The solution iterates through the input without creating any new data structures that scale with the input size.

Edge Cases

Case	How to Handle
Input array `dimensions` is empty	The loop over the dimensions will not execute, and the initial area of 0 will be correctly returned.
Input array `dimensions` contains only one rectangle	The single rectangle will trivially have the longest diagonal and its area will be returned.
Multiple rectangles share the same longest diagonal length	The solution must track the maximum area seen so far for the current longest diagonal and update it if a new rectangle with the same diagonal has a larger area.
Rectangle dimensions contain zeros, e.g., [5, 0] or [0, 0]	The area calculation correctly results in zero, which is a valid area for a degenerate rectangle.
All rectangles in the input have the exact same dimensions	The algorithm will correctly identify the shared diagonal length as the longest and return the shared area.
The rectangle with the overall maximum area does not have the longest diagonal	The solution logic correctly prioritizes the longest diagonal first, ensuring the largest area rectangle is ignored if its diagonal is shorter.
Large values for length and width that could cause integer overflow	Calculating the squared diagonal (ll + ww) and area (l*w) should use 64-bit integers (long in Java/C++, int in Python) to prevent overflow.
The input array is very large, approaching constraint limits (e.g., 100 elements)	A single pass O(N) solution is efficient and will handle large inputs without performance issues.

Input array `dimensions` is empty

How to Handle:

The loop over the dimensions will not execute, and the initial area of 0 will be correctly returned.

Input array `dimensions` contains only one rectangle

How to Handle:

The single rectangle will trivially have the longest diagonal and its area will be returned.

Multiple rectangles share the same longest diagonal length

How to Handle:

The solution must track the maximum area seen so far for the current longest diagonal and update it if a new rectangle with the same diagonal has a larger area.

Rectangle dimensions contain zeros, e.g., [5, 0] or [0, 0]

How to Handle:

The area calculation correctly results in zero, which is a valid area for a degenerate rectangle.

All rectangles in the input have the exact same dimensions

How to Handle:

The algorithm will correctly identify the shared diagonal length as the longest and return the shared area.

The rectangle with the overall maximum area does not have the longest diagonal

How to Handle:

The solution logic correctly prioritizes the longest diagonal first, ensuring the largest area rectangle is ignored if its diagonal is shorter.

Large values for length and width that could cause integer overflow

How to Handle:

Calculating the squared diagonal (l*l + w*w) and area (l*w) should use 64-bit integers (long in Java/C++, int in Python) to prevent overflow.

The input array is very large, approaching constraint limits (e.g., 100 elements)

How to Handle:

A single pass O(N) solution is efficient and will handle large inputs without performance issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of rectangles in the `dimensions` array and the values for length and width?
Can the length `li` or width `wi` be zero? If so, how should a rectangle with zero area be handled?
What should be returned if the input `dimensions` array is empty?
If multiple rectangles share the same longest diagonal and also have the same maximum area, does it matter which one's area is returned?
Are the lengths and widths guaranteed to be integers, or could they be floating-point numbers? And will the result (area) fit within a standard integer type?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very first rectangle in the list.
Calculate the length of its diagonal. You can think of this as the straight line distance from one corner to the opposite corner.
Let's assume this first rectangle is our best candidate so far. So, we'll remember the length of its diagonal and also its area.
Now, move on to the next rectangle in the list.
Calculate the diagonal length for this new rectangle.
Compare this new diagonal length to the one from our best candidate so far.
If the new rectangle's diagonal is longer, it becomes our new best candidate. We'll forget the old one and remember this new rectangle's diagonal length and its area instead.
If the new rectangle's diagonal is exactly the same length as our current best, we need a tie-breaker. We'll compare their areas and keep the one with the bigger area as our new best candidate.
If the new rectangle's diagonal is shorter, we just ignore it and move on.
Continue this process, examining every single rectangle one by one, and updating our best candidate whenever we find one with a longer diagonal, or one with the same diagonal length but a larger area.
After checking all the rectangles, the area of the final best candidate we're holding onto is the answer.

Code Implementation

def max_area_of_longest_diagonal_rectangle(dimensions):
    longest_diagonal_squared = 0
    max_area_for_longest_diagonal = 0

    # We will look at every single rectangle provided to find our answer.
    for current_rectangle in dimensions:
        length = current_rectangle[0]
        width = current_rectangle[1]

        current_diagonal_squared = length**2 + width**2

        # If the new rectangle's diagonal is longer, it becomes our new best candidate.
        if current_diagonal_squared > longest_diagonal_squared:
            longest_diagonal_squared = current_diagonal_squared
            max_area_for_longest_diagonal = length * width
        
        # If diagonals are equal, the tie-breaker is to keep the one with the larger area.
        elif current_diagonal_squared == longest_diagonal_squared:
            current_area = length * width
            if current_area > max_area_for_longest_diagonal:
                max_area_for_longest_diagonal = current_area

    return max_area_for_longest_diagonal

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine you have a special place to remember the longest diagonal you've seen and the area of that rectangle. Initially, you haven't seen any, so let's say the longest diagonal is zero and the area is zero.
Now, look at the first rectangle in the list. Figure out the length of its diagonal line using the Pythagorean theorem.
Compare this new rectangle's diagonal to the longest one you've remembered so far.
If the new diagonal is longer, this rectangle is now the best one. Update your memory to hold its diagonal length and its area.
If the new diagonal is exactly the same length as the one you've remembered, you have a tie. To break the tie, compare their areas and keep the one with the bigger area.
If the new diagonal is shorter, simply ignore this rectangle and move on.
Repeat this process for every single rectangle in the list.
After checking all the rectangles, the area you have remembered will be the final answer.

Code Implementation

def max_area_of_longest_diagonal_rectangle(dimensions):
    longest_diagonal_squared = 0
    max_area_for_longest_diagonal = 0

    # Iterate through each rectangle to find the one with the longest diagonal.
    for current_rectangle_dimensions in dimensions:
        length = current_rectangle_dimensions[0]
        width = current_rectangle_dimensions[1]

        current_diagonal_squared = length**2 + width**2

        # If we find a new longest diagonal, this rectangle becomes the best candidate so far.
        if current_diagonal_squared > longest_diagonal_squared:

            longest_diagonal_squared = current_diagonal_squared
            max_area_for_longest_diagonal = length * width

        # In case of a tie in diagonal length, the one with the larger area is preferred.
        elif current_diagonal_squared == longest_diagonal_squared:

            max_area_for_longest_diagonal = max(max_area_for_longest_diagonal, length * width)
    
    # The final stored area corresponds to the rectangle that met the criteria.
    return max_area_for_longest_diagonal

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array `dimensions` is empty	The loop over the dimensions will not execute, and the initial area of 0 will be correctly returned.
Input array `dimensions` contains only one rectangle	The single rectangle will trivially have the longest diagonal and its area will be returned.
Multiple rectangles share the same longest diagonal length	The solution must track the maximum area seen so far for the current longest diagonal and update it if a new rectangle with the same diagonal has a larger area.
Rectangle dimensions contain zeros, e.g., [5, 0] or [0, 0]	The area calculation correctly results in zero, which is a valid area for a degenerate rectangle.
All rectangles in the input have the exact same dimensions	The algorithm will correctly identify the shared diagonal length as the longest and return the shared area.
The rectangle with the overall maximum area does not have the longest diagonal	The solution logic correctly prioritizes the longest diagonal first, ensuring the largest area rectangle is ignored if its diagonal is shorter.
Large values for length and width that could cause integer overflow	Calculating the squared diagonal (ll + ww) and area (l*w) should use 64-bit integers (long in Java/C++, int in Python) to prevent overflow.
The input array is very large, approaching constraint limits (e.g., 100 elements)	A single pass O(N) solution is efficient and will handle large inputs without performance issues.

Input array `dimensions` is empty

How to Handle:

The loop over the dimensions will not execute, and the initial area of 0 will be correctly returned.

Input array `dimensions` contains only one rectangle

How to Handle:

The single rectangle will trivially have the longest diagonal and its area will be returned.

Multiple rectangles share the same longest diagonal length

How to Handle:

The solution must track the maximum area seen so far for the current longest diagonal and update it if a new rectangle with the same diagonal has a larger area.

Rectangle dimensions contain zeros, e.g., [5, 0] or [0, 0]

How to Handle:

The area calculation correctly results in zero, which is a valid area for a degenerate rectangle.

All rectangles in the input have the exact same dimensions

How to Handle:

The algorithm will correctly identify the shared diagonal length as the longest and return the shared area.

The rectangle with the overall maximum area does not have the longest diagonal

How to Handle:

The solution logic correctly prioritizes the longest diagonal first, ensuring the largest area rectangle is ignored if its diagonal is shorter.

Large values for length and width that could cause integer overflow

How to Handle:

Calculating the squared diagonal (l*l + w*w) and area (l*w) should use 64-bit integers (long in Java/C++, int in Python) to prevent overflow.

The input array is very large, approaching constraint limits (e.g., 100 elements)

How to Handle:

A single pass O(N) solution is efficient and will handle large inputs without performance issues.

0/134 Accenture questions completed

0/134 completed