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

Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

Problem Understanding

This problem asks us to count how many different ways a pointer can end up back at index 0 after taking exactly steps moves inside an array of length arrLen.

We start with a pointer positioned at index 0. For every step, we have exactly three possible actions:

Move one position to the left.
Move one position to the right.
Stay at the current position.

However, there is an important restriction: the pointer can never leave the bounds of the array. That means we cannot move left from index 0, and we cannot move right from index arrLen - 1.

The input consists of two integers:

steps, which tells us exactly how many moves we must make.
arrLen, which represents the size of the array.

The output is the number of distinct valid movement sequences that result in the pointer being back at index 0 after exactly steps moves.

Since the answer can become extremely large, we return the result modulo 10^9 + 7.

The constraints reveal an important challenge:

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

The very large upper bound for arrLen suggests that we cannot afford algorithms proportional to the full array size. However, steps is only 500, which hints that the reachable region of the array is actually much smaller than arrLen.

An important observation is that after steps moves, the pointer can never be farther than steps positions away from index 0. In fact, because we must eventually return to 0, going beyond steps // 2 + 1 positions is pointless. This dramatically reduces the effective search space.

Several edge cases are important:

If arrLen = 1, the pointer cannot move left or right, so the only valid action is staying in place every step.
If steps = 1, the only way to remain at index 0 is to stay.
When arrLen is huge, for example 10^6, we must avoid creating DP arrays of that size because most positions are unreachable.
Cases where the pointer is near the boundaries require careful handling to avoid invalid indices.

Approaches

Brute Force Approach

A straightforward solution is to recursively explore every possible sequence of moves. At each step, we branch into three possibilities:

Move left
Move right
Stay

We continue this recursion until exactly steps moves have been taken. If the pointer ends at index 0, we count that path as valid.

This approach is correct because it exhaustively considers every possible valid sequence of actions.

However, the runtime becomes prohibitively expensive. Since each step introduces up to three choices, the total number of paths grows exponentially.

The time complexity becomes roughly O(3^steps), which is impossible for steps = 500.

We can improve brute force slightly using memoization, since many states repeat. Specifically, the same (remaining_steps, position) state may be computed multiple times.

Key Insight for the Optimal Solution

The problem has overlapping subproblems and optimal substructure, making it a strong candidate for dynamic programming.

Let us define:

dp[i][j] = number of ways to be at index j after i steps

From any position j, we can arrive there in three ways:

Stay at j
Move right from j - 1
Move left from j + 1

Thus:

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]

We also notice an important optimization:

We never need to consider positions larger than:

