LeetCode 1344. Jump Game V

Question

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

• i + x where: i + x < arr.length and 0 < x <= d.
• i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Solution

We need to use DFS to search for the index that can meet the conditions, otherwise we return 1. Also, we can memorize the index to steps we need and that can help us to reduce the time to O(nd).

Code

// time:O(n * d) space:O(n)
    public int maxJumps(int[] arr, int d) {
        if (arr == null || arr.length == 0) return 0;
        if (arr.length == 1) return 1;
        int n = arr.length;
        boolean[] visited = new boolean[n];
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, dfs(arr, d, visited, i, map));
        }
        return max;
    }

    public int dfs(int[] arr, int d, boolean[] visited, int currIndex, HashMap<Integer, Integer> map) {
        if (currIndex < 0 || currIndex >= arr.length) return 0;
        if (visited[currIndex]) return 0;
        if (map.get(currIndex) != null) return map.get(currIndex);

        visited[currIndex] = true;
        int val = 1;
        for (int i = 1; i <= d; i++) {
            if (isValid(arr, currIndex, currIndex + i)) val = Math.max(val, dfs(arr, d, visited, currIndex + i, map) + 1) ;
            if (isValid(arr, currIndex, currIndex - i)) val = Math.max(val, dfs(arr, d, visited, currIndex - i, map) + 1);
        }

        visited[currIndex] = false;
        map.put(currIndex, val);
        return val;
    }
    public boolean isValid(int[] nums, int from, int to) {
        if (from < 0 || from >= nums.length || to < 0 || to >= nums.length) return false;

        int max = nums[from];
        if (from > to) {
            for (int i = to; i < from; i++) {
                if (nums[i] >= max) return false;
            }
        } else {
            for (int i = from + 1; i <= to; i++) {
                if (nums[i] >= max) return false;
            }
        }
        return true;
    }

// more elegant solution
// time: O(nd) space:O(n)
    public int maxJumps2(int[] arr, int d) {
        int n = arr.length;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dfs(arr, i, memo, d, n));
        }
        return res;
    }

    public int dfs (int[] arr, int index, int[] memo, int d, int n) {
        if (memo[index] != -1) return memo[index];
        int val = 1;
        // we don't need visited array, because each time we couldn't go back.
        for (int j = index + 1; j <= Math.min(n - 1, index + d) && arr[index] > arr[j]; j++) {
            val = Math.max(val, dfs(arr, j, memo, d, n) + 1);
        }

        for (int j = index - 1; j >= Math.max(0, index - d) && arr[index] > arr[j]; j--) {
            val = Math.max(val, dfs(arr, j, memo, d, n) + 1);
        }
        memo[index] = val;
        return val;
    }

Reference

• https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-1344-jump-game-v/