Frog Jump

                                            
class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> dp;
        for (int stone : stones) {
            dp[stone] = unordered_set<int>();
        }
        
        dp[0].insert(0);
        
        for (int i = 0; i < stones.size(); ++i) {
            for (int k : dp[stones[i]]) {
                for (int step = k - 1; step <= k + 1; ++step) {
                    if (step > 0 && dp.find(stones[i] + step) != dp.end()) {
                        dp[stones[i] + step].insert(step);
                    }
                }
            }
        }
        
        return !dp[stones.back()].empty();
    }
};

                                            
class Solution {
    public boolean canCross(int[] stones) {
        if (stones.length < 2 || stones[1] != 1) {
            return false;
        }
        
        int n = stones.length;
        
        // Create a HashSet to store all the stones for quicker access
        Set<Integer> stoneSet = new HashSet<>();
        for (int stone : stones) {
            stoneSet.add(stone);
        }
        
        // Create a HashMap to store the possible jumps for each stone
        Map<Integer, Set<Integer>> dp = new HashMap<>();
        dp.put(0, new HashSet<>());
        dp.get(0).add(1);
        
        for (int i = 1; i < n; i++) {
            dp.put(stones[i], new HashSet<>());
        }
        
        for (int i = 0; i < n - 1; i++) {
            int stone = stones[i];
            for (int jump : dp.get(stone)) {
                int nextPos = stone + jump;
                if (nextPos == stones[n - 1]) {
                    return true;
                }
                
                if (stoneSet.contains(nextPos)) {
                    if (jump - 1 > 0) dp.get(nextPos).add(jump - 1);
                    dp.get(nextPos).add(jump);
                    dp.get(nextPos).add(jump + 1);
                }
            }
        }
        
        return false;
    }
}

                                            
class Solution(object):
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        if not stones:
            return False
        
        dp = {}
        
        for stone in stones:
            dp[stone] = set()
        
        dp[0].add(0)
        
        for stone in stones:
            for step in dp[stone]:
                for move in range(step-1, step+2):
                    if move > 0 and stone + move in dp:
                        dp[stone + move].add(move)
        
        return len(dp[stones[-1]]) > 0

                                            
public class Solution {
    public bool CanCross(int[] stones) {
        // Create a HashSet to store all the stones
        HashSet<int> stoneSet = new HashSet<int>();
        foreach (int stone in stones) {
            stoneSet.Add(stone);
        }
        
        // Create a dictionary to store each stone and the jumps that can reach it
        Dictionary<int, HashSet<int>> dp = new Dictionary<int, HashSet<int>>();
        dp[0] = new HashSet<int>();
        dp[0].Add(0);
        
        // Iterate through each stone and check if it is reachable from any previous stone
        for (int i = 0; i < stones.Length; i++) {
            int stone = stones[i];
            if (!dp.ContainsKey(stone)) continue;
            
            HashSet<int> jumps = dp[stone];
            
            foreach (int jump in jumps) {
                for (int k = jump - 1; k <= jump + 1; k++) {
                    if (k <= 0) continue;
                    int nextStone = stone + k;
                    if (nextStone == stones[stones.Length - 1]) return true;
                    if (stoneSet.Contains(nextStone)) {
                        if (!dp.ContainsKey(nextStone)) {
                            dp[nextStone] = new HashSet<int>();
                        }
                        dp[nextStone].Add(k);
                    }
                }
            }
        }
        
        return false;
    }
}

                                            
/**
 * @param {number[]} stones
 * @return {boolean}
 */
