1340. Jump Game V

HardArrayDynamic ProgrammingSorting
Leetcode Link

Problem Description

The problem presents an array of integers called arr alongside an integer d. You are tasked with finding the maximum number of indices you can visit starting from any index in the array. From a given index i, you can jump to an index i + x or i - x under two conditions:

  1. The value of x is between 1 and d, and the jump does not take you outside the bounds of the array.
  2. You can only make the jump if the number at the starting index arr[i] is greater than arr[j], where j is the index you want to jump to, and arr[i] is also greater than all the numbers between indices i and j.

You must navigate through the array by following these rules, with the goal being to maximize the number of indices visited.

Intuition

The intuition for solving this problem hinges on dynamic programming, which keeps track of the optimal sub-structure: the maximum number of jumps that can be made from each index. The process can be visualized as follows:

  1. We understand that each index is a potential starting point, and from each index, we need to consider jumps in both directions within the allowed range.
  2. If we are at index i, to determine the optimal number of jumps (f[i]) from that index, we need to look at all indices j we could jump to within the specified d range. If a jump to j is permissible, we update f[i] to be a maximum between its current value and f[j] + 1 which accounts for the jump just made.
  3. Since we need to ensure we are always jumping to a lower value, we sort the indices of the array based on the values at those indices. This ensures that when we are considering jumps from a particular index i, we have already computed the optimal jumps from lower valued indices.
  4. In this manner, we build up an array f where f[i] represents the maximum number of indices that can be visited starting from index i. The end goal is to return the maximum value from this f array, representing the maximum number of indices visited from the best starting location.

By building up a table of optimal solutions to sub-problems (f array) and using the sorted values to iterate in a controlled manner, we can use dynamic programming to compute the solution in an efficient way, without re-computing results. This makes the program more efficient compared to brute-force approaches, which would try to make a jump from every index in an uncontrolled manner and encounter considerable overlap and repeated calculation of the same scenarios.

Learn more about Dynamic Programming and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which technique can we use to find the middle of a linked list?

Solution Approach

The solution for this problem involves a dynamic programming approach. We create a table f where each index i has an initial value of 1, representing the minimum number of indices that can be visited (the index itself). We'll walk through the implementation approach step by step:

  • The problem is framed as a dynamic programming one, which commonly involves filling out a table or array of values. In this case, we're filling out the array f with the maximum number of indices that can be visited starting from each index.

  • Initially, all entries in f are set to 1, but as we explore jumps from each index, these entries may increase.

  • We sort a list of pairs, where each pair consists of the value at each index arr[i] and the index itself i. This ensures we always work from lower to higher values, respecting the jump rule that you can only jump to a smaller value.

  • We iterate over the sorted list, and for each index i, we examine the possible indices we can jump to within the range d in both directions (to the left and to the right).

  • For each possible jump from i to j, we check two conditions: whether the jump is within the distance d, and if arr[j] is less than arr[i]. If both conditions are met, it means a jump from i to j is valid.

  • Upon finding a valid jump, we update f[i] to be the maximum of its current value and f[j] + 1, reflecting the number of indices visited from j plus the jump just made from i to j.

  • This updating of f[i] happens for all j within the jumpable range from i that match the criteria of lower value and within the d distance. This ensures that f[i] represents the optimal (maximum) number of indices visited starting from i.

  • Since f has been filled from the lowest value of arr[i] upwards, by the time we reach higher values, we've already calculated the optimal number of indices that can be visited from all lower values; this property of the solution eliminates unnecessary recalculations and ensures the solution is efficient.

  • After we finish updating f[i] for all indices, the last step is to return max(f), the maximum value within f, which represents the maximum number of indices we can visit starting from the best possible index.

This process structurally follows a bottom-up dynamic programming approach, going from smaller sub-problems to larger sub-problems and using previous results to construct an optimal final answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's assume we have an array arr = [6, 4, 14, 6, 8] and d = 2.

