Maximum Area of Longest Diagonal Rectangle

Problem

Qn - Maximum Area of Longest Diagonal Rectangle

Approach

Approach here is pretty trivial, though it was pretty irritating trying to code it out nicely. We first have to find the longest diagonal, and some elements might have the same diagonal length. If they do we need to find the one with the largest area.

Realised that we don’t actually need to store the indexes of all the elements with the longest diagonal length. We could just keep a counter of the longest diagonal length and largest area. Once we see an element that has a longer diagonal length, we can just replace the largest area with the area of that element. And if we see something that is equal in diagonal length, then we can just get the maximum area of the 2.

Complexity

• Time: O(n)
• Space: O(1)

Code

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        largest, longest = 0, 0
        for l,w in dimensions:
            diagonal = sqrt(l*l+w*w)
            if diagonal > longest: 
                longest = diagonal
                largest = l*w
            elif diagonal == longest: largest = max(largest, l*w)
 
        return largest

The O(2n) runtime and O(n) solution

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        longest, largest = 0, 0
        indexes = []
        for i,dimension in enumerate(dimensions):
            l,w = dimension
            val = sqrt(l*l+w*w)
            if val > longest: indexes = [i]
            elif val == longest: indexes.append(i)
            else: continue
            longest = val
        for i in indexes:
            l,w = dimensions[i]
            largest = max(largest, l*w)
        return largest