DAY 85 - Frog Jump

Hey Guys! Nayan this side and we are on day 85 of our 100 Days Code Challenge. Today we are going to solve daily problem of leetcode.

---

Question: 403. Frog Jump

A frog is crossing a river. The river is divided into some number of 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 can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

---

Examples:

Example 1:

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Example 2:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: 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.

---

Intuition and Algorithm:

Here we are presented with multiple choices, which means one of the ways to find out the answer is go through the all the cases and find out if we can get our answer.

Why DP?: Well it's obvious because of 2 things:

• Repeating Cases: If we draw out a map of our jumps that we can do we will see a lot of repeating cases.
• Recursive Approach to go through all cases.

We use dynamic programming and utilize an unordered map to keep track of possible jump sizes for each stone. Here's a breakdown of the key components and the steps taken for the solution:

Initialization: We start by creating an unordered map named mp, where the keys represent the stone positions, and the values are unordered sets containing the possible jump sizes from that stone. This maintains the jumps we can do so that we can check our final answer is maintained.

Initially, the first stone's position (1) is added to the map with a possible jump size of 1.

Iteration: we iterate through the stones array starting from the second stone. For each stone, we iterate through the possible jump sizes stored in mp[stones[i]] basically traversing all the jumps from that respective stone.

Updating JumpSizes: For each stone and each valid jump size, we update the possibilities for the next stones. We have a total of three possibilities to the next stone: the current jump size, one less than the jump size, and one more than the jump size. We add these possibilities are added to the mp map.

Checking Final Stone: After iterating through all stones, we check whether the last stone's position has any valid jump sizes in the mp map. If there are valid jump sizes, it indicates that it's possible to reach the last stone, we can return true. Otherwise, it returns false.

Code:

bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> mp;
        mp[1] = {1};

        for(int i = 1; i < stones.size(); i++){
            for(auto jumpSize : mp[stones[i]]){
                mp[stones[i] + jumpSize].insert(jumpSize);
                mp[stones[i]+ jumpSize-1].insert(jumpSize-1);
                mp[stones[i]+ jumpSize+1].insert(jumpSize+1);
            }
        }

        return mp[stones.back()].size() != 0;
    }

---

Complexity Analysis:

Complexity	Analysis
Time	O(n^2)
Space	O(n^2)