Following the solution approach:

  1. We create our table f with the same length as arr and initialize all values to 1, because each index can visit at least itself.

    f = [1, 1, 1, 1, 1]

  2. We create a list of pairs to sort by value in arr: [(6, 0), (4, 1), (14, 2), (6, 3), (8, 4)].

  3. After sorting by the first element in the pairs: [(4, 1), (6, 0), (6, 3), (8, 4), (14, 2)].

  4. We proceed to iterate through our sorted list and consider jumps.

    • Starting with the pair (4, 1). There are no indices with smaller values than 4 within the range d, so we skip to the next pair.

    • For the pair (6, 0), we can jump to index 1 which has the value 4 (and is within d distance). We update f[0] to be the maximum of f[0] and f[1] + 1, so:

      f = [2, 1, 1, 1, 1]

    • Considering pair (6, 3), we can jump to index 1 and index 4. We update f[3] to be the maximum of f[3] and f[1] + 1, and f[3] and f[4] + 1:

      f = [2, 1, 1, 2, 1]

    • With pair (8, 4), we examine the indices within range d (indices 2 and 3), but we can only jump to index 3, updating f[4]:

      f = [2, 1, 1, 2, 3]

    • Lastly, the pair (14, 2). This value lets us jump to any lower index within d (0, 1, 3, and 4). We update f[2] for each of these:

      f = [2, 1, 4, 2, 3]

  5. Now we have our completed f table indicating the maximum number of indices that can be visited starting from each index. To get the answer, we just take the maximum value in f:

    max(f) = 4

So the maximum number of indices we can visit starting from the best index is 4, which starts from index 2 in the example array.

Solution Implementation

