3047. Find the Largest Area of Square Inside Two Rectangles

EasyView on LeetCode

Array Math Sorting enumeration

Time: O(n²)

Space: O(1)

Intuition

Find maximum and minimum sum of n+1 elements from two arrays. Pick largest n+1 from combined, smallest n+1.

Algorithm

1Merge and sort. Max sum = sum of top n+1 values ensuring at least one from each array.
2Min sum = sum of bottom n+1 values with same constraint.

Common Pitfalls

•Must include at least one element from each array. Greedy with constraint handling.

3047.cs

// Approach: For each pair of rectangles find overlapping square side = min(x-overlap, y-overlap).
// Time: O(n²) Space: O(1)

public class Solution
{
    public long LargestSquareArea(int[][] bottomLeft, int[][] topRight)
    {
        int minSide = 0;

        for (int i = 0; i < bottomLeft.Length; ++i)
            for (int j = i + 1; j < bottomLeft.Length; ++j)
            {
                int ax1 = bottomLeft[i][0];
                int ay1 = bottomLeft[i][1];
                int ax2 = topRight[i][0];
                int ay2 = topRight[i][1];
                int bx1 = bottomLeft[j][0];
                int by1 = bottomLeft[j][1];
                int bx2 = topRight[j][0];
                int by2 = topRight[j][1];
                int overlapX = Math.Min(ax2, bx2) - Math.Max(ax1, bx1);
                int overlapY = Math.Min(ay2, by2) - Math.Max(ay1, by1);
                minSide = Math.Max(minSide, Math.Min(overlapX, overlapY));
            }

        return (long)minSide * minSide;
    }
}

Was this solution helpful?