This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.
This one was an interesting question, it is definitely up there as one of my more liked question have done so far. I tagged title with "no trick explanation", because after looking through the discussion and other possible solutions, I found out there are some tricks and mathematical thing you can do to make the question 1000000x easier. However, we aren't all math magicians and so I'll be guiding you through how a programmer would have solved this instead.
So the first thing you should do is come up with a naive brute force solution. This should be simple enough for most people.
1.) we keep a while loop going for as long as n > 0
2.) inside, we run a for loop iterating through the cells
3.) we'll have 3 pointers: val, prev and next.
val for the cells[index];
prev for value of index-1 and next for index+1
be sure to take care of the beginning and end, I didn't quite get what the question meant and had to find out the hard way that they meant if cell[i] === undefined, keep it undefined instead of 0;
4.) if prev === next, then cells[index] = 1, else =0;
5.) at the end of iteration, we set prev = val
6.) remember to set prev to null at the end of full cells iteration so that it won't affect the next run.
let prev, next
while (n--) {
prev = null;
cells.forEach(function(val, index){
next = cells[index+1];
if (prev === next) {
cells[index] = 1
} else {
cells[index] = 0
}
prev = val;
});
};
Now this should be relatively simple, the use of prev might be a slight head scratcher but shouldn't be a major roadblock for ya.
The real problem is why the problem set n to be huge.
Because it's clear that from the question description there is really no way around the n*(num of cells) time complexity, so there have to be some way of reducing this madness dramatically.
This really took some intuition, the first thing that came into my mind is that there must be something that could be memoized.
The reasoning for this is that it's just 0 and 1 change with only 8 cells via a relatively strict mutation rule. Therefore there must be some limitation to how many times these 8 cells can change.
[it is...mathematically speaking 2^8, but even less because of the mutation rule ... but I didn't think of this when I was solving this]
so I built my memo solution first:
let prev, next
let key = '';
const map = {};
while (n--) {
prev = null;
key = cells.join('');
if(map[key]) { cells=map[key] };
cells.forEach(function(val, index){
next = cells[index+1];
if (prev === next) {
cells[index] = 1
} else {
cells[index] = 0
}
prev = val;
});
map[key] = cells.slice();
};
I think this is simple, I literally just memoized the change by using the current cells as key and the changed after as the value.
However, this was still not good enough. I didn't know why at first.
upon thinking about it, I realized that for n to be THAT large and solvable and memoization to still not be enough, it must means that there is at least one other thing that could happen.
the first thing that came into my mind that for n = 100000000, there must not be 100000000 different solutions; memoization already improved somewhat, just not enough.
I thought that there could be a lot...maybe like 100 different solutions at best? just because the restriction of the question. So MAYBE it is possible to have a loop in the chain of changes in the map.
I do not know where does the cycle starts or end, but if a cycle does exist, then it would make a lot of sense for n to be that big of number. This is because once the cells mutates into a cycle, it just stays in the cycle, so we can just do n % cycleLength and just iterate a bit more to find out what's the final mutation looking like.
Below is the full code:
var prisonAfterNDays = function(cells, n) {
let prev, next
let key = '';
const map = {};
while (n--) {
prev = null;
key = cells.join('');
if(map[key]) { break; };
cells.forEach(function(val, index){
next = cells[index+1];
if (prev === next) {
cells[index] = 1
} else {
cells[index] = 0
}
prev = val;
});
map[key] = cells.slice();
};
if(n < 0) { return cells }
const startCycleKey = cells.join('');
cells = map[startCycleKey];
let counter = 1;
let found = false;
while(n > 0) {
key = cells.join('');
if(key === startCycleKey && !found) {
found = true;
n = n % counter;
continue
}
counter++
cells = map[key];
n--;
}
return cells;
};
You'll notice that I changed the first part a bit:
1.) it breaks out after we find a loop, because we want to get to phase 2 of the solution instead
2.) if n is already 0 we want to return the cells already. There is probably a better way to code it so that it works nice with phase 2, but I am burnt out of this question already.
For phase 2:
1.) we need to find out the length of the cycle
2.) once we have the length we n % cycleLength
3.) then continue the iteration until n === 0.
note at this point since we are in the cycle, we just need to use the map to get the cells mutation instead of calculating it.
to achieve phase 2 we need to:
1.) remember the startCycleKey
2.) put cells into the next point in the cycle so that in the iteration it won't immediately terminate when we check the currentKey vs the startCycleKey
3.) start the counter at 1.
4.) iterate through the map as normally until we hit startCycleKey again and can finally n % counter.
I definitely did not get this code out in a timely manner. There are probably a couple of places where it can be simpler but hey, it is in logical steps and I can justify every step of it without having to write some kind of weird math proof for it.
Apparently the math trick about this is that the length of the cycle is always 14. In fact the cycle is the whole map itself. I don't think you can adequately justify either without basically saying you have seen this problem beforehand, nor I'd expect any interviewer to expect you to do so.
Let me know anything on your mind after reading through this, THANKS!
Top comments (0)