1class Solution:
2    def maxJumps(self, arr: List[int], max_distance: int) -> int:
3        # Determine the total number of elements in the array
4        num_elements = len(arr)
5      
6        # Initial jump counts set to 1 for each position, as each position can jump at least once
7        jumps = [1] * num_elements
8      
9        # Process positions in ascending order of their heights, along with their indices
10        for height, position in sorted(zip(arr, range(num_elements))):
11            # Check for jumps to the left
12            for left in range(position - 1, -1, -1):
13                # Stop if out of jump distance or if an equal or higher bar is met
14                if position - left > max_distance or arr[left] >= height:
15                    break
16                # Update the jump count if a new max is found
17                jumps[position] = max(jumps[position], 1 + jumps[left])
18              
19            # Check for jumps to the right
20            for right in range(position + 1, num_elements):
21                # Stop if out of jump distance or if an equal or higher bar is met
22                if right - position > max_distance or arr[right] >= height:
23                    break
24                # Update the jump count if a new max is found
25                jumps[position] = max(jumps[position], 1 + jumps[right])
26              
27        # Return the maximum jump count found across all positions
28        return max(jumps)
29
1class Solution {
2    public int maxJumps(int[] heights, int maxDistance) {
3        int n = heights.length;
4      
5        // Create an array of indices from the input array
6        Integer[] indices = new Integer[n];
7        for (int i = 0; i < n; ++i) {
8            indices[i] = i;
9        }
10      
11        // Sort the indices based on the heights, if the same height maintain the order of indices
12        Arrays.sort(indices, (i, j) -> Integer.compare(heights[i], heights[j]));
13      
14        int[] dp = new int[n]; // Dynamic programming array to store the max number of jumps
15        Arrays.fill(dp, 1); // Initialize with 1 since the min jumps for each position is 1 (stand still)
16      
17        int maxJumps = 0; // Variable to keep track of the maximum number of jumps
18      
19        // Calculate the maximum number of jumps you can do from each position
20        for (int currentIndex : indices) {
21            // Look left of the current index
22            for (int leftIndex = currentIndex - 1; leftIndex >= 0; --leftIndex) {
23                // If it's too far or the height at leftIndex is higher or equal, we can't jump from there
24                if (currentIndex - leftIndex > maxDistance || heights[leftIndex] >= heights[currentIndex]) {
25                    break;
26                }
27                // Update the dp value if we find a better path
28                dp[currentIndex] = Math.max(dp[currentIndex], 1 + dp[leftIndex]);
29            }
30          
31            // Look right of the current index
32            for (int rightIndex = currentIndex + 1; rightIndex < n; ++rightIndex) {
33                // If it's too far or the height at rightIndex is higher or equal, we can't jump from there
34                if (rightIndex - currentIndex > maxDistance || heights[rightIndex] >= heights[currentIndex]) {
35                    break;
36                }
37                // Update the dp value if we find a better path
38                dp[currentIndex] = Math.max(dp[currentIndex], 1 + dp[rightIndex]);
39            }
40          
41            // Update the result with the maximum dp value found so far
42            maxJumps = Math.max(maxJumps, dp[currentIndex]);
43        }
44      
45        return maxJumps; // Return the maximum number of jumps possible
46    }
47}
48
1#include <vector>
2#include <algorithm>
3#include <numeric>
4using namespace std;
5
6class Solution {
7public:
8    // Function to find the maximum number of jumps you can make in the array
9    int maxJumps(vector<int>& heights, int maxDistance) {
10        int n = heights.size(); // Size of the array
11      
12        // Initialize an index vector with values from 0 to n-1
13        vector<int> indices(n);
14        iota(indices.begin(), indices.end(), 0);
15      
16        // Sort the indices based on the corresponding values in 'heights'
17        sort(indices.begin(), indices.end(), [&](int a, int b) { return heights[a] < heights[b]; });
18      
19        // Initialize a vector to store the furthest jump length from every position
20        vector<int> dp(n, 1); // All elements are initialized to 1 as the minimum jump is always 1 (itself)
21      
22        // Loop through the sorted indices to fill dp in increasing order of heights
23        for (int index : indices) {
24            // Look to the left of the current index
25            for (int left = index - 1; left >= 0; --left) {
26                // If the left element is out of bounds or taller, stop checking further
27                if (index - left > maxDistance || heights[left] >= heights[index]) {
28                    break;
29                }
30                // Update dp array for index with the optimal previous jump count
31                dp[index] = max(dp[index], 1 + dp[left]);
32            }
33            // Look to the right of the current index
34            for (int right = index + 1; right < n; ++right) {
35                // If the right element is out of bounds or taller, stop checking further
36                if (right - index > maxDistance || heights[right] >= heights[index]) {
37                    break;
38                }
39                // Update dp array for index with the optimal previous jump count
40                dp[index] = max(dp[index], 1 + dp[right]);
41            }
42        }
43        // Return the maximum jumps that can be made, found in the dp array
44        return *max_element(dp.begin(), dp.end());
45    }
46};
47
1// Importing necessary functionalities from arrays and algorithms
2import { max } from 'lodash';
3
4// Function to find the maximum number of jumps you can make in the array
5function maxJumps(heights: number[], maxDistance: number): number {
6    const n: number = heights.length; // Size of the array
7
8    // Initialize an index array with values from 0 to n-1
9    const indices: number[] = Array.from({ length: n }, (_, i) => i);
10
11    // Sort the indices based on the corresponding values in 'heights'
12    indices.sort((a, b) => heights[a] - heights[b]);
13
14    // Initialize an array to store the furthest jump length from every position
15    const dp: number[] = new Array(n).fill(1); // All elements are initialized to 1 as the minimum jump is always 1 (itself)
16
17    // Loop through the sorted indices to fill dp in increasing order of heights
18    indices.forEach((index) => {
19        // Look to the left of the current index
20        for (let left = index - 1; left >= 0; --left) {
21            // If the left element is out of maxDistance or taller, stop checking further
22            if (index - left > maxDistance || heights[left] >= heights[index]) {
23                break;
24            }
25            // Update dp array for index with the optimal previous jump count
26            dp[index] = Math.max(dp[index], 1 + dp[left]);
27        }
28        // Look to the right of the current index
29        for (let right = index + 1; right < n; ++right) {
30            // If the right element is out of maxDistance or taller, stop checking further
31            if (right - index > maxDistance || heights[right] >= heights[index]) {
32                break;
33            }
34            // Update dp array for index with the optimal previous jump count
35            dp[index] = Math.max(dp[index], 1 + dp[right]);
36        }
37    });
38
39    // Return the maximum jumps that can be made, found in the dp array
40    return Math.max(...dp);
41}
42
43// Example usage:
44// If you want to call the function, you would pass in the heights array and maxDistance like so:
45// maxJumps([4, 2, 7, 6, 9, 14, 12], 2);
46
Not Sure What to Study? Take the 2-min Quiz

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed based on the following:

  1. Sorting the array arr alongside the indices has a complexity of O(n log n) where n is the length of the array arr.
  2. The double nested loops contribute to the time complexity in the following way:
    • The outer loop runs n times since it iterates over the sorted arrays of heights and indices.
    • Each inner loop performs a linear scan in both directions, but due to the constraint limiting the jumps to distance d, the inner loops each run at most d times.
    • Therefore, the inner loops collectively contribute at most O(n * 2d) = O(nd) time complexity.

Combining these, the total time complexity of the code is O(n log n + nd).

Space Complexity

The space complexity of the given code can be analyzed based on the following:

  1. An auxiliary array f of size n is used to store the maximum number of jumps from each position, contributing an O(n) space complexity.
  2. Since there are no recursive calls or additional data structures that grow with the input size, and the sorting operation can be assumed to use O(1) space given that most sorting algorithms can be done in-place (like Timsort in Python), the additional space complexity imposed by the stack frames during the for loops and sorting is constant.

Therefore, the total space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«