const canCross = (stones) => {
    const dp = Array(stones.length).fill().map(() => Array(stones.length).fill(false));
    dp[0][0] = true;
    
    for (let i = 1; i < stones.length; i++) {
        for (let j = i - 1; j >= 0; j--) {
            const jump = stones[i] - stones[j];
            if (jump > j + 1) break;
            
            if (jump <= i) {
                dp[i][jump] = dp[j][jump - 1] || dp[j][jump] || dp[j][jump + 1]; 
                if (i === stones.length - 1 && dp[i][jump]) return true;
            }
        }
    }
    
    return false;
};

                                            
function canCross(stones: number[]): boolean {
    const dp: Set<number>[] = stones.map(() => new Set());
    dp[0].add(0);

    for (let i = 0; i < stones.length; i++) {
        for (const k of dp[i]) {
            for (let j = i + 1; j < stones.length; j++) {
                const gap = stones[j] - stones[i];
                if (gap >= k - 1 && gap <= k + 1) {
                    dp[j].add(gap);
                }
            }
        }
    }

    return dp[stones.length - 1].size > 0;
};

                                            
class Solution {
    /**
     * @param Integer[] $stones
     * @return Boolean
     */
    function canCross($stones) {
        $n = count($stones);
        $dp = array_fill(0, $n, array());
        $dp[0][0] = true;

        for ($i = 1; $i < $n; $i++) {
            for ($j = $i - 1; $j >= 0; $j--) {
                $diff = $stones[$i] - $stones[$j];
                if ($diff > $j + 1) break;
                if (isset($dp[$j][$diff]) || isset($dp[$j][$diff - 1]) || isset($dp[$j][$diff + 1])) {
                    $dp[$i][$diff] = true;
                    if ($i == $n - 1) return true;
                }
            }
        }

        return false;
    }
}

                                            
class Solution {
    func canCross(_ stones: [Int]) -> Bool {
        var dp = [Int: Set<Int>]()
        
        for stone in stones {
            dp[stone] = Set<Int>()
        }
        dp[0]!.insert(0)
        
        for i in 0..<stones.count {
            let stone = stones[i]
            for k in dp[stone]! {
                for step in -1...1 {
                    if step + k > 0, let next = dp[stone + step + k] {
                        dp[stone + step + k]!.insert(step + k)
                    }
                }
            }
        }
        
        return !dp[stones.last!]!.isEmpty
    }
}

                                            
class Solution {
    fun canCross(stones: IntArray): Boolean {
        val map = HashMap<Int, HashSet<Int>>()
        for (stone in stones) {
            map[stone] = HashSet()
        }
        
        map[0]!!.add(0)
        
        for (i in stones.indices) {
            val positions = map[stones[i]]!!
            for (k in positions) {
                for (step in -1..1) {
                    if (step + k > 0 && map.containsKey(stones[i] + step + k)) {
                        map[stones[i] + step + k]!!.add(step + k)
                    }
                }
            }
        }
        
        return map[stones.last()]!!.isNotEmpty()
    }
}

                                            
class Solution {
  bool canCross(List<int> stones) {
    // Check if the stones list is empty or has a stone at the second position
    if (stones.isEmpty || stones[1] != 1) {
      return false;
    }
    
    // Create a set to store all stones positions for faster lookup
    Set<int> stoneSet = stones.toSet();
    
    // Use a recursive helper function to simulate frog jumps
    return canCrossHelper(stoneSet, 1, 1, stones.last);
  }
  
  bool canCrossHelper(Set<int> stoneSet, int position, int jumpSize, int target) {
    // Check if the landing position is the target stone
    if (position == target) {
      return true;
    }
    
    // Loop through the possible next jump sizes
    for (int nextJump = jumpSize - 1; nextJump <= jumpSize + 1; nextJump++) {
      if (nextJump > 0 && stoneSet.contains(position + nextJump)) {
        // Recursively check if the frog can reach the target stone from the next position
        if (canCrossHelper(stoneSet, position + nextJump, nextJump, target)) {
          return true;
        }
      }
    }
    
    return false;
  }
}

                                            
func canCross(stones []int) bool {
    n := len(stones)
    dp := make([]map[int]bool, n)
    for i := range dp {
        dp[i] = make(map[int]bool)
    }

    dp[0][0] = true

    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            k := stones[i] - stones[j]
            if k <= i {
                if dp[j][k-1] || dp[j][k] || dp[j][k+1] {
                    dp[i][k] = true
                }
            }
        }
    }

    return len(dp[n-1]) > 0
}

                                            
# @param {Integer[]} stones
# @return {Boolean}
def can_cross(stones)
    dp = Hash.new { |h, k| h[k] = Hash.new(false) }
    dp[0][0] = true
    (1...stones.length).each do |i|
        (0...i).each do |j|
            dist = stones[i] - stones[j]
            dp[i][dist] = dp[j][dist - 1] || dp[j][dist] || dp[j][dist + 1]
        end
    end
    !dp[stones.length - 1].select { |k, v| v }.empty?
