<commit_before>"""Leetcode 45. Jump Game II
Hard

URL: https://leetcode.com/problems/jump-game-ii/

Given an array of non-negative integers, you are initially positioned at
the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:
You can assume that you can always reach the last index.
"""

class SolutionDPGreedy(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        Time complexity: O(n^2), where n is length of nums.
        Space complexity: O(n).
        """
        n = len(nums)

        # Create table T, where T[i] is min number of jumps to reach i.
        T = [n] * n
        T[0] = 0

        # For each pos i, loop to update T[end+1] ~ T[i+nums[i]].
        end = 0
        for i in range(n):
            for j in range(end + 1, min(i + nums[i], n - 1) + 1):
                T[j] = min(T[j], T[i] + 1)

            end = max(end, i + nums[i])

        return T[-1]


class SolutionBFSGreedy1(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        Time complexity: O(n), where n is length of nums.
        Space complexity: O(1).
        """
        n = len(nums)

        # Apply greedy algorithm to check index i in prev_end and end.
        prev_end, end = -1, 0
        jumps = 0

        for i in range(n):
            # Check if reached last index already.
            if end >= n - 1:
                break

            # Update jump if current index is behind prev_end.
            if prev_end < i:
                jumps += 1
                prev_end = end

            # Update end with current index and jump.
            end = max(end, i + nums[i])

        return jumps


class SolutionBFSGreedy2(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        Time complexity: O(n), where n is length of nums.
        Space complexity: O(1).
        """
        n = len(nums)

        cur_end, end = 0, 0
        jumps = 0

        for i in range(n - 1):
            # Break if reaches last index.
            if cur_end >= n - 1:
                break

            # Update end with current index and jump.
            end = max(end, i + nums[i])

            # If i reaches cur_end, trigger another jump and update cur_end.
            if i == cur_end:
                jumps += 1
                cur_end = end

        return jumps


def main():
    # Outpout: 2
    nums = [2,3,1,1,4]
    print SolutionDPGreedy().jump(nums)
    print SolutionBFSGreedy1().jump(nums)
    print SolutionBFSGreedy2().jump(nums)

    # Outpout: 2
    nums = [7,0,9,6,9,6,1,7,9,0,1,2,9,0,3]
    print SolutionDPGreedy().jump(nums)
    print SolutionBFSGreedy1().jump(nums)
    print SolutionBFSGreedy2().jump(nums)


if __name__ == '__main__':
    main()<commit_msg>Revise *end to *reach for better vars<commit_after>"""Leetcode 45. Jump Game II
Hard

URL: https://leetcode.com/problems/jump-game-ii/

Given an array of non-negative integers, you are initially positioned at
the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:
You can assume that you can always reach the last index.
"""

class SolutionDPGreedy(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        Time complexity: O(n^2), where n is length of nums.
        Space complexity: O(n).
        """
        n = len(nums)

        # Create table T, where T[i] is min number of jumps to reach i.
        T = [n] * n
        T[0] = 0

        # For each index i, loop to update T[reach+1] ~ T[i+nums[i]].
        reach = 0
        for i in range(n):
            for j in range(reach + 1, min(i + nums[i], n - 1) + 1):
                T[j] = min(T[j], T[i] + 1)

            reach = max(reach, i + nums[i])

        return T[-1]


class SolutionBFSGreedy1(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        Time complexity: O(n), where n is length of nums.
        Space complexity: O(1).
        """
        n = len(nums)

        # Apply greedy algorithm to check index i in prev_reach and reach.
        prev_reach, reach = -1, 0
        result = 0

        for i in range(n):
            # Check if reached last index already.
            if reach >= n - 1:
                break

            # Update jump if prev_reach is behind current index.
            if prev_reach < i:
                result += 1
                prev_reach = reach

            # Update reach with current index and jump.
            reach = max(reach, i + nums[i])

        return result


class SolutionBFSGreedy2(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        Time complexity: O(n), where n is length of nums.
        Space complexity: O(1).
        """
        n = len(nums)

        # Apply greedy algorithm to check index i in cur_reach and reach.
        cur_reach, reach = 0, 0
        result = 0

        for i in range(n - 1):
            # Break if reaches last index.
            if cur_reach >= n - 1:
                break

            # Update reach with current index and jump.
            reach = max(reach, i + nums[i])

            # If i reaches cur_reach, trigger another jump and update cur_reach.
            if i == cur_reach:
                result += 1
                cur_reach = reach

        return result


def main():
    # Outpout: 2
    nums = [2,3,1,1,4]
    print SolutionDPGreedy().jump(nums)
    print SolutionBFSGreedy1().jump(nums)
    print SolutionBFSGreedy2().jump(nums)

    # Outpout: 2
    nums = [7,0,9,6,9,6,1,7,9,0,1,2,9,0,3]
    print SolutionDPGreedy().jump(nums)
    print SolutionBFSGreedy1().jump(nums)
    print SolutionBFSGreedy2().jump(nums)


if __name__ == '__main__':
    main()
{'fraction_non_alphanumeric': 0.10299625468164794, 'fraction_numerical': 0.019975031210986267, 'mean_word_length': 1.820862676056338, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1741681', 'n_tokens_mistral': 2176, 'n_tokens_neox': 2012, 'n_words': 734}