LeetCode Entry

70. Climbing Stairs

18.01.2024 easy 2024 kotlin rust

Ways to climb n stairs by 1 or 2 steps.

70. Climbing Stairs easy blog post substack youtube image.png image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/476

Problem TLDR

Ways to climb n stairs by 1 or 2 steps.

Intuition

Start with brute force DFS search: either go one or two steps and cache the result in a HashMap<Int, Int>. Then convert solution to iterative version, as only two previous values matter.

Approach

  • no need to check if n < 4
  • save some lines of code with also

Complexity

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

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

Code


  fun climbStairs(n: Int): Int {
    var p = 0
    var c = 1
    for (i in 1..n) c += p.also { p = c }
    return c
  }



    pub fn climb_stairs(n: i32) -> i32 {
      (0..n).fold((0, 1), |(p, c), _| (c, p + c)).1
    }