LeetCode Entry

3047. Find the Largest Area of Square Inside Two Rectangles

17.01.2026 medium 2026 kotlin rust

Max square in intersection

3047. Find the Largest Area of Square Inside Two Rectangles medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1240

Problem TLDR

Max square in intersection #medium

Intuition

Brute-force is accepted. The intersection is max(bottom left) & min(top right)

Approach

• we also can sort and return inner loop early
• or freeze the result S length and binary search if it fits
• or sort and line sweep 2d or with segment tree

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(1)\)

Code

// 350ms
    fun largestSquareArea(a: Array<IntArray>, b: Array<IntArray>) =
        (0..<b.size-1).maxOf { i -> (i+1..<b.size).maxOf { j ->
            (0..1).minOf { min(b[i][it],b[j][it])-max(a[i][it],a[j][it]) }
        }}.let { 1L*it*max(0,it) }

// 77ms
    pub fn largest_square_area(a: Vec<Vec<i32>>, b: Vec<Vec<i32>>) -> i64 {
        a.iter().zip(&b).tuple_combinations().map(|((l1, r1), (l2, r2))|
             (0..2).map(|k| r1[k].min(r2[k]) - l1[k].max(l2[k])).min().unwrap()
        ).max().map_or(0, |x| (x.max(0) as i64).pow(2))
    }