Number of Ways to Stay in the Same Place After Some Steps
HardPrompt
You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).
Given two integers steps and arrLen, return the number of ways such that your pointer is still at index 0 after exactly steps steps. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, StayExample 2:
Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, StayExample 3:
Input: steps = 4, arrLen = 2
Output: 8
Constraints:
1 <= steps <= 5001 <= arrLen <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses recursion with memoization, a top-down dynamic programming technique. We define a function that calculates the number of ways to reach a certain position with a certain number of steps remaining. The problem has overlapping subproblems (e.g., the ways to reach position p in s steps is needed by multiple future states), which makes it a perfect candidate for memoization to store and reuse results of subproblems.
Algorithm
- Define a recursive function, let's call it
solve(stepsLeft, pos), which returns the number of ways to get toposwithstepsLeftremaining. - The base cases for the recursion are:
- If
posis out of bounds (< 0or>= arrLen), there are 0 ways. Return 0. - If
stepsLeftis 0, there is 1 way ifposis 0, and 0 ways otherwise. - An important optimization: if
pos > stepsLeft, it's impossible to return to index 0, so we can return 0.
- If
- To avoid recomputing the same state
(stepsLeft, pos)multiple times, use a 2D arraymemofor memoization. Before computing, check if the result is already inmemo. - The recursive step calculates the result by summing the ways from the three possible previous moves:
solve(stepsLeft - 1, pos)(stay),solve(stepsLeft - 1, pos - 1)(move left), andsolve(stepsLeft - 1, pos + 1)(move right). - The maximum position that needs to be considered is limited by
steps. AnyarrLengreater thansteps + 1behaves the same asarrLen = steps + 1. So, we can cap the array length atsteps + 1.
Walkthrough
The core idea is to define a function solve(stepsLeft, pos) that computes the number of ways to end up at pos given stepsLeft moves. The state is defined by (stepsLeft, pos). The transitions are based on the three allowed moves: stay, move left, or move right. We call the function recursively for stepsLeft - 1 and the corresponding new positions.
To make this efficient, we store the results for each state (stepsLeft, pos) in a 2D memoization table. This prevents redundant calculations for the same state, drastically reducing the time complexity from exponential to polynomial.
The maximum possible index we can reach is limited by the number of steps. For instance, with s steps, we can't reach an index greater than s. Therefore, we can effectively cap the array length to min(arrLen, steps + 1) for our state space.
class Solution { int MOD = 1_000_000_007; int maxPos; Integer[][] memo; public int numWays(int steps, int arrLen) { this.maxPos = Math.min(arrLen, steps + 1); this.memo = new Integer[steps + 1][this.maxPos]; return solve(steps, 0); } private int solve(int stepsLeft, int pos) { if (pos < 0 || pos >= maxPos) { return 0; } if (stepsLeft == 0) { return pos == 0 ? 1 : 0; } // Optimization: if we are further from 0 than steps left, we can't return. if (pos > stepsLeft) { return 0; } if (memo[stepsLeft][pos] != null) { return memo[stepsLeft][pos]; } long res = 0; // Stay res = (res + solve(stepsLeft - 1, pos)) % MOD; // Move Left res = (res + solve(stepsLeft - 1, pos - 1)) % MOD; // Move Right res = (res + solve(stepsLeft - 1, pos + 1)) % MOD; memo[stepsLeft][pos] = (int) res; return (int) res; }}Complexity
Time
O(steps * min(arrLen, steps)). Each state `(stepsLeft, pos)` is computed only once. The number of states is `steps * maxPos`, where `maxPos` is `min(arrLen, steps + 1)`.
Space
O(steps * min(arrLen, steps)). This is for the memoization table `memo` which stores the result for each state `(steps, pos)`. The recursion depth can also go up to `steps`, contributing to stack space.
Trade-offs
Pros
Intuitive and closely follows the problem's recursive definition.
Handles the state space pruning (
pos > stepsLeft) naturally.
Cons
May lead to stack overflow for very large
steps(not an issue with the given constraints).Generally has higher overhead than iterative bottom-up approaches due to function calls.
Solutions
Solution
class Solution {private Integer[][] f;private int n;public int numWays(int steps, int arrLen) { f = new Integer[steps][steps + 1]; n = arrLen; return dfs(0, steps); }private int dfs(int i, int j) { if (i > j || i >= n || i < 0 || j < 0) { return 0; } if (i == 0 && j == 0) { return 1; } if (f[i][j] != null) { return f[i][j]; } int ans = 0; final int mod = (int)1 e9 + 7; for (int k = -1; k <= 1; ++k) { ans = (ans + dfs(i + k, j - 1)) % mod; } return f[i][j] = ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.