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, Stay
Example 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, Stay
Example 3:
Input: steps = 4, arrLen = 2 Output: 8
Constraints:
1 <= steps <= 5001 <= arrLen <= 106The key observation in #1269 Number of Ways to Stay in the Same Place After Some Steps is that at each step you can move left, right, or stay. Since we must end at index 0 after exactly steps, we can model the process using dynamic programming. Let dp[i][j] represent the number of ways to reach position j after i steps.
From each state, transitions occur from three possible previous positions: j (stay), j-1 (move right), and j+1 (move left). However, we never need to consider positions beyond min(arrLen - 1, steps) because it is impossible to travel farther than the number of steps available.
To optimize space, we can compress the DP table into a rolling array since each step only depends on the previous step. The final answer is the number of ways to return to index 0 after all steps, computed modulo 1e9 + 7. This approach efficiently reduces unnecessary state exploration.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with State Compression | O(steps × min(arrLen, steps)) | O(min(arrLen, steps)) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Try with Dynamic programming, dp(pos,steps): number of ways to back pos = 0 using exactly "steps" moves.
Notice that the computational complexity does not depend of "arrlen".
This approach leverages dynamic programming to find the number of ways to stay at index 0 after a given number of steps. We define a 2D table dp[i][j] where i represents the number of steps remaining, and j represents the current position of the pointer.
To optimize computation, we can limit the table size to the minimum of steps and arrLen since going beyond these positions is unnecessary.
Time Complexity: O(steps * min(steps, arrLen))
Space Complexity: O(steps * min(steps, arrLen))
1const MOD = 1000000007;
2
3function numWays(steps, arrLen) {
4 const maxPos = Math.min(steps, arrLen -
This JavaScript implementation follows the dynamic programming strategy to compute the required count of ways. It controls the array size using generic JavaScript functionality such that the number of computations remains efficient and manageable.
This approach utilizes recursion combined with memoization to optimize the recursive calls. Here, recursion is used to explore all possible paths dynamically adjusting by staying at, moving left, or moving right from each position in every step.
The results of the recursive calls are stored in a memoization table to avoid redundant calculations.
Time Complexity: O(steps * min(steps, arrLen))
Space Complexity: O(steps * min(steps, arrLen))
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving dynamic programming state transitions and movement constraints are common in FAANG-style interviews. This problem tests DP modeling, optimization, and understanding of state limits.
The optimal approach uses dynamic programming where dp[i][j] represents the number of ways to be at position j after i steps. Transitions consider staying in place, moving left, or moving right. Limiting positions to min(arrLen - 1, steps) keeps the state space manageable.
You cannot move farther from the origin than the number of steps taken. Therefore, positions greater than min(arrLen - 1, steps) are unreachable and can be ignored, which significantly reduces computation.
A dynamic programming array is the most suitable structure for this problem. Using a rolling 1D array helps reduce memory usage while still capturing all valid transitions between steps.
This C implementation uses recursion with memoization. The recursive function explores all directions (stay, left, right) and stores results in a cache to prevent redundant computation, ensuring efficiency.