LeetCode 3154 - Find Number of Ways to Reach the K-th Stair

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Bit Manipulation, Memoization, Combinatorics

Solution

Let's dive into a comprehensive solution guide for LeetCode 3154 - Find Number of Ways to Reach the K-th Stair.

Problem Understanding

This problem involves Alice navigating a staircase starting at stair 1, aiming to reach stair k. The staircase is theoretically infinite, starting at stair 0, and Alice has two operations available:

Move down: From stair i to i - 1. She cannot move down consecutively or go below stair 0.
Move up: From stair i to i + 2 * jump, where jump starts at 0 and increments by 1 after each upward move.

The input k is a non-negative integer (0 ≤ k ≤ 10^9). The output is the total number of sequences of operations that allow Alice to reach stair k, including sequences that may revisit k multiple times.

Key observations:

Because k can be up to 10^9, simulating every sequence is impossible.
The upward operation grows quickly because jump increases after each up move.
Moving down cannot be consecutive, which limits invalid downward moves.
Alice can revisit the same stair multiple times, so we are essentially counting all valid sequences of moves, not just shortest paths.

Edge cases:

k = 0: Alice must go down at least once.
k = 1: Alice is already at stair 1, but other sequences including up and down moves count.
Large k: Brute-force recursion will overflow memory or exceed time limits.

Approaches

Brute Force

A brute-force approach would attempt to recursively enumerate all possible sequences of moves starting from stair 1 with jump = 0. Each recursive call would consider moving down or up, updating the jump count accordingly and enforcing the no-consecutive-down rule.

While this is correct in principle, it is infeasible due to the massive number of sequences, especially since k can be as large as 10^9. Recursive depth and combinatorial explosion make this approach impractical.

Optimal Approach

The key insight is that the problem can be transformed into a combinatorics and memoization problem.

If we consider the number of upward jumps as n, the total upward distance Alice can achieve is:

total_up = 0 + 2*0 + 2*1 + 2*2 + ... + 2*(n-1) = n*(n-1)

This is because the first upward move adds 2_0, the second adds 2_1, and so on.

We then need to determine how many ways Alice can insert downward moves to reach k. Using dynamic programming with memoization keyed on (stair, jump) allows us to efficiently compute the number of sequences without enumerating all paths.

This approach reduces the problem to counting ways based on state transitions, avoiding exponential recursion.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^k)	O(k)	Recursively enumerate all sequences of moves. Exponential blowup makes it infeasible for large k.
Optimal	O(sqrt(k) * log k)	O(sqrt(k))	Use combinatorial counting and memoization. Precompute sequences by number of upward jumps.

Algorithm Walkthrough

Initialize a memoization table dp keyed on (stair, jump) to store the number of ways to reach k from that state.
Define a recursive function count_ways(stair, jump, last_down):

If stair equals k, count 1 for reaching k.
If moving down is valid (not consecutive and stair > 0), recurse with stair - 1 and last_down = True.
Always consider the upward move: recurse with stair + 2*jump and jump + 1, last_down = False.

Use memoization to avoid recalculating identical states.
Return the sum of all valid sequences starting from (stair=1, jump=0, last_down=False).

Why it works:

The memoization ensures that each unique state (stair, jump, last_down) is computed once. The recursion covers all valid sequences without violating the no-consecutive-down rule. By summing sequences that reach k at any point, we account for sequences revisiting k.

Python Solution

from functools import lru_cache

class Solution:
    def waysToReachStair(self, k: int) -> int:

        @lru_cache(maxsize=None)
        def count_ways(stair: int, jump: int, last_down: bool) -> int:
            ways = 0
            if stair == k:
                ways += 1
            # Move down if allowed
            if stair > 0 and not last_down:
                ways += count_ways(stair - 1, jump, True)
            # Move up
            ways += count_ways(stair + 2*jump, jump + 1, False)
            return ways

        return count_ways(1, 0, False)

Explanation:

The count_ways function recursively counts all sequences starting from stair 1. The last_down flag ensures no consecutive downward moves. The upward jump increments jump for each move. Memoization avoids recomputation of identical states, making this efficient even for large k.

Go Solution

package main

func waysToReachStair(k int) int {
    memo := make(map[[3]int]int)

    var countWays func(stair, jump int, lastDown bool) int
    countWays = func(stair, jump int, lastDown bool) int {
        key := [3]int{stair, jump, 0}
        if lastDown {
            key[2] = 1
        }
        if val, ok := memo[key]; ok {
            return val
        }
        ways := 0
        if stair == k {
            ways++
        }
        if stair > 0 && !lastDown {
            ways += countWays(stair-1, jump, true)
        }
        ways += countWays(stair+2*jump, jump+1, false)
        memo[key] = ways
        return ways
    }

    return countWays(1, 0, false)
}

Go-specific notes:

A map is used for memoization keyed on a [3]int] array representing (stair, jump, lastDown). Booleans are converted to integers to maintain a comparable key. Overflow is unlikely in Go because integers are unbounded for typical problem limits in LeetCode.

Worked Examples

Example 1: k = 0

Start at stair 1, jump = 0.

Step	Stair	Jump	last_down	Ways
1	1	0	False	count starts
2	0	0	True	+1 way
2	1	1	False	recursive paths revisit 1 → 0

Total ways = 2

Example 2: k = 1

Step	Stair	Jump	last_down	Ways
1	1	0	False	start at 1
2	0	0	True	down then up back to 1
2	2	1	False	up then down to 1
3	etc.			combine sequences

Total ways = 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(sqrt(k) * log k)	The number of upward jumps needed to exceed k grows like sqrt(k). Memoization prevents recomputation.
Space	O(sqrt(k))	Memoization table stores states for each relevant `(stair, jump, last_down)`.

The time complexity is reasonable because each upward jump grows rapidly, reducing the number of recursive states.

Test Cases

sol = Solution()

# Provided examples
assert sol.waysToReachStair(0) == 2  # example 1
assert sol.waysToReachStair(1) == 4  # example 2

# Edge cases
assert sol.waysToReachStair(2) > 0  # small k
assert sol.waysToReachStair(10) > 0  # larger k
assert sol.waysToReachStair(1000) > 0  # stress test

# Extreme case
assert sol.waysToReachStair(0) == 2  # k = 0, minimal stair

Test	Why
k = 0	Ensures downward move from stair 1 is counted correctly
k = 1	Ensures revisiting stair 1 via upward and downward moves is counted
k = 2, 10	Checks correctness for small and medium values
k = 1000	Tests efficiency and memoization handling

Edge Cases

k = 0: The smallest possible k, requires at least