LeetCode 403 : Frog Jump (HARD….NOT MUCH)

Question :

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog’s last jump was k units, then its next jump must be either k — 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Constraints :

2≤Number of Stones<1100

Each Stone’s position will be a non negative value < 2³¹

1st stone’s position is always 0.

Example :

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Approach :

The problem can be solved by coding a simple recurrence relation.

Suppose we are at position ‘pos’ with last jump ‘k’, so the next jump could be of size k-1, k or k+1 and the landing positions could be pos+k-1, pos+k or pos+k+1 respectively.

So the recurrence relation is

dp[pos][k] = dp[pos+k][k]||dp[pos+k-1][k-1]||dp[pos+k+1][k+1]

Since pos’s value can be very large, we can use map instead of 2D array as dp where key will be {pos,k} and T/F will be value, i.e dp[{pos,k}] = True/False. True if pos = last position of stone, or there exists a way from position pos with previous jump of size k to reach the last stone.

Code :

class Solution {
public:
   map<int, bool> stone;
   int lastPos;
   map<pair<int, int>, bool> dp;
   bool solve(int pos, int k) {
      if (pos == lastPos)
         return true;
      if (k <= 0 || pos > lastPos)
         return false;
      if (dp.find({pos, k}) != dp.end())
         return dp[{pos, k}];
      if (stone[pos] == 1)
         return dp[{pos, k}] = solve(pos + k, k) || 
                               solve(pos + k - 1, k - 1) ||
                               solve(pos + k + 1, k + 1);
      return dp[{pos, k}] = false;
   }
   bool canCross(vector<int>& stones) {
      lastPos = stones.back();
      for (int x : stones)
         stone[x] = 1;
      if (stones[1] == 1)
         return solve(1, 1);
      return false;
   }
};

Code Explanation :

The map named ‘stone’ is used to store is at position p there is a stone or not. The variable lastPos stores the position of the last stone where we need to reach.

map<int, bool> stone;
int lastPos;

If we reach the position of the last stone i.e if pos == lastPos, then we return true.

if (pos == lastPos)
         return true;

If we reach at position > lastPos or if JumpSize ≤ 0 we return false.

if (k <= 0 || pos > lastPos)
         return false;

If there is a stone at position ‘pos’ then we check all the three jumps of length k-1, k and k+1 with the recursive calls shown in the code below. If any of the calls return true then dp[{pos,k}] becomes true which says that we can reach the last stone from the stone at position pos with previous jump of size k.

if (stone[pos] == 1)
         return dp[{pos, k}] = solve(pos + k, k) || 
                               solve(pos + k - 1, k - 1) ||
                               solve(pos + k + 1, k + 1);

As the first stone is always 0 and 1st jump is always of length 1, so the second stone should be at position 0+1 = 1 and this position is reached by jump of length 1 at previous step. Hence we call solve function with 1,1 as arguments.

lastPos = stones.back();
for (int x : stones)
   stone[x] = 1;
if (stones[1] == 1)
   return solve(1, 1);
return false;

This is my first blog ever. Will be surely improving with the coming blogs. Till then Keep Coding!!