Don’t look back, go forward?

1871. Jump Game VII

This is the third problem of LC weekly contest (May 22, 2021). If we look forward, for each 0, we have a region which are reachable, we have to update that region. This process will make the algorithm have the complexity of O(n²), hence it will get TLE.

   L              R
0000000010000001000000

Reference Code

class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
const int n = s.size();
vector<bool> reachable(n+1, false);
vector<int> prefixsum(n+1, 0);
reachable[1] = true;
prefixsum[1] = 1;
// use 1 based index
for (int i = 1; i <=n; ++i)
{
if (s[i-1] == '1')
{
prefixsum[i] = prefixsum[i-1];
continue;
}
// look back to see whether we have any reachable points in the region [l, r], if so, the point i can be reachable.
// See if any points reachable in [l, r], we can check the prefix sum. If we have any true in [l, R], the region sum
// should be greater than 0.
int l = i - maxJump, r = i - minJump;
// if r is less than 1, it means this zero is unreachable.
if (r >= 1) {
l = max(1, l);
reachable[i] = prefixsum[r] - prefixsum[l-1] > 0;
}
prefixsum[i] = prefixsum[i-1] + reachable[i];
}
return reachable[n];
}
};

Reference

[1]https://youtu.be/1UjN4cXyL34

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store