LeetCode Entry
3025. Find the Number of Ways to Place People I
Left-top, bottom-right pairs with empty rectangles
3025. Find the Number of Ways to Place People I medium blog post substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1100
Problem TLDR
Left-top, bottom-right pairs with empty rectangles #medium
Intuition
Brute-force is accepted for n=50.
Another intuition: sort by x then rotate CCW around each point.
Approach
- should we learn quad trees?
Complexity
-
Time complexity: \(O(n^3)\)
-
Space complexity: \(O(1)\)
Code
// 55ms
fun numberOfPairs(p: Array<IntArray>): Int {
var res = 0
for (i in p.indices) for (j in p.indices)
if (i != j && p[i][0] <= p[j][0] && p[i][1] >= p[j][1] &&
p.indices.none { k -> k != i && k != j &&
p[k][0] in p[i][0]..p[j][0] && p[k][1] in p[j][1]..p[i][1] }) ++res
return res
}
// 43ms
fun numberOfPairs(p: Array<IntArray>): Int {
p.sortBy { it[0]*1000-it[1] }
return p.indices.sumOf { i ->
var y = -1
p.drop(i+1).count { (_,d) -> d <= p[i][1] && d > y.also{y=max(y,d)}}
}
}