LeetCode Entry

1424. Diagonal Traverse II

22.11.2023 medium 2023 kotlin

Diagonal 2D matrix order with prunes

1424. Diagonal Traverse II medium blog post substack image.png

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]} }
  }