45. Jump Game II

Partho Biswas · Partho Biswas · commit 1959365ec8e8 · 2019-11-10T02:40:37.000+06:00
diff --git a/README.md b/README.md
@@ -280,7 +280,8 @@ I have solved quite a number of problems from several topics. See the below tabl
 |04| [406. Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/)| [Python](leetcode.com/python/406_Queue_Reconstruction_by_Height.py)| [Article 1](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC%2B%2BJava-Solution), [Article 2](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89359/Explanation-of-the-neat-Sort%2BInsert-solution) | Medium | 📌 Fundamentals |
 |05| [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/)| [Python](leetcode.com/python/621_Task_Scheduler.py)| [Ex 1](https://leetcode.com/problems/task-scheduler/discuss/190390/Can-anyone-explain-to-me-what-the-problem-is-asking), [Ex 2](https://leetcode.com/problems/task-scheduler/discuss/130786/Python-solution-with-detailed-explanation), [Vid 1](https://www.youtube.com/watch?v=hVhOeaONg1Y) | Medium | 📌 Extremely tricky. Not done. Check later |
 |06| [392. Is Subsequence](https://leetcode.com/problems/is-subsequence/)| [Python](leetcode.com/python/392_Is_Subsequence.py)| [Ex 1](https://leetcode.com/problems/is-subsequence/discuss/87264/Easy-to-understand-binary-search-solution), [Ex 3](https://leetcode.com/problems/is-subsequence/discuss/87302/Binary-search-solution-for-follow-up-with-detailed-comments/144323) | Easy | 📌  |
-|07| *[55. Jump Game](https://leetcode.com/problems/jump-game/)* | [Python](leetcode.com/python/55_Jump_Game.py)| *[Official](https://leetcode.com/articles/jump-game/)* | Medium | 📌 *Must Check. Learned a lot* |
+|07| **[55. Jump Game](https://leetcode.com/problems/jump-game/)** | [Python](leetcode.com/python/55_Jump_Game.py)| **[Official](https://leetcode.com/articles/jump-game/)** , [Art 1](https://tinyurl.com/yy9vyjyn)| Medium | 📌 **Must Check. Learned a lot** |
+|08| [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)| [Python](leetcode.com/python/45_Jump_Game_II.py)| [Vid  1](https://www.youtube.com/watch?v=cETfFsSTGJI), [Vid 2](https://www.youtube.com/watch?v=jH_5ypQggWg), [Vid 3](https://www.youtube.com/watch?v=vBdo7wtwlXs), [Art 1](https://tinyurl.com/yalsno6r) | Hard | 📌  |
 
 
 ### [Dynamic Programming](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews)
diff --git a/leetcode.com/python/45_Jump_Game_II.py b/leetcode.com/python/45_Jump_Game_II.py
@@ -0,0 +1,23 @@
+class Solution(object):
+
+    # Greedy Approach. BFS to be precise.
+    def jump(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        jumps, currentEnd, currentFarthest = 0, 0, 0
+        for i in range(len(nums) - 1):
+            currentFarthest = max(currentFarthest, i + nums[i])
+            if i == currentEnd:
+                jumps += 1
+                currentEnd = currentFarthest
+        return jumps
+
+
+
+
+sol = Solution()
+input = [2,3,1,1,4]
+output = sol.jump(input)
+print("Res: ", output)