end

                                            
object Solution {
    def canCross(stones: Array[Int]): Boolean = {
        val map = collection.mutable.HashMap[Int, collection.mutable.HashSet[Int]]()
        stones.foreach(map(_) = collection.mutable.HashSet[Int]())
        map(0).add(0)

        stones.foreach { stone =>
            map(stone).foreach { step =>
                for (s <- step - 1 to step + 1 if s > 0 && map.contains(stone + s))
                    map(stone + s).add(s)
            }
        }

        map(stones.last).nonEmpty
    }
}

To solve this coding challenge, you'll need to determine if a frog can cross a river by jumping on stones. The stones are positioned at specific units in a sorted array, and the frog must start at the first stone. Each jump can be of length

k - 1

k

, or

k + 1

, where

k

is the length of the last jump the frog made. Here's a detailed approach to tackling the problem:

Explanation

Understanding the Problem:

You are given a list of stone positions in a strictly increasing order.
The frog starts at the first stone (position 0) and aims to reach the last stone in the list.
The frog's jump length must be one of three values: the length of the last jump minus one, the same as the last jump, or the last jump plus one.
The frog can only jump forward.

Constraints and Conditions:

The initial list of stones will have at least 2 elements and no more than 2000 elements.
The positions of the stones are non-negative integers and fit within a 32-bit signed integer range.
The frog must land exactly on the stones, not in between them.

Approach:

Use dynamic programming to keep track of all possible jump lengths the frog can make for each stone position.
Utilize a dictionary where the key is the stone position and the value is a set of jump lengths that reach that stone.
Start by initializing a dictionary where each stone maps to an empty set.
The frog starts at the first stone with a jump length of 0.
Iterate through each stone, and for every possible jump length that can reach that stone, check the next possible positions (stone + k - 1, stone + k, stone + k + 1) and add those jump lengths to the respective stones if they exist in the list.
Finally, check if there are any possible jump lengths that land on the last stone.

Pseudocode:

                                            
# Initialize a solution class with a method to solve the problem
class Solution
# Function to determine if the frog can cross the river
function canCross(stone_positions_list):
# If the list is empty, return False
if stone_positions_list is empty:
return False

# Initialize a dictionary to map each stone position to a set of possible jump lengths
stone_to_jumps_map = dictionary
for each stone_position in stone_positions_list:
stone_to_jumps_map[stone_position] = empty set

# The initial stone (position 0) is reachable with a jump length of 0
stone_to_jumps_map[0] add 0

# Iterate through each stone in the stones list
for each stone_position in stone_positions_list:
# Iterate through each possible jump length to reach this stone
for each jump_length in stone_to_jumps_map[stone_position]:
# Consider the possible next jump lengths: k - 1, k, and k + 1
for next_jump_length in range(jump_length - 1 to jump_length + 1):
# Ensure the next jump length is positive and the next stone position exists in the stones list
if next_jump_length > 0 and (stone_position + next_jump_length) is in stone_to_jumps_map:
# Add the next jump length to the set of jump lengths for the next stone position
stone_to_jumps_map[stone_position + next_jump_length] add next_jump_length

# The frog can cross the river if there are any possible jump lengths to reach the last stone
return length of stone_to_jumps_map[last stone_position] > 0

Step-by-Step Explanation/Detailed Steps in Pseudocode

Class Initialization:

Create a class
Solution

that contains our main function
canCross

.

Function Initialization:

The function
canCross

takes an input parameter
stone_positions_list

which is a list of integers representing the stone positions.

Empty Check:

Check if the
stone_positions_list

is empty. If yes, return
False

because the frog can't jump anywhere.

Dictionary Initialization:

Initialize a dictionary called
stone_to_jumps_map

where each stone is mapped to an empty set. This set will keep track of the possible jump lengths that can reach that stone.

Start Position:

Set the first stone's position (position 0) and initialize it with a jump length of 0.

Iterate Through Stones:

Loop over each stone in
stone_positions_list

.
For each stone, loop through all possible jump lengths stored in the set corresponding to that stone.

Calculate Next Positions:

For each possible jump length (k - 1, k, k + 1), calculate the next stone position (current position + next jump length).
If the next jump length is positive (i.e., greater than 0) and the next stone position exists in the dictionary, add it to the set for that next stone position.

Final Check:

Check if the set of possible jump lengths for the last stone contains any elements. If yes, the frog can reach the last stone, so return
True

. Otherwise, return
False

.

By breaking the problem down in this manner, we can use dynamic programming to efficiently track all possible jump sequences. This ensures we cover all scenarios and make the correct determination if the frog can reach the end.