This page did not load. You can still read it on the original site — the toolbar below keeps your place in the directory.

Leetcode: 70. Climbing Stairs Naive Solution Primary idea: Recursion to calculate fifibonacci sequence Time Complexity: O(2^n), because at…

Leetcode: 70. Climbing Stairs

Naive Solution

Primary idea: Recursion to calculate fifibonacci sequence
Time Complexity: O(2^n), because at each stair there are two choices and there are total of n stairs.
Space Complexity: O(n), because of recursive stack space.

func climbStairs(_ n: Int) -> Int {
    fib(n + 1)
}
func fib(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}
climbStairs(1) // 2
climbStairs(2) // 2
climbStairs(3) // 3
climbStairs(4) // 5

Optimised Solution

Primary idea: Dynamic Programming (Memoization): dp[i] = dp[i - 1] + dp[i - 2]
Time Complexity: O(n), where n is the number of steps.
Space Complexity: O(1), constant space

func climbStairs(_ n: Int) -> Int {
    // Base case: if n is 0 or 1, return 1
    if n <= 1 { return 1 }
    // Create an array to store the number of ways to reach each step
    var dp = [Int](repeating: 0, count: n + 1)
    dp[0] = 1
    dp[1] = 1
    // Fill the dp array
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n] // The number of ways to reach step n
}
climbStairs(1) // 2
climbStairs(2) // 2
climbStairs(3) // 3
climbStairs(4) // 5

iOS Interview - Leetcode 70. Climbing Stairs

Naive Solution

Optimised Solution

Further Reading

Comments