min(arrLen - 1, steps // 2 + 1)

Why?

Because if we move too far right, we will not have enough remaining steps to return to 0.

This optimization drastically reduces the state space.

Instead of a full 2D DP table, we can use rolling arrays because each row only depends on the previous row.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	`O(3^steps)`	`O(steps)`	Tries every movement sequence recursively
Optimal Dynamic Programming	`O(steps × min(arrLen, steps))`	`O(min(arrLen, steps))`	Uses rolling DP and reachable-state pruning

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

Determine the maximum reachable position

We only care about indices that can realistically contribute to a valid return to index 0.

We compute:

max_position = min(arrLen - 1, steps // 2 + 1)

This avoids wasting memory on unreachable indices. 2. Initialize the DP array

We create a DP array where:

dp[position]

stores the number of ways to reach that position after the current number of steps.

Initially:

dp[0] = 1

because we start at index 0. 3. Iterate through each step

For every step, create a new array called next_dp.

This array represents the number of ways to reach each position after one additional move. 4. Update transitions

For every reachable position pos:

Stay in place:

next_dp[pos] += dp[pos]

Move left:

next_dp[pos - 1] += dp[pos]

Move right:

next_dp[pos + 1] += dp[pos]

We only perform moves that remain inside bounds. 5. Apply modulo arithmetic

Since values grow extremely quickly, every update is performed modulo:

10^9 + 7

Replace the old DP array

After processing one step:

dp = next_dp

Return the answer

After exactly steps iterations, return:

dp[0]

Why it works

The algorithm maintains the invariant that after processing i steps, dp[j] represents the exact number of valid ways to stand at position j.

Every legal move is accounted for exactly once through the recurrence relation. Since transitions only come from the immediately previous step, and because invalid boundary moves are excluded, every counted path is valid and every valid path is counted.

Thus, after all steps are processed, dp[0] contains precisely the number of ways to return to index 0.

Python Solution

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9 + 7

        max_position = min(arrLen - 1, steps // 2 + 1)

        dp = [0] * (max_position + 1)
        dp[0] = 1

        for _ in range(steps):
            next_dp = [0] * (max_position + 1)

            for pos in range(max_position + 1):
                ways = dp[pos]

                if ways == 0:
                    continue

                # Stay
                next_dp[pos] = (next_dp[pos] + ways) % MOD

                # Move left
                if pos > 0:
                    next_dp[pos - 1] = (
                        next_dp[pos - 1] + ways
                    ) % MOD

                # Move right
                if pos < max_position:
                    next_dp[pos + 1] = (
                        next_dp[pos + 1] + ways
                    ) % MOD

            dp = next_dp

        return dp[0]

The implementation begins by computing the effective maximum position that can matter. This optimization prevents allocating memory proportional to arrLen, which could be as large as one million.

The dp array stores the number of ways to reach each position after the current step count. Initially, only position 0 is reachable.

For every step, we construct next_dp, which represents the next layer of states. For each position, we propagate its contribution to staying, moving left, and moving right, while respecting boundaries.

Modulo arithmetic ensures numbers remain manageable and satisfies the problem requirements.

At the end of all iterations, dp[0] holds the final answer.

Go Solution

func numWays(steps int, arrLen int) int {
	const mod = 1000000007

	maxPosition := steps/2 + 1
	if arrLen-1 < maxPosition {
		maxPosition = arrLen - 1
	}

	dp := make([]int, maxPosition+1)
	dp[0] = 1

	for step := 0; step < steps; step++ {
		nextDP := make([]int, maxPosition+1)

		for pos := 0; pos <= maxPosition; pos++ {
			ways := dp[pos]

			if ways == 0 {
				continue
			}

			// Stay
			nextDP[pos] = (nextDP[pos] + ways) % mod

			// Move left
			if pos > 0 {
				nextDP[pos-1] = (nextDP[pos-1] + ways) % mod
			}

			// Move right
			if pos < maxPosition {
				nextDP[pos+1] = (nextDP[pos+1] + ways) % mod
			}
		}

		dp = nextDP
	}

	return dp[0]
}

The Go implementation closely mirrors the Python logic. Slices are used for dynamic arrays, and integer modulo operations are performed during every update.

Unlike Python, Go uses fixed integer types, but integer overflow is not a concern here because every operation is reduced modulo 10^9 + 7.

The rolling DP optimization is identical, meaning space usage remains efficient.

Worked Examples

Example 1

Input:

steps = 3
arrLen = 2

Maximum position:

min(1, 3//2 + 1)
= min(1, 2)
= 1

Initial state:

Step	DP State
0	`[1, 0]`

After step 1:

From position 0:

Stay → 0
Right → 1

Step	DP State
1	`[1, 1]`

After step 2:

From position 0:

Stay → 0
Right → 1

From position 1:

Stay → 1
Left → 0

Step	DP State
2	`[2, 2]`

After step 3:

From position 0:

Stay → 0
Right → 1

From position 1:

Stay → 1
Left → 0

Step	DP State
3	`[4, 4]`

Answer:

dp[0] = 4

Example 2

Input:

steps = 2
arrLen = 4

Maximum position:

min(3, 2)
= 2

Initial:

Step	DP State
0	`[1, 0, 0]`

After step 1:

Step	DP State
1	`[1, 1, 0]`

After step 2:

Step	DP State
2	`[2, 2, 1]`

Answer:

Example 3

Input:

steps = 4
arrLen = 2

Initial:

Step	DP State
0	`[1, 0]`
1	`[1, 1]`
2	`[2, 2]`
3	`[4, 4]`
4	`[8, 8]`

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(steps × min(arrLen, steps))`	We process each step across all reachable positions
Space	`O(min(arrLen, steps))`	Only one rolling DP array is stored

The key optimization comes from limiting the reachable positions. Instead of iterating over the entire array length, which could be up to one million, we only consider positions that can realistically be visited and still allow a return to index 0. Since steps <= 500, the DP remains efficient.

Test Cases

solution = Solution()

assert solution.numWays(3, 2) == 4  # Example 1
assert solution.numWays(2, 4) == 2  # Example 2
assert solution.numWays(4, 2) == 8  # Example 3

assert solution.numWays(1, 1) == 1  # Only stay possible
assert solution.numWays(1, 2) == 1  # One step, must stay
assert solution.numWays(2, 1) == 1  # Cannot move anywhere

assert solution.numWays(3, 1) == 1  # Always forced to stay
assert solution.numWays(5, 1) == 1  # Larger stay-only case

assert solution.numWays(2, 2) == 2  # Stay-stay, right-left
assert solution.numWays(3, 3) == 4  # Small balanced case

assert solution.numWays(500, 1000000) > 0  # Large arrLen stress test
assert solution.numWays(500, 500) > 0  # Maximum practical DP size

Test	Why
`(3, 2)`	Validates Example 1
`(2, 4)`	Validates Example 2
`(4, 2)`	Validates Example 3
`(1, 1)`	Minimum possible input
`(1, 2)`	Single step edge case
`(2, 1)`	Array length prevents movement
`(3, 1)`	Only staying allowed
`(5, 1)`	Repeated forced staying
`(2, 2)`	Small transition correctness
`(3, 3)`	Balanced reachable states
`(500, 1000000)`	Large `arrLen` optimization test
`(500, 500)`	Maximum dynamic programming workload

Edge Cases

Edge Case 1: `arrLen = 1`

When the array length is one, index 0 is the only valid position. The pointer cannot move left or right.

A buggy implementation might still try to access neighboring positions and produce index errors.

This implementation handles it naturally because:

max_position = 0

The DP array only has one element, and only the "stay" transition is valid.

Edge Case 2: Very Large `arrLen`

The constraint allows:

arrLen = 10^6

A naive DP using the full array size would waste enormous memory and time.

The optimization:

min(arrLen - 1, steps // 2 + 1)

ensures we only consider positions that are realistically reachable.

Since steps <= 500, memory remains small even when arrLen is huge.

Edge Case 3: Small Number of Steps

When steps is very small, such as 1, the pointer has almost no flexibility.

For example:

steps = 1
arrLen = 2

The only valid way to remain at index 0 is:

Stay

The DP transitions correctly produce this because moving right would leave the pointer at index 1, which does not contribute to the final answer.

Edge Case 4: Boundary Positions

Whenever the pointer is at index 0, moving left is invalid. Similarly, moving right from the last valid position is invalid.

The implementation explicitly checks:

if pos > 0

and

if pos < max_position

to prevent out-of-bounds transitions. This guarantees correctness near array boundaries.

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

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight for the Optimal Solution

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Edge Cases

Edge Case 1: arrLen = 1

Edge Case 2: Very Large arrLen

Edge Case 3: Small Number of Steps

Edge Case 4: Boundary Positions

Edge Case 1: `arrLen = 1`

Edge Case 2: Very Large `arrLen`