Frog Jump

class Solution {
public:
    unordered_map<int, int> stonePosition;
    int memoization[2001][2001];

    bool canReach(vector<int>& stones) {
        int stoneCount = stones.size();
        // Updating positions of stones in the map
        for (int i = 0; i < stoneCount; i++) {
            stonePosition[stones[i]] = i;
        }
        
        memoization[0][0] = 1;
        for (int idx = 0; idx < stoneCount; idx++) {
            for (int lastJump = 0; lastJump <= stoneCount; lastJump++) {
                if (memoization[idx][lastJump]) {
                    int nextPosition = stones[idx] + lastJump;
                    if (stonePosition.count(nextPosition)) {
                        memoization[stonePosition[nextPosition]][lastJump] = 1;
                    }
                    nextPosition = stones[idx] + lastJump + 1;
                    if (stonePosition.count(nextPosition)) {
                        memoization[stonePosition[nextPosition]][lastJump + 1] = 1;
                    }
                    nextPosition = stones[idx] + lastJump - 1;
                    if (stonePosition.count(nextPosition) && lastJump > 1) {
                        memoization[stonePosition[nextPosition]][lastJump - 1] = 1;
                    }
                }
            }
        }
        
        // Check if reaching the last stone is possible
        for (int lastJump = 0; lastJump <= stoneCount; lastJump++) {
            if (memoization[stoneCount - 1][lastJump]) {
                return true;
            }
        }
        return false;
    }
};

The given problem, known as "Frog Jump," deals with determining whether a frog can jump across various stones positioned at specific points until it reaches the last stone. Implementing this solution in C++, the code utilizes a combination of memoization and hashing (unordered_map) to solve the problem efficiently.

Start by mapping each stone's position to its index with an unordered map, stonePosition. This mapping helps in constant-time look-up for determining if a stone exists at a given position. Next, initialize a 2D array memoization to keep track of reachable positions and jumps.

The main logic involves iterating over each stone and checking if it is possible to jump from the current stone to the next one using last jump's length -1, +0, or +1. If such a jump lands on another stone, that jump is recorded as feasible in the memoization array.

The solution checks all possible jump lengths from each stone and marks them in the 2D memoization array indicating a valid jump from one stone to another.

Finally, to determine if reaching the final stone is possible, iterate through the memoization entries for the last stone. If any entry reveals a feasible jump reaching this stone, then it is possible for the frog to reach the end; otherwise, it isn't.

This method leverages dynamic programming to reduce the complexity of checking every possible sequence of jumps, making it more efficient than a naive approach.

class Solution {
    HashMap<Integer,Integer> stoneIndexMap = new HashMap<>();
    boolean pathMatrix[][] = new boolean[2001][2001];

    public boolean canCross(int[] stones) {
        int stoneCount = stones.length;
        for (int i = 0 ; i < stoneCount; i++) {
            stoneIndexMap.put(stones[i], i);
        }

        pathMatrix[0][0] = true;
        for (int index = 0; index < stoneCount; index++) {
            for (int jump = 0; jump <= stoneCount; jump++) {
                if (pathMatrix[index][jump]) {
                    if (stoneIndexMap.containsKey(stones[index] + jump)) {
                        pathMatrix[stoneIndexMap.get(stones[index] + jump)][jump] = true;
                    }
                    if (stoneIndexMap.containsKey(stones[index] + jump + 1)) {
                        pathMatrix[stoneIndexMap.get(stones[index] + jump + 1)][jump + 1] = true;
                    }
                    if (stoneIndexMap.containsKey(stones[index] + jump - 1)) {
                        pathMatrix[stoneIndexMap.get(stones[index] + jump - 1)][jump - 1] = true;
                    }
                }
            }
        }

        for (int i = 0; i <= stoneCount; i++) {
            if (pathMatrix[stoneCount - 1][i]) {
                return true;
            }
        }
        return false;
    }
}

The "Frog Jump" problem involves determining if a frog can hop from the start of an array of stone positions to the end by adhering to specific jumping rules. The solution is implemented in Java, utilizing a dynamic programming approach represented through a 2D boolean matrix (pathMatrix) and a hash map (stoneIndexMap) for quick index referencing of stone positions.

• stoneIndexMap maps each stone's position to its index in the array, enabling quick look-up.
• pathMatrix helps track possible positions and jumps. If pathMatrix[index][jump] is true, it indicates that the frog can be on the stone at index with a last jump of jump units.

Key steps in the solution:

1. Initialize stoneIndexMap with the stone positions and corresponding indices.
2. Set pathMatrix[0][0] to true, indicating starting at the first stone without any jump.
3. Iterate through each stone position. For each possible jump length:
   1. If the pathMatrix for the current stone and jump is true, check:
      • The consecutive stone positions (jump, jump+1, and jump-1 units away). Update the corresponding pathMatrix values to true if those stones exist.
4. Conclude by verifying the last row of the pathMatrix. If any position is true, return true, signifying that the frog can reach the final stone.

This solution leverages memoization to avoid redundant calculations and ensures efficient look-up for possible jumps by using a hash map. The solution dynamically builds up possibilities of reaching each stone with specific jumps, making it efficient for larger stone arrays. Return false if the end of the matrix is reached and no true entry is found in the last row, indicating the frog cannot reach the last stone.