Tejav
#1269

Number of Ways to Stay in the Same Place After Some Steps

Hard
Dynamic ProgrammingDynamic ProgrammingRecursion
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

The optimal solution uses dynamic programming to store the number of ways to reach each position at each step, reducing redundant calculations. This approach efficiently builds on previously computed results.

⚙️

Algorithm

3 steps
  1. 1Step 1: Create a DP array where dp[i] represents the number of ways to reach index 0 after i steps.
  2. 2Step 2: Initialize dp[0] = 1 (1 way to stay at index 0 with 0 steps).
  3. 3Step 3: For each step from 1 to steps, update the dp array based on the previous values (considering left, right, and stay moves).
solution.py16 lines
1# Full working Python code
2MOD = 10**9 + 7
3
4def countWays(steps, arrLen):
5    dp = [0] * (steps + 1)
6    dp[0] = 1
7    for step in range(1, steps + 1):
8        new_dp = [0] * (steps + 1)
9        for pos in range(min(arrLen, step + 1)):
10            new_dp[pos] = dp[pos] % MOD
11            if pos > 0:
12                new_dp[pos] = (new_dp[pos] + dp[pos - 1]) % MOD
13            if pos < steps:
14                new_dp[pos] = (new_dp[pos] + dp[pos + 1]) % MOD
15        dp = new_dp
16    return dp[0]
ℹ

Complexity note: The time complexity is O(n) because we iterate through the number of steps and update the DP array in linear time. The space complexity is O(n) due to the storage of the DP array.

  • 1Understanding the problem as a pathfinding problem helps in visualizing the moves.
  • 2Dynamic programming is effective for problems involving counting distinct ways to achieve a state.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.