975. Odd Even Jump

HardStackArrayDynamic ProgrammingOrdered SetMonotonic Stack
Leetcode Link

Problem Description

This problem asks us to count "good" starting indices in an array arr. A good starting index is defined as an index from which it is possible to reach the end of the array by making a series of jumps following specific rules. These jumps are of two types: odd-numbered jumps and even-numbered jumps. For odd-numbered jumps, you look for the smallest value in the array that is greater than or equal to the value at the current index and jump to the first occurrence of this smallest value. For even-numbered jumps, you look for the largest value that is less than or equal to the value at the current index and jump to the first occurrence of this largest value. If there are no valid jumps possible from an index, you cannot proceed from that point. The goal is to determine the count of indices from which reaching the end of the array is possible.

Intuition

The intuition behind this solution lies in dynamic programming and the use of efficient data structures to keep track of legal jumps.

Since the jumps need us to look up the smallest larger (or largest smaller) value, we can leverage a sorted data structure like SortedDict from the sortedcontainers module in Python. This allows us to efficiently locate the next jump index using binary search operations (in O(log n) time complexity).

With dynamic programming, we can avoid recalculating whether it's possible to reach the end from a given index by storing the results of our calculations. We define a recursive function dfs which tries to determine if it is possible to reach the end of the array starting at index i and making a specific type of jump (odd or even). We then apply memoization using the cache decorator to store the results and avoid redundant computations.

For the overall solution, we iterate backward through the array. At each index, we use the SortedDict structure to find the correct jump indices for both odd and even jumps. Then, we attempt to find out if it's possible to reach the end from each index making an odd jump first (since we must start with an odd-numbered jump). The total count of "good" starting indices is the sum of all indices from which the end can be reached by following the jumping rules.

The crux of the solution is to carefully build a graph-like structure that maps each index to the next index for an odd or even jump. And then, use a depth-first search (DFS) strategy to explore possible paths from each potential starting index to the last index, using memoization to speed up the process significantly.

Learn more about Stack, Dynamic Programming and Monotonic Stack patterns.

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

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The given Python solution follows a bottom-up dynamic programming strategy with memoization. Here is a step-by-step breakdown of the implementation details:

  1. Memoization Decorator: The @cache decorator is applied to the dfs function. This is Python's built-in way to store results of expensive function calls and return the cached result when the same inputs occur again. It helps to avoid repeated computation for the same starting index and jump type.

  2. Helper Function dfs: This is the function that attempts to find if the current index (i) can reach the end of the array with a sequence of odd and even jumps. The parameter k indicates the jump type, 0 for even and 1 for odd.

    • Base Case: If the current index is the last in the array (i == n - 1), the function returns True as we've successfully reached the end.
    • Recursive Case: If a jump is possible (g[i][k] is not -1), the function recursively calls itself, toggling the jump type (k ^ 1) to simulate the alternation of jumps.
    • Jump Not Possible: If no jump is possible from the current index (g[i][k] is -1), the function returns False.

  3. Graph g: A 2D list g is initialized to keep track of next indices for odd and even jumps from each index. The first dimension corresponds to the index in arr and the second dimension (0 or 1) corresponds to the type of jump.

  4. SortedDict sd: A SortedDict is used to efficiently find the next indices for jumps. As we iterate backward through the array (i going from n - 1 to 0), this structure allows us to:

    • Odd-numbered jumps: Use sd.bisect_left(arr[i]) to find the smallest index where arr[j] is greater than or equal to arr[i].
    • Even-numbered jumps: Use sd.bisect_right(arr[i]) - 1 to find the largest index where arr[j] is smaller than or equal to arr[i].

  5. Building the Graph g: For each index i, we update g[i][1] for odd jumps and g[i][0] for even jumps, or assign -1 if no jump is possible. Here, sd.values() returns the list of indices in the order of their corresponding values in sd.

  6. Calculating Good Starting Indices: Finally, the sum of all indices from which the end of the array can be reached by starting with an odd jump is computed. We do this by invoking dfs(i, 1) for all indices from 0 to n - 1, and then taking the sum of these boolean results.

The solution smartly combines memoized recursion for dynamic programming and binary search within a sorted dictionary to maintain a balance between time complexity and the practical execution speed of the algorithm.

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

Which data structure is used in a depth first search?

Example Walkthrough

