Frog Jump – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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.
Example 1:
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.
Example 2:
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.
Constraints:
2 <= stones.length <= 20000 <= stones[i] <= 231 - 1stones[0] == 0stonesis sorted in a strictly increasing order.
C++ Frog Jump LeetCode Solution
class Solution {
public:
bool canCross(vector<int>& stones) {
unordered_map<int , unordered_set<int>> hashMap; // Initializing required hashmap.
hashMap[stones[0] + 1] = {1}; // Viable Jump Sizes to reach 2nd stone.
for(int i = 1 ; i < stones.size() ; ++i){ // Traversing all positions
int position = stones[i]; // Current Position
for(auto it : hashMap[position]){ // Traversing all viable jump sizes that can be used from current position.
hashMap[position + it].insert(it); // Populating the sets of positions that can be reached from current position with a viable jump size.
hashMap[position + it + 1].insert(it + 1);
hashMap[position + it - 1].insert(it - 1);
}
}
return hashMap[stones.back()].size() != 0; // Checking the set size of last stone.
}
};
Java Frog Jump LeetCode Solution
public boolean canCross(int[] stones) {
if (stones.length == 0) {
return true;
}
HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>(stones.length);
map.put(0, new HashSet<Integer>());
map.get(0).add(1);
for (int i = 1; i < stones.length; i++) {
map.put(stones[i], new HashSet<Integer>() );
}
for (int i = 0; i < stones.length - 1; i++) {
int stone = stones[i];
for (int step : map.get(stone)) {
int reach = step + stone;
if (reach == stones[stones.length - 1]) {
return true;
}
HashSet<Integer> set = map.get(reach);
if (set != null) {
set.add(step);
if (step - 1 > 0) set.add(step - 1);
set.add(step + 1);
}
}
}
return false;
}
Python 3 Frog Jump LeetCode Solution
class Solution(object):
def canCross(self, stones):
self.memo = set()
target = stones[-1]
stones = set(stones)
res = self.bt(stones, 1, 1, target)
return res
def bt(self, stones, cur, speed, target):
# check memo
if (cur, speed) in self.memo:
return False
if cur==target:
return True
if cur>target or cur<0 or speed<=0 or cur not in stones:
return False
# dfs
candidate = [speed-1, speed, speed+1]
for c in candidate:
if (cur + c) in stones:
if self.bt(stones, cur+c, c, target):
return True
self.memo.add((cur,speed))
return False
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
