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

You have a pointer at index 0 in an array of size arrLen. At each step, you can move one position to the left, one position to the right, or stay in place. Given steps total steps, how many different ways can you end up back at index 0?

This is LeetCode 1269: Number of Ways to Stay in the Same Place After Some Steps, and it is a great exercise in 2D dynamic programming with a space optimization twist. The trick is recognizing that you do not need to track all arrLen positions, because you can never move farther than steps / 2 positions away from the start. Return the result modulo 10^9 + 7.

Why this problem matters

At first glance, this looks like a complex counting problem. But it follows the same DP pipeline you have seen in Climbing Stairs and Unique Paths: define a state, write a recurrence, fill a table. The new wrinkle here is that the array can be enormous (up to 10^6), so you need to be clever about which positions you actually track. That pruning insight is what makes this a hard problem rather than a medium one.

The DP formulation

Define dp[step][pos] as the number of ways to be at position pos after exactly step steps. The recurrence is:

• dp[0][0] = 1 (start at position 0)
• dp[0][pos] = 0 for all pos > 0
• For each subsequent step: dp[step][pos] = dp[step-1][pos] + dp[step-1][pos-1] + dp[step-1][pos+1]

The three terms correspond to the three choices at the previous step: stay in place, arrive from the left, or arrive from the right. Boundary conditions apply: if pos = 0 there is no pos - 1 contribution, and if pos = arrLen - 1 there is no pos + 1 contribution.

The key optimization: position pos is only reachable if pos <= steps // 2. You can never move more than steps // 2 positions away and still make it back to 0. So the effective number of positions is min(arrLen, steps // 2 + 1).

Starting with the 2D table

Here is the full 2D DP approach. We build a table of size (steps + 1) x maxPos where maxPos = min(arrLen, steps // 2 + 1).

def numWays(steps, arrLen):
    MOD = 10**9 + 7
    max_pos = min(arrLen, steps // 2 + 1)
    dp = [[0] * max_pos for _ in range(steps + 1)]
    dp[0][0] = 1

    for s in range(1, steps + 1):
        for p in range(max_pos):
            dp[s][p] = dp[s - 1][p]
            if p > 0:
                dp[s][p] += dp[s - 1][p - 1]
            if p < max_pos - 1:
                dp[s][p] += dp[s - 1][p + 1]
            dp[s][p] %= MOD

    return dp[steps][0]

This works, but it uses O(steps * maxPos) space. Since each row only depends on the previous row, we can compress this to a single 1D array.

Optimizing to O(n) space

We only need the previous row to compute the current row. Use two 1D arrays (or overwrite carefully) to cut space from O(steps * maxPos) to O(maxPos).

def numWays(steps, arrLen):
    MOD = 10**9 + 7
    max_pos = min(arrLen, steps // 2 + 1)
    dp = [0] * max_pos
    dp[0] = 1

    for s in range(1, steps + 1):
        new_dp = [0] * max_pos
        for p in range(max_pos):
            new_dp[p] = dp[p]
            if p > 0:
                new_dp[p] += dp[p - 1]
            if p < max_pos - 1:
                new_dp[p] += dp[p + 1]
            new_dp[p] %= MOD
        dp = new_dp

    return dp[0]

Time: O(steps * min(arrLen, steps / 2)). We fill one row of length maxPos for each of the steps iterations.

Space: O(min(arrLen, steps / 2)). Just two arrays of length maxPos.

Step-by-step walkthrough

Let's trace through a small example: steps = 3, arrLen = 2. The reachable positions are 0 and 1.

The four paths that return to position 0 after 3 steps are:

• Stay, stay, stay: 0 -> 0 -> 0 -> 0
• Stay, right, left: 0 -> 0 -> 1 -> 0
• Right, left, stay: 0 -> 1 -> 0 -> 0
• Right, stay, left: 0 -> 1 -> 1 -> 0

Complexity analysis

The min(arrLen, steps // 2 + 1) bound is critical. Without it, you would allocate arrays of size arrLen (up to 10^6) for every step, which would be far too slow and memory-heavy. With the bound, the effective position count never exceeds steps // 2 + 1, which is at most 250 when steps = 500.

The building blocks

This problem is built on two reusable patterns working together.

The first is 2D grid DP with row compression. The table has steps on one axis and positions on the other. Each cell depends on three neighbors in the previous row (left, same, right). Because you only look back one row, you can compress the 2D table into a single 1D array. This is the same space optimization you see in Unique Paths and Edit Distance.

The second is state space pruning. The array can be enormous, but the pointer can never travel more than steps // 2 positions away and still return to 0. This observation shrinks the problem from potentially millions of positions down to a few hundred. Recognizing when the state space is smaller than it appears is a skill that shows up in many hard DP problems.

Together, these two building blocks give you:

• State: dp[pos] = number of ways to be at position pos after the current step
• Transition: dp[pos] = prev[pos] + prev[pos-1] + prev[pos+1] (with boundary checks)
• Pruning: only track positions 0 through min(arrLen, steps // 2 + 1) - 1
• Space optimization: keep only the current and previous row

Edge cases to watch for

• steps = 0: return 1. You are already at position 0 with zero steps taken.
• arrLen = 1: you can only stay in place every step, so the answer is always 1.
• Large steps with small arrLen: the pruning bound is min(arrLen, steps // 2 + 1). When arrLen = 2 and steps = 500, you only track 2 positions, making the problem very fast.
• Modular arithmetic: do not forget to take mod 10^9 + 7 at each step. The numbers grow quickly.

From understanding to recall

You have walked through the full solution, from the 2D DP formulation to the space-optimized version with position pruning. The logic clicks when you read it. But reproducing it under pressure requires more than comprehension.

In an interview, you need to identify the state (dp[step][pos]), write the three-way recurrence, remember the pruning bound, and implement the 1D optimization. That is a lot of moving parts to hold in your head at once. Spaced repetition turns each piece into something automatic.

The combination of 2D grid DP and state space pruning appears in many hard problems. Drilling this problem at increasing intervals trains you to spot both patterns quickly and wire them together without hesitation. After a few reps, the setup writes itself.

Related posts

• Climbing Stairs - The simplest linear DP, teaching the recursion-to-table pipeline that this problem builds on
• Unique Paths - 2D grid DP with row compression, the same space optimization technique used here
• Coin Change - Classic 1D DP with variable lookback, another essential building block for counting problems