README.md

Frog Jump

A frog is trying to cross a river by jumping on stones placed at various positions along the river. The river is divided into units, and some units contain stones while others do not. The frog can only land on a stone, but it must not jump into the water.

You are given an array, stones, that represents the positions of the stones in ascending order (in units). The frog starts on the first stone, and its first jump must be exactly 1 unit.

If the frog’s last jump was of length k units, its next jump must be either k−1, k, or k+1 units. The frog can only move forward.

Your task is to determine whether the frog can successfully reach the last stone.

Constraints

• 2 ≤ stones.length ≤ 1000
• 0 ≤ stones[i] ≤ 2^20 − 1
• stones[0] == 0
• The stones array is sorted in a strictly increasing order.

Topics

• Array
• Dynamic Programming

Solution

The solution’s essence lies in leveraging dynamic programming to track all the jump lengths that can reach each stone. The frog begins on the first stone with a jump length of zero, and from every reachable stone, it tries jumps of the same size, one unit longer, or one unit shorter. Each valid move updates the DP table to record new reachable states. The algorithm stores each stone’s position along with its index in a map, allowing for quick checks to determine if a stone exists at a given position. Finally, if any jump length reaches the last stone, the frog can successfully cross the river.

Using the intuition above, we implement the algorithm as follows:

• Store the number of stones in a variable n.
• Create an unordered map, mapper, to store each stone’s position as the key and its index as the value for fast lookups.
• Populate the mapper by mapping every stone position, stones[i], to its index, i.
• Initialize a 2D array, dp, of size 1001 x 1001 with zeros to track reachable states.

  Note that this is highly dependable on the constraints, larger sizes of stones will cause an Index out of bounds error. So, ensure to initialize the size correctly

• Set dp[0][0] to 1 to indicate that the frog starts on the first stone with a previous jump of 0.
• Iterate over each stone index i:
  • For each stone, iterate over all possible previous jump lengths prevJump.
  • Check if dp[i][prevJump] is 1 to confirm that the frog can reach stone i with jump size prevJump:
    • If reachable, store the current position as currPos = stones[i].
    • Check if a stone exists at currPos + prevJump; if yes, mark dp[mapper[currPos + prevJump]][prevJump] as 1.
    • Check if a stone exists at currPos + prevJump + 1; if yes, mark dp[mapper[currPos + prevJump + 1]][prevJump + 1] as 1
    • If prevJump > 1 and a stone exists at currPos + prevJump - 1, mark dp[mapper[currPos + prevJump - 1]][prevJump - 1] as 1.
• After filling the DP table, iterate over all possible jump sizes jump for the last stone.
  • If any dp[n - 1][jump] equals 1, return TRUE to indicate that the frog can cross the river.
• If no valid jump leads to the last stone, return FALSE.

Time Complexity

The algorithm’s time complexity is O(n^2), where n is the number of stones. For each stone, it may check all possible previous jump lengths, and for each valid state, it performs constant-time lookups in the map.

Space Complexity

The algorithm’s space complexity is O(n) occupied by the mapper map.