1269. Number of Ways to Stay in the Same Place After Some Steps LeetCode Solution
In this guide, you will get 1269. Number of Ways to Stay in the Same Place After Some Steps LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Stay in the Same Place After Some Steps problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 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
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 <= 500
1 <= arrLen <= 106
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1269. Number of Ways to Stay in the Same Place After Some Steps LeetCode Solution in C++
class Solution {
public:
int numWays(int steps, int arrLen) {
constexpr int kMod = 1'000'000'007;
const int n = min(arrLen, steps / 2 + 1);
// dp[i] := the number of ways to stay at index i
vector<long> dp(n);
dp[0] = 1;
while (steps-- > 0) {
vector<long> newDp(n);
for (int i = 0; i < n; ++i) {
newDp[i] = dp[i];
if (i - 1 >= 0)
newDp[i] += dp[i - 1];
if (i + 1 < n)
newDp[i] += dp[i + 1];
newDp[i] %= kMod;
}
dp = std::move(newDp);
}
return dp[0];
}
}; /* code provided by PROGIEZ */
1269. Number of Ways to Stay in the Same Place After Some Steps LeetCode Solution in Java
class Solution {
public int numWays(int steps, int arrLen) {
final int kMod = 1_000_000_007;
final int n = Math.min(arrLen, steps / 2 + 1);
// dp[i] := the number of ways to stay at index i
long[] dp = new long[n];
dp[0] = 1;
while (steps-- > 0) {
long[] newDp = new long[n];
for (int i = 0; i < n; ++i) {
newDp[i] = dp[i];
if (i - 1 >= 0)
newDp[i] += dp[i - 1];
if (i + 1 < n)
newDp[i] += dp[i + 1];
newDp[i] %= kMod;
}
dp = newDp;
}
return (int) dp[0];
}
} // code provided by PROGIEZ
1269. Number of Ways to Stay in the Same Place After Some Steps LeetCode Solution in Python
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
kMod = 1_000_000_007
# dp[i] := the number of ways to stay at index i
dp = [0] * min(steps // 2 + 1, arrLen)
dp[0] = 1
for _ in range(steps):
newDp = [0] * min(steps // 2 + 1, arrLen)
for i, ways in enumerate(dp):
if ways > 0:
for dx in (-1, 0, 1):
nextIndex = i + dx
if 0 <= nextIndex < len(dp):
newDp[nextIndex] += ways
newDp[nextIndex] %= kMod
dp = newDp
return dp[0] # code by PROGIEZ
