Number of Ways to Stay in the Same Place After Some Steps — Hard Problem & Solution

Problem statement

A pointer sits at index 0 of an array of length arrLen. In one step it may move one left, one right, or stay, never leaving the array.

Return the number of step sequences of length exactly steps that leave the pointer back at index 0, modulo 10⁹ + 7.

Example 1

Input: steps = 3, arrLen = 2
Output: 4
Explanation: `stay,stay,stay`; `stay,right,left`; `right,left,stay`; `right,stay,left`.

Example 2

Input: steps = 2, arrLen = 4
Output: 2
Explanation: `stay,stay` and `right,left`.

Example 3

Input: steps = 4, arrLen = 2
Output: 8

Constraints

• 1 <= steps <= 500
• 1 <= arrLen <= 10^6

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

Layered DP over the step count. dp[p] counts the sequences that leave the pointer at index p. Each step spreads every position's count to itself and to its two neighbours, staying inside the array.

Approach

1. Set the usable width to min(arrLen, steps + 1) — anything beyond is unreachable.
2. Start with dp[0] = 1.
3. Repeat steps times: build next by adding dp[p] into next[p], next[p-1] and next[p+1] where those exist, modulo 10⁹ + 7.
4. Return dp[0].

Why it works

Capping the width is what makes the problem tractable at arrLen = 10⁶: to return to index 0 in steps moves the pointer can never have gone further than steps / 2, and even the generous bound steps + 1 keeps the table at 501 entries. Without the cap the DP would allocate a million-wide row 500 times over for positions that can never be reached, let alone returned from.

Complexity

• Time — O(steps · min(arrLen, steps))
• Space — O(min(arrLen, steps))

Pitfalls

• Allocating arrLen cells is the trap the constraints are built around.
• The pointer must not step outside the array, so the edges have fewer options.
• Sequences are counted, not final positions — staying put is a distinct move.

Reference solution

Python

def numWays(steps: int, arrLen: int) -> int:
    MOD = 10**9 + 7
    width = min(arrLen, steps + 1)
    dp = [0] * width
    dp[0] = 1
    for _ in range(steps):
        nxt = [0] * width
        for p in range(width):
            if dp[p] == 0:
                continue
            nxt[p] = (nxt[p] + dp[p]) % MOD
            if p > 0:
                nxt[p - 1] = (nxt[p - 1] + dp[p]) % MOD
            if p + 1 < width:
                nxt[p + 1] = (nxt[p + 1] + dp[p]) % MOD
        dp = nxt
    return dp[0]

JavaScript

var numWays = function(steps, arrLen) {
    var MOD = 1000000007;
    var width = Math.min(arrLen, steps + 1), p;
    var dp = [];
    for (p = 0; p < width; p++) dp.push(0);
    dp[0] = 1;
    for (var s = 0; s < steps; s++) {
        var next = [];
        for (p = 0; p < width; p++) next.push(0);
        for (p = 0; p < width; p++) {
            if (dp[p] === 0) continue;
            next[p] = (next[p] + dp[p]) % MOD;
            if (p > 0) next[p - 1] = (next[p - 1] + dp[p]) % MOD;
            if (p + 1 < width) next[p + 1] = (next[p + 1] + dp[p]) % MOD;
        }
        dp = next;
    }
    return dp[0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Count Ways to Make Array With Product Hard
• Count the Number of Ideal Arrays Hard
• Number of Ways to Rearrange Sticks With K Sticks Visible Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard