55. Jump Game

Partho Biswas · Partho Biswas · commit e828d9f2ca21 · 2019-11-09T23:28:11.000+06:00
diff --git a/README.md b/README.md
@@ -280,7 +280,7 @@ 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)| ```diff + [Text test]() ``` | Medium | 📌  |
+|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* |
 
 
 ### [Dynamic Programming](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews)
diff --git a/leetcode.com/python/55_Jump_Game.py b/leetcode.com/python/55_Jump_Game.py
@@ -0,0 +1,77 @@
+class Solution(object):
+
+    # # Backtracking Approach - TLE
+    # def canJump(self, nums):
+    #     """
+    #     :type nums: List[int]
+    #     :rtype: bool
+    #     """
+    #     return self.canJumpHelper(nums, 0)
+    #
+    # def canJumpHelper(self, nums, currentIdx):
+    #     if currentIdx == len(nums) - 1:
+    #         return True
+    #     nextMaxJumpIdx = min(currentIdx + nums[currentIdx], len(nums) - 1)
+    #     for i in range(nextMaxJumpIdx, currentIdx,
+    #                    -1):  # Python for loop decrementing index >> https://stackoverflow.com/questions/28650128/python-for-loop-decrementing-index/28650284
+    #         if self.canJumpHelper(nums, i):
+    #             return True
+    #     return False
+    #
+    # # DP top-down with memoization Approach - TLE
+    # def canJump(self, nums):
+    #     """
+    #     :type nums: List[int]
+    #     :rtype: bool
+    #     """
+    #     memo = [0] * len(nums)
+    #     memo[-1] = True  # Here True means reachable and True means not rechable
+    #     return self.canJumpHelper(nums, 0, memo)
+    #
+    # def canJumpHelper(self, nums, currentIdx, memo):
+    #     if memo[currentIdx] != 0:
+    #         return memo[currentIdx]
+    #     nextMaxJumpIdx = min(currentIdx + nums[currentIdx], len(nums) - 1)
+    #     for i in range(nextMaxJumpIdx, currentIdx, -1):
+    #         if self.canJumpHelper(nums, i, memo):
+    #             memo[currentIdx] = True
+    #             return True
+    #     memo[currentIdx] = False
+    #     return False
+    #
+    # # DP bottom-up with memoization Approach - TLE
+    # def canJump(self, nums):
+    #     """
+    #     :type nums: List[int]
+    #     :rtype: bool
+    #     """
+    #     memo = [0] * len(nums)
+    #     memo[-1] = True  # Here True means reachable and True means not rechable
+    #     for i in range(len(nums) - 1, -1, -1):
+    #         nextMaxJumpIdx = min(i + nums[i], len(nums) - 1)
+    #         for j in range(i + 1, nextMaxJumpIdx + 1):
+    #             if memo[j] is True:
+    #                 memo[i] = True
+    #                 break
+    #     return True if memo[0] == True else False
+
+    # Greedy
+    def canJump(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: bool
+        """
+        lastPosition = len(nums) - 1
+        for i in range(len(nums) - 1, -1, -1):
+            nextMaxJump = i + nums[i]
+            if nextMaxJump >= lastPosition:
+                lastPosition = i
+        return True if lastPosition == 0 else False
+
+
+sol = Solution()
+# input = [2,3,0,1,4]
+input = [3,2,1,0,4]
+# input = [2,0,6,9,8,4,5,0,8,9,1,2,9,6,8,8,0,6,3,1,2,2,1,2,6,5,3,1,2,2,6,4,2,4,3,0,0,0,3,8,2,4,0,1,2,0,1,4,6,5,8,0,7,9,3,4,6,6,5,8,9,3,4,3,7,0,4,9,0,9,8,4,3,0,7,7,1,9,1,9,4,9,0,1,9,5,7,7,1,5,8,2,8,2,6,8,2,2,7,5,1,7,9,6]
+output = sol.canJump(input)
+print('res: ', output)