Let's consider a small array arr = [5, 1, 3, 4, 2] to illustrate the solution approach:

  1. Initialization: We prepare a 2D list g where g[i][0] and g[i][1] will store the next index for an even and an odd jump from the index i, respectively. We also create a SortedDict named sd.

  2. Building the Graph: Start iterating from the end (i = 4) to the start (i = 0) of the array:

    • For i = 4 (value 2), sd is empty, so no jumps are possible. g[4] = [-1, -1].
    • Insert (2, 4) into sd.
    • For i = 3 (value 4), the next odd jump goes to the smallest larger or equal value in sd (bisect_left(4)), but there is none, so g[3][1] = -1. For even jumps, the next jump is to the largest smaller or equal value in sd (bisect_right(4) - 1), which is the index of value 2, so g[3][0] = 4.
    • Insert (4, 3) into sd.
    • For i = 2 (value 3), the next odd jump is to 4 and the next even jump is to 2. So g[2] = [4, 3].
    • Insert (3, 2) into sd.
    • For i = 1 (value 1), the next odd jump is to 3 and there is no even jump, so g[1] = [-1, 2].
    • Insert (1, 1) into sd.
    • For i = 0 (value 5), there are no larger or smaller values than 5 in sd, so g[0] = [-1, -1].

  3. Calculating Good Starting Indices: We create a dfs function with memoization using the @cache decorator:

    • Start with index 0 and an odd jump (dfs(0, 1)). This function call returns False because g[0][1] = -1.
    • dfs(1, 1) returns True because g[1][1] = 2 and from index 2, an even jump leads to the end (dfs(2, 0) returns True).
    • dfs(3, 1) returns False since no odd jump is possible from 3.
    • dfs(4, 1) also returns False since no jump is possible from 4.

  4. Result: Count all True results from dfs(i, 1) for i in [0, 1, 2, 3, 4] to get the total number of "good" starting indices. In our example, the count is 1 (only index 1 leads to the end of the array by following jump rules).

Hence, for our array arr = [5, 1, 3, 4, 2], there is only one "good" starting index, which is the index 1.

Solution Implementation

