# 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

--

--

## More from Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.