LeetCode Entry

3027. Find the Number of Ways to Place People II

03.09.2025 hard 2025 kotlin

Left-top, bottom-right pairs with empty rectangles

3027. Find the Number of Ways to Place People II hard blog post substack youtube

1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1101

Problem TLDR

Left-top, bottom-right pairs with empty rectangles #medium #geometry

Intuition

Sort by x then rotate CCW around each point.

Approach

  • attention to the numbers range -10^9..10^9

Complexity

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

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

Code


// 692ms
    fun numberOfPairs(p: Array<IntArray>): Int {
        p.sortWith(compareBy({it[0]},{-it[1]}))
        return p.indices.sumOf { i -> var m = Int.MIN_VALUE
            p.drop(i+1).count { (_,y) -> y <= p[i][1] && y > m.also{m=max(m,y)}}
        }
    }