22.11.2023
1424. Diagonal Traverse II medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/413
Problem TLDR
Diagonal 2D matrix order with prunes
Intuition
The naive solution is to adjust the pointers x
and y
. However, that will cost O(max(x)*max(y)) and give TLE.
Let’s just sort indices pairs (x y)
and take them one by one.
Approach
Use some Kotlin’s features:
with
let
indices
compareBy({ one }, { two })
Complexity
Time complexity:
O(nlog(n))Space complexity:
O(n)
Code
fun findDiagonalOrder(nums: List<List<Int>>): IntArray =
with(PriorityQueue<Pair<Int, Int>>(compareBy(
{ it.first + it.second }, { it.first }, { it.second }
))) {
for (y in nums.indices)
for (x in nums[y].indices) add(x to y)
IntArray(size) { poll().let { (x, y) -> nums[y][x]} }
}