Number of Ways to Stay in the Same Place After Some Steps
Problem
A pointer starts at index 0 of an array of length arrLen. In one step it may move one slot left, one slot right, or stay put, but it must never leave the array. Given steps total moves, count how many distinct move sequences return the pointer to index 0 at the end. Return the count modulo 109 + 7.
steps = 3, arrLen = 24def num_ways(steps, arr_len):
MOD = 10**9 + 7
width = min(arr_len, steps // 2 + 1)
dp = [0] * width
dp[0] = 1
for _ in range(steps):
nxt = [0] * width
for p in range(width):
total = dp[p]
if p > 0:
total += dp[p - 1]
if p + 1 < width:
total += dp[p + 1]
nxt[p] = total % MOD
dp = nxt
return dp[0]function numWays(steps, arrLen) {
const MOD = 1000000007n;
const width = Math.min(arrLen, Math.floor(steps / 2) + 1);
let dp = new Array(width).fill(0n);
dp[0] = 1n;
for (let s = 0; s < steps; s++) {
const nxt = new Array(width).fill(0n);
for (let p = 0; p < width; p++) {
let total = dp[p];
if (p > 0) total += dp[p - 1];
if (p + 1 < width) total += dp[p + 1];
nxt[p] = total % MOD;
}
dp = nxt;
}
return Number(dp[0]);
}class Solution {
public int numWays(int steps, int arrLen) {
long MOD = 1000000007L;
int width = Math.min(arrLen, steps / 2 + 1);
long[] dp = new long[width];
dp[0] = 1;
for (int s = 0; s < steps; s++) {
long[] nxt = new long[width];
for (int p = 0; p < width; p++) {
long total = dp[p];
if (p > 0) total += dp[p - 1];
if (p + 1 < width) total += dp[p + 1];
nxt[p] = total % MOD;
}
dp = nxt;
}
return (int) dp[0];
}
}int numWays(int steps, int arrLen) {
const long long MOD = 1000000007LL;
int width = min(arrLen, steps / 2 + 1);
vector<long long> dp(width, 0);
dp[0] = 1;
for (int s = 0; s < steps; s++) {
vector<long long> nxt(width, 0);
for (int p = 0; p < width; p++) {
long long total = dp[p];
if (p > 0) total += dp[p - 1];
if (p + 1 < width) total += dp[p + 1];
nxt[p] = total % MOD;
}
dp = nxt;
}
return (int) dp[0];
}Explanation
We want to count move sequences, and many of them overlap, so this is a natural dynamic programming problem. Let dp[p] be the number of ways to land on index p after a certain number of steps. We process one step at a time and rebuild the array.
From index p the pointer can go to p−1, stay at p, or go to p+1. Read backwards, the ways to reach p after one more step is the sum of the previous counts at p−1, p, and p+1 — skipping any neighbour that falls outside the array. That gives the recurrence next[p] = dp[p−1] + dp[p] + dp[p+1].
The key optimization is on the width. To come back to index 0 after steps moves, the pointer can wander out at most steps / 2 slots — it needs the other half of its moves to walk home. So positions beyond min(arrLen, steps/2 + 1) are unreachable and can be dropped, no matter how large arrLen is.
We start with dp[0] = 1 (one way to be at the start before moving) and apply the recurrence steps times, taking everything modulo 109 + 7 to keep the numbers small. The final answer is dp[0].
Example: steps = 3, arrLen = 2. The width caps at min(2, 2) = 2. Starting at [1, 0], the array evolves to [1, 1], then [2, 2], then dp[0] becomes 2 + 2 = 4 — matching the four sequences listed above.