Cracking the LeetCode - 1269
Number of Ways to Stay in the Same Place After Some Steps
Introduction
I am writing this summary on a Sunday afternoon, many days before this will get published, and before even reading the problem for today's LeetCode challenge. I am home alone and am committed to completing this before the end of the day which I usually don't have time to do so let's get into it.
Problem
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 10<sup>9</sup> + 7.
Examples
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 <= 10<sup>6</sup>
Process
As I am writing this blog entry while solving the challenge, I'm going to give the play-by-play without any filtering so here goes nothing. I start by breaking down the problem:
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).
- My understanding of this is that I start at the first item in an array and then for each step (like a turn in a game) I can move to an element either side of where I am or stay put.
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 10<sup>9</sup> + 7.
- So I am given the number of steps (or the number of turns in my game) and the length of the array (which will give me an upper and lower bound). I then have to find all the different combinations of moves that will return me to the first item in the array. The one part I don't quite understand at the moment is 'return it modulo
10<sup>9</sup> + 7' but we will get back to that.
Going forward I'm going to use the terminology of the examples, where moving index + 1 is moving Right, moving index - 1 is moving Left, and not moving is to Stay.
My immediate thought is that there will always be the case where you never move from the initial starting index which will give you one way to still be at index 0. My next thought is that there is no way for the last move to be a move to the right - to finish at index 0 you must at some point move from index 1 to 0 and then move no more. I also note that you can only start with either not moving or moving to the right. However, these isolated ideas aren't helping me get closer to a solution.
Approach 1
My initial thought is to start with all Stay's and then for each new combination, change the least amount of moves to also end up at index 0.
I would need to store a list of each combination to check against to make sure I'm not repeating combinations
I would also need to come up with some mechanism that could figure out how to get back to index 0.
I don't love this idea, feels a bit linear and brute force-y. Onto the next:
Approach 2
I start with all the options for Move 1.
- This has to be Stay or Right
I would then figure out all the possible options for all of Move 2.
Stay -> Stay or Right
Right -> Stay, Left, Right
I repeat this until I get to Move n where n is the length of the array. Note for each step I would have to figure out if it's possible to get back to index 0.
E.g. # of steps is 5
If I am at index 2 after 3 steps, the only possible options is Left as to Stay or move Right would not allow the pointer to get back to index 0 in the 2 remaining steps.
The number of total options on the last step should give me the total number of moves.
E.g. # of steps is 4, array length is 3, (i) indicates the index of the pointer.
Step 1: Stay (0), Right (1)
Stay -> Stay (0), Right (1)
Right-> Stay (1), Right (2), Left (0)
Stay -> Stay -> Stay (0), Right (1)
Stay -> Right -> Stay (1), Left (0)
Right -> Stay -> Stay (1), Left (0)
Right -> Right -> Left (1)
Right -> Left -> Stay (0), Right (1)
Stay -> Stay -> Stay -> Stay (0)
Stay -> Stay -> Right -> Left (0)
Stay -> Right -> Stay -> Left (0)
Stay -> Right -> Left -> Stay (0)
Right -> Stay -> Stay -> Left (0)
Right -> Stay -> Left -> Stay (0)
Right -> Right -> Left -> Left (0)
Right -> Left -> Stay -> Stay (0)
Right -> Left -> Right -> Left (0)
Total moves: 9
Having written this solution out, I found several helpful shortcuts. Firstly, because the final move can only be from either index 0 or index 1, I only need to find all combinations for steps - 1. I also noticed that I was able to calculate which moves were possible based only on the current index and the number of moves remaining using the following rules:
Left: index > 0
Stay: index < # of moves remaining
Right: index < moves remaining - 1 AND index < length of array
And I think that's everything I need. Time to write some code...
The first function I need will take in the # of steps left, length of the array, and current index of the pointer and return a list of possible indexes that the pointer could be at after the step:
ublic HashSet<int> ProcessStep(int index, int stepsRemaining, int arrLen) {
HashSet<int> possibleIndex = new HashSet<int>();
if (index > 0) {
possibleIndex.Add(index - 1);
}
if (index < stepsRemaining) {
possibleIndex.Add(index);
}
if (index < stepsRemaining - 1 && index < arrLen) {
possibleIndex.Add(index + 1);
}
return possibleIndex
}
This was great for the first step but I immediately ran into the issue of iterating for all steps and keeping track of all the possible outcomes each time. So instead of passing in the current index, I made it pass in all the possible indexes. Obviously, I can no longer use a HashSet so I also changed this to be a List and then I modified it to loop over every possible index each step and get the final number of steps at the end.:
public class Solution {
public int NumWays(int steps, int arrLen) {
List<int> indexes = ProcessStep(new List<int>{0}, steps, arrLen);
steps -= 1;
while (steps > 1) {
indexes = ProcessStep(indexes, steps, arrLen);
steps -= 1;
}
return indexes.Count;
}
public List<int> ProcessStep(List<int> indexSet, int stepsRemaining, int arrLen) {
List<int> possibleIndex = new List<int>();
foreach (int i in indexSet) {
if (i > 0) {
possibleIndex.Add(i - 1);
}
if (i < stepsRemaining) {
possibleIndex.Add(i);
}
if (i < stepsRemaining - 1 && i < arrLen) {
possibleIndex.Add(i + 1);
}
}
return possibleIndex;
}
}
All 3 test cases passed! However, I decided to test out test cases written myself and with any step value greater than 20 I had a runtime error of "Out of memory". Back to the drawing board.
Approach 3
Thinking back, I now remember that there may not even be enough memory to return the correct int and round down to 109 + 7. So I need a more memory-efficient solution which would be counting the number of ways to get to index 0 at each step but not storing those values except for the count. Best way to achieve this: dynamic programming.
In this particular case, we can use something known as Tabulation to fill a 2D array iteratively. The idea here is that we can iterate through all the steps, and at each step iterate through all the possible positions (max position being the minimum value between half the steps and the last index in the array) to determine the number of ways to either stay in the same place, move one step to the left, or move one step to the right, and end up at that position.
This is done by checking for three things at each iteration:
The pointer can always Stay (as we never iterate past the max position) so add the moves from the previous step at the same index.
Can the pointer move left? Then add the moves from the previous step but the index to the left
Can the point move right? Then add the moves from the previous step but the index to the right
The loop looks a little something like this:
arr[0,0] = 1; // Starting point
for (int i = 1; i <= steps; i++) {
for (int j = 0; j <= furthestIndex; j++) {
arr[i, j] = arr[i - 1, j];
if (j > 0) {
arr[i, j] = (arr[i, j] + arr[i - 1, j - 1]) % max;
}
if (j < furthestIndex) {
arr[i, j] = (arr[i, j] + arr[i - 1, j + 1]) % max;
}
}
}
After writing this out, I realised that keeping track of the entire array wasn't necessary as you only ever use the values form the previous step. I modified the loop to then look this this:
for (int i = 1; i <= steps; i++) {
for (int j = 0; j <= furthestIndex; j++) {
curIndex[j] = prevIndex[j];
if (j > 0) {
curIndex[j] = (curIndex[j] + prevIndex[j - 1]) % max;
}
if (j < furthestIndex) {
curIndex[j] = (curIndex[j] + prevIndex[j + 1]) % max;
}
}
var tempArray = curIndex;
curIndex = prevIndex;
prevIndex = tempArray;
}
Solution
C
Here is the final C# solution using Bottom-Up Dynamic Programming:
public class Solution {
public int NumWays(int steps, int arrLen) {
const int max = 1000000007; // 10^9 + 7
// Furthest we can travel while still being able to get back to index
int furthestIndex = Math.Min(arrLen - 1, steps / 2 );
int[] curIndex = new int[furthestIndex + 1];
int[] prevIndex = new int[furthestIndex + 1];
prevIndex[0] = 1;
for (int i = 1; i <= steps; i++) {
for (int j = 0; j <= furthestIndex; j++) {
curIndex[j] = prevIndex[j];
if (j > 0) {
curIndex[j] = (curIndex[j] + prevIndex[j - 1]) % max;
}
if (j < furthestIndex) {
curIndex[j] = (curIndex[j] + prevIndex[j + 1]) % max;
}
}
var tempArray = curIndex;
curIndex = prevIndex;
prevIndex = tempArray;
}
return prevIndex[0];
}
}
Python
And as usual, here it is in Python3:
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
max = 1000000007
furthest_index = min(arrLen - 1, steps // 2 )
cur_index = [0] * (furthest_index + 1)
prev_index = [0] * (furthest_index + 1)
prev_index[0] = 1
for i in range(1, steps + 1):
for j in range(furthest_index + 1):
cur_index[j] = prev_index[j]
if j > 0:
cur_index[j] = (cur_index[j] + prev_index[j - 1]) % max
if j < furthest_index:
cur_index[j] = (cur_index[j] + prev_index[j + 1]) % max
cur_index, prev_index = prev_index, cur_index
return prev_index[0]
Conclusion
This took me a lot longer than I was expecting. While it isn't obvious in the blog post, the gap between Approaches 2 and 3 was many hours. I hadn't had to use dynamic programming in a long time, especially not at work, so it took me a lot of playing around to get to the answer. I even started going down the ternary tree route during that time but didn't bother mentioning it as it was a dead end pretty early on.
I tried out a different syntactical approach to my C# code this time around by not new-lining the initial curly braces. This was just to see how it would look as I almost always place it on a new line in C# for ease of reading. I think I will go back to using that method as I wasn't fussed this way (and I see it more as a Javascript convention).
I think exploring other dynamic programming approaches to this problem would be useful. I assume you could attempt it with a Top-Down approach instead but I didn't put much thought into this as I was already deep in trying it from the bottom up by the time I got to my final solution. There may also be a nicer way to do use functions recursively to achieve the same thing which might be worthwhile trying out if anyone else want sot have a go at this.