1from sortedcontainers import SortedDict
2from functools import lru_cache  # This is used for memoization in Python 3
3from typing import List
4
5class Solution:
6    def oddEvenJumps(self, arr: List[int]) -> int:
7        # Helper function to perform a depth-first search (dfs)
8        # i: current index
9        # jump_type: 1 for odd jumps, 0 for even jumps
10        @lru_cache(maxsize=None)  # use lru_cache for memoization
11        def dfs(index: int, jump_type: int) -> bool:
12            if index == n - 1:  # If we've reached the last element, return True
13                return True
14            if jump_graph[index][jump_type] == -1:  # If there's no valid jump, return False
15                return False
16            # Perform the jump and toggle the jump_type (odd <-> even)
17            return dfs(jump_graph[index][jump_type], jump_type ^ 1)
18
19        n = len(arr)  # Length of the input array
20        # Initialize a 2D array with an additional dimension representing the jump type
21        jump_graph = [[-1, -1] for _ in range(n)]
22        sd = SortedDict()  # Use SortedDict to maintain a sorted order of elements
23      
24        # Build the graph in reverse
25        for i in range(n - 1, -1, -1):
26          
27            # Handle odd jumps (ascending order)
28            next_jump_index = sd.bisect_left(arr[i])
29            if next_jump_index < len(sd):
30                jump_graph[i][1] = sd.peekitem(next_jump_index)[1]
31          
32            # Handle even jumps (descending order)
33            next_jump_index = sd.bisect_right(arr[i]) - 1
34            if next_jump_index >= 0:
35                jump_graph[i][0] = sd.peekitem(next_jump_index)[1]
36          
37            # Update the SortedDict with the current element
38            sd[arr[i]] = i
39      
40        # We can start with an odd jump (1), so we check for each index if we can reach the end
41        return sum(dfs(i, 1) for i in range(n))
42
43# Example usage of the solution - uncomment to test:
44# sol = Solution()
45# print(sol.oddEvenJumps([10, 13, 12, 14, 15]))  # Expected output: 2
46
1class Solution {
2    private int arrayLength;
3    private Integer[][] dp;
4    private int[][] nextIndices;
5
6    // Main function to compute the number of good starting indices
7    public int oddEvenJumps(int[] arr) {
8        TreeMap<Integer, Integer> valueToIndexMap = new TreeMap<>();
9        arrayLength = arr.length;
10        dp = new Integer[arrayLength][2];
11        nextIndices = new int[arrayLength][2];
12      
13        // Preprocessing: Populate the next indices for odd and even jumps for each element
14        for (int i = arrayLength - 1; i >= 0; --i) {
15            // Find the smallest number greater than or equal to current number
16            var higher = valueToIndexMap.ceilingEntry(arr[i]);
17            // Update the next index for an odd jump
18            nextIndices[i][1] = higher == null ? -1 : higher.getValue();
19          
20            // Find the greatest number less than or equal to the current number
21            var lower = valueToIndexMap.floorEntry(arr[i]);
22            // Update the next index for an even jump
23            nextIndices[i][0] = lower == null ? -1 : lower.getValue();
24          
25            // Map the current number to its index
26            valueToIndexMap.put(arr[i], i);
27        }
28      
29        int goodStartingIndicesCount = 0;
30        // Check each index as a starting point
31        for (int i = 0; i < arrayLength; ++i) {
32            // If the current index leads to the end by a sequence of jumps, include it in the count
33            goodStartingIndicesCount += performJump(i, 1);
34        }
35        return goodStartingIndicesCount;
36    }
37
38    // Recursive function to determine if we can reach the end from index i
39    private int performJump(int index, int jumpType) {
40        // If we've reached the end, return 1 (successful jump sequence)
41        if (index == arrayLength - 1) {
42            return 1;
43        }
44        // If there is no valid next jump, return 0 (failed to reach the end)
45        if (nextIndices[index][jumpType] == -1) {
46            return 0;
47        }
48        // Use memoization to avoid recomputation
49        if (dp[index][jumpType] != null) {
50            return dp[index][jumpType];
51        }
52        // Perform the next jump with the alternating jump type (odd -> even, even -> odd)
53        return dp[index][jumpType] = performJump(nextIndices[index][jumpType], jumpType ^ 1);
54    }
55}
56
1#include <vector>
2#include <map>
3#include <cstring> // For memset
4#include <functional> // For std::function
5
6class Solution {
7public:
8    int oddEvenJumps(std::vector<int>& arr) {
9        int n = arr.size(); // Size of the input array
10        std::map<int, int> indicesMap; // Map to hold value-to-index mappings
11        int jumps[n][2]; // Jump status (odd-0/even-1) array
12        int nextJump[n][2]; // Next jump index (odd-0/even-1) array
13        memset(jumps, 0, sizeof(jumps)); // Initialize the jump status array to 0
14      
15        // Populate the next jump index array
16        for (int i = n - 1; i >= 0; --i) {
17            auto it = indicesMap.lower_bound(arr[i]); // Iterator for the 'odd' jump
18            nextJump[i][1] = it == indicesMap.end() ? -1 : it->second; // Set next jump for 'odd'
19          
20            it = indicesMap.upper_bound(arr[i]); // Iterator for the 'even' jump
21            // Set next jump for 'even', using previous iterator if not the beginning
22            nextJump[i][0] = it == indicesMap.begin() ? -1 : std::prev(it)->second; 
23          
24            indicesMap[arr[i]] = i; // Update the map with the current index
25        }
26      
27        // Depth-first search function to perform the jump calculation
28        std::function<int(int, int)> dfs = [&](int index, int jumpType) -> int {
29            if (index == n - 1) { // If we've reached the last index, the jump is successful
30                return 1;
31            }
32            if (nextJump[index][jumpType] == -1) { // If there's no next jump, return 0
33                return 0;
34            }
35            if (jumps[index][jumpType] != 0) { // If the jump status is already calculated, return it
36                return jumps[index][jumpType];
37            }
38            // Perform the jump and store the result in the jump status array
39            return jumps[index][jumpType] = dfs(nextJump[index][jumpType], jumpType ^ 1);
40        };
41      
42        int answer = 0; // Initialize answer to count successful jumps
43        // Try to start a jump (odd) from each index
44        for (int i = 0; i < n; ++i) {
45            answer += dfs(i, 1); // Count only the successful jumps
46        }
47        return answer; // Return the number of successful jumps
48    }
49};
50
1// Importing necessary functions for the code to work
2import { lowerBound, prev } from 'some-library-to-handle-arrays'; // Placeholder, replace with actual library
3
4const n: number; // Size of the input array
5const indicesMap: Map<number, number> = new Map(); // Map to hold value-to-index mappings
6const jumps: number[][] = Array.from(Array(n), () => Array(2).fill(0)); // Jump status array for odd (0) and even (1) jumps
7const nextJump: number[][] = Array.from(Array(n), () => Array(2).fill(-1)); // Next jump index array for odd (0) and even (1) jumps
8
9function populateNextJump(arr: number[]): void {
10  // Reverse iterate through the input array to populate the next jump indices
11  for (let i = n - 1; i >= 0; --i) {
12    const it = lowerBound(indicesMap, arr[i]); // Lower bound for the odd jump
13    nextJump[i][1] = it === indicesMap.end() ? -1 : it.value; // Set next jump index for the odd jump
14
15    const itUpper = upperBound(indicesMap, arr[i]); // Upper bound for the even jump
16    // Set next jump index for the even jump, using the previous element if not at the beginning
17    nextJump[i][0] = itUpper === indicesMap.begin() ? -1 : prev(itUpper).value;
18
19    indicesMap.set(arr[i], i); // Update the indices map with the current index
20  }
21}
22
23function depthFirstSearch(index: number, jumpType: number): number {
24  // If we've reached the last index, the jump is successful
25  if (index === n - 1) {
26    return 1;
27  }
28  // If there's no next jump, the jump is not successful
29  if (nextJump[index][jumpType] === -1) {
30    return 0;
31  }
32  // If the jump status is already computed, return it
33  if (jumps[index][jumpType] !== 0) {
34    return jumps[index][jumpType];
35  }
36  // Calculate the jump status by jumping to the next index, and alternate the jump type
37  jumps[index][jumpType] = depthFirstSearch(nextJump[index][jumpType], 1 - jumpType);
38  return jumps[index][jumpType];
39}
40
41function oddEvenJumps(arr: number[]): number {
42  populateNextJump(arr); // Populate next jump indices before computing jumps
43
44  let answer: number = 0; // Initialize answer to count successful odd jumps from each index
45  // Iterate through each index in the input array to start an odd jump
46  for (let i = 0; i < n; ++i) {
47    answer += depthFirstSearch(i, 1); // Add to the answer if the odd jump is successful
48  }
49  return answer; // Return the total count of successful odd jumps
50}
51
52// Mock implementation, replace 'some-library-to-handle-arrays' with the actual library
53function lowerBound(map: Map<number, number>, value: number): { end: () => boolean, value: number } {
54  // Implement the lowerBound logic specific to your requirements
55  // This should find the first element in the map that is not less than 'value'
56  return { end: () => false, value: 0 }; // Placeholder return
57}
58
59function upperBound(map: Map<number, number>, value: number): { begin: () => boolean, value: number } {
60  // Implement the upperBound logic specific to your requirements
61  // This should find the first element in the map that is greater than 'value'
62  return { begin: () => false, value: 0 }; // Placeholder return
63}
64
65// Mock implementation for the prev function, replace with actual implementation
66function prev(iterator: { value: number }): { value: number } {
67  // Implement the prev logic specific to your requirements
68  return { value: iterator.value }; // Placeholder return
69}
70
Not Sure What to Study? Take the 2-min Quiz

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Time and Space Complexity

