LeetCode Entry

62. Unique Paths

3.09.2023 medium 2023 kotlin

Unique paths count, moving right-down from top-left to bottom-right

62. Unique Paths medium blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/328

Problem TLDR

Unique paths count, moving right-down from top-left to bottom-right

Intuition

On each cell, the number of paths is a sum of direct up number and direct left number.

Approach

Use single row array, as only previous up row is relevant

Complexity

  • Time complexity: \(O(nm)\)

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

Code


    fun uniquePaths(m: Int, n: Int): Int {
      val row = IntArray(n) { 1 }
      for (y in 1..<m)
        for (x in 1..<n)
          row[x] += row[x - 1]
      return row.last()
    }