Leetcode 1269. Number of Ways to Stay in the Same Place After Some Steps
The Problem
In the problem, we are given an array of a certain size (arrLen
) and a pointer which starts at index 0
of the array.
In each step, the pointer can either:
- Move one position to the left
- Move one position to the right
- Stay in the same place
However, the pointer should never be placed outside the array at any time.
We are given two integers, steps
and arrLen
, and are asked to return the number of ways
such that the pointer still ends up at index 0
after exactly steps
steps.
Because the answer could be very large, we need to return it modulo 10^9 + 7
.
Example Walkthrough
Input: steps = 3
, arrLen = 2
Output: 4
Explanation:
Here are the 4 different ways to stay at index 0
after 3
steps with an array length of 2
:
- Move right, move left, stay
- Stay, move right, move left
- Move right, stay, move left
- Stay, stay, stay
Solution Approach
The approach towards solving this problem involves the use of dynamic programming.
Dynamic programming involves breaking down a problem into smaller subproblems, and storing the solution to each subproblem so that each subproblem is only solved once, thus reducing the computation time.
We use a dynamic programming array dp[]
where dp[i]
holds the number of ways to stay on index i
.
We iterate through the steps, and for each step, we create a newDP array. In that array, for each index i
, we determine the number of ways to stay on index i
.
If the pointer can move left (i.e., i-1
is not out of array bounds), we add the number of ways to stay on index i-1
(dp[i-1]
) to newDP[i]
.
Similarly, if the pointer can move right (i.e., i+1
is not out of array bounds), we add the number of ways to stay on index i+1
(dp[i+1]
) to newDP[i]
.
Ultimately, dp[0]
holds the number of ways to end up at index 0
after all steps.
Example
Suppose we have steps = 3
and arrLen = 2
.
We create our dp[]
array with 3
elements all initialized to 0
except dp[0]
which is initialized to 1
.
In the first step:
newDp[0] = dp[0] + dp[1] = 1 + 0 = 1
newDp[1] = dp[1] + dp[0] + dp[2] = 0 + 1 + 0 = 1
In the second step:
newDp[0] = dp[0] + dp[1] = 1 + 1 = 2
newDp[1] = dp[1] + dp[0] + dp[2] = 1 + 2 + 0 = 3
And so on...
Solutions
For each given language, the solution will adhere to the approach we've discussed. A class Solution
is given with a method numWays(steps, arrLen)
which takes steps
and arrLen
as parameters and returns the number of ways to stay at index 0
after exactly steps
steps mod 10^9 + 7
.
The Time Complexity of these solution is O(steps)
Python Solution
1 2python 3class Solution: 4 def numWays(self, steps: int, arrLen: int) -> int: 5 MOD = 10 ** 9 + 7 6 dp = [0] * min(arrLen, steps // 2 + 2) 7 dp[0] = 1 8 for _ in range(steps): 9 dpNew = list(dp) 10 for i in range(len(dpNew)-1): 11 dpNew[i] += dp[i+1] 12 dpNew[i] %= MOD 13 if i+1 < len(dpNew) - 1: 14 dpNew[i+1] += dp[i] 15 dpNew[i+1] %= MOD 16 dp = dpNew 17 return dp[0]
Java Solution
1 2java 3public class Solution { 4 public int numWays(int steps, int arrLen) { 5 int MOD = 1000000007; 6 int maxColumn = Math.min(arrLen - 1, steps); 7 int[][] dp = new int[steps + 1][maxColumn + 1]; 8 dp[0][0] = 1; 9 for (int i = 1; i <= steps; i++) { 10 for (int j = 0; j <= maxColumn; j++) { 11 dp[i][j] = dp[i - 1][j]; 12 if (j - 1 >= 0) { 13 dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD; 14 } 15 if (j + 1 <= maxColumn) { 16 dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD; 17 } 18 } 19 } 20 return dp[steps][0]; 21 } 22}
JavaScript Solution
1 2javascript 3class Solution { 4 static numWays(steps, arrLen) { 5 let Mod = 1e9 + 7; 6 let dp = Array(steps + 1).fill(0).map(() => Array(Math.min(steps, arrLen) + 1).fill(0)); 7 dp[0][0] = 1; 8 for(let i = 1; i <= steps; i++) { 9 for(let j = 0; j <= Math.min(i, arrLen - 1); j++){ 10 dp[i][j] = dp[i - 1][j]; 11 if(j - 1 >= 0) 12 dp[i][j] = (dp[i][j]+ dp[i - 1][j - 1]) % Mod; 13 if(j + 1 <= arrLen - 1) 14 dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % Mod; 15 } 16 } 17 return dp[steps][0]; 18 }; 19}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int numWays(int steps, int arrLen) { 6 const int MOD = 1e9 + 7; 7 const int n = min(arrLen, steps / 2 + 1); 8 vector<long> dp(n, 0); 9 dp[0] = 1; 10 for(int _ = 0; _ < steps; _++) { 11 vector<long> dp_new(n, 0); 12 for(int i = 0; i < n; i++) { 13 dp_new[i] = (dp_new[i] + dp[i]) % MOD; 14 if(i - 1 >= 0) 15 dp_new[i] = (dp_new[i] + dp[i - 1]) % MOD; 16 if(i + 1 < n) 17 dp_new[i] = (dp_new[i] + dp[i + 1]) % MOD; 18 } 19 dp = dp_new; 20 } 21 return dp[0]; 22 } 23};
C# Solution
1 2csharp 3public class Solution { 4 public int NumWays(int steps, int arrLen) { 5 int MOD = 1000000007; 6 int maxColumn = Math.Min(arrLen - 1, steps); 7 int[,] dp = new int[steps + 1, maxColumn + 1]; 8 dp[0, 0] = 1; 9 for (int i = 1; i <= steps; i++) { 10 for (int j = 0; j <= maxColumn; j++) { 11 dp[i, j] = dp[i - 1, j]; 12 if (j - 1 >= 0) { 13 dp[i, j] = (dp[i, j] + dp[i - 1, j - 1]) % MOD; 14 } 15 if (j + 1 <= maxColumn) { 16 dp[i, j] = (dp[i, j] + dp[i - 1, j + 1]) % MOD; 17 } 18 } 19 } 20 return dp[steps, 0]; 21 } 22}
Each solution first determines the length of the steps array. This is either the length of the array or half the number of steps, whichever is smaller. It then creates an array dp
with that length, where dp[i]
is the number of ways to stay at index i
.
The program then loops once for each step. For each step, it calculates the number of ways to stay at each index position. This requires looking at the previous step's array dp
and adding up the values of the current position, the left position (if applicable), and the right position (if applicable). All these calculations are performed under modulo operation to keep the numbers within the range mentioned in the problem statement.
Finally, it returns the number of ways to stay at index 0 after all steps.In conclusion, the primary approach to solving the problem is based on dynamic programming. The key idea implemented is tracking the number of ways to stay at each index after each step and continuously updating this information. By doing such, you can calculate the final result by looking at the total number of ways to stay at index 0 after all steps. This advanced yet efficient strategy optimizes the time consumption of the problem solving process, making it particularly effective for dealing with large data input. Along the way, by keeping track of all potential positions in an array, we ensure all possible routes are accounted for, hence providing a comprehensive and precise solution.
It should be noted that this approach will only work if the given array size does not exceed half the number of steps due to its dependence on continuous updates at each index of the array. Therefore, this solution should be considered in the appropriate context and with the right constraints, as it might not provide a valid answer with a different set of inputs.
Although presented solutions in multiple languages, Python, Java, JavaScript, C++, and C#, exhibit the same logic, there can be specific differences based on each language's syntactic and structural elements. Nevertheless, there can always be other ways to tackle the problem, so feel free to use these solutions as a starting point and modify or expand on them based on specific requirements or constraints.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.