Time Complexity

The function oddEvenJumps involves both a dynamic programming approach (through memoization with @cache) and the use of a balanced binary search tree (BST) through SortedDict.

  • The loop that constructs the graph g runs for n iterations, where n is the length of arr. In each iteration, two bisect operations are performed on SortedDict to find the next indices for odd and even jumps.

    • The bisect_left and bisect_right operations on a BST have a time complexity of O(log m), where m is the number of elements in the BST at the time of the query. In the worst case, m can be as large as n.
    • Inserting an element into the SortedDict also has a time complexity of O(log n).

  • The DFS function dfs could potentially be called for every starting position i with every jump type k. As memoization is used, each pair (i, k) will be computed at most once. Therefore, we can consider it to have a constant time complexity O(1) for each call, after the initial computation.

  • The final sum calls dfs for each starting position i with the initial jump type 1 (odd jump), totaling n calls to dfs. However, since dfs is memoized, the actual complexity of all these calls altogether is O(n).

Combining these parts, the overall time complexity is O(n log n) due to the combination of the loop and the operations on the SortedDict within the loop, which dominates over the linear time complexity of the final sum.

Space Complexity

  • The space used by the memoization in dfs function will require O(n * 2) space since it stores results for each element and jump type (odd or even). This simplifies to O(n).

  • The graph g is a 2D array with dimensions n * 2, also taking O(n) space.

  • The SortedDict can hold up to n elements, so it also consumes O(n) space.

Overall, combining the space for memoization, the graph g, and the SortedDict, the total space complexity 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:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

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

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

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 đŸ‘šâ€đŸ«