LeetCode Entry

119. Pascal's Triangle II

16.10.2023 easy 2023 kotlin

Pascal's Triangle

119. Pascal’s Triangle II easy blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/372

Problem TLDR

Pascal’s Triangle

Intuition

One way is to generate sequence:

    fun getRow(rowIndex: Int): List<Int> =
      generateSequence(listOf(1)) {
        listOf(1) + it.windowed(2) { it.sum() } + 1
      }.elementAtOrElse(rowIndex) { listOf() }

Another way is to use fold

Approach

  • notice, we can add a simple 1 to collection by +
  • use sum and windowed

Complexity

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

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

Code


    fun getRow(rowIndex: Int): List<Int> =
      (1..rowIndex).fold(listOf(1)) { r, _ ->
        listOf(1) + r.windowed(2) { it.sum() } + 1
      }