975. Odd Even Jump
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.
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:
-
Memoization Decorator: The
@cache
decorator is applied to thedfs
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. -
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 parameterk
indicates the jump type,0
for even and1
for odd.- Base Case: If the current index is the last in the array (
i == n - 1
), the function returnsTrue
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 returnsFalse
.
- Base Case: If the current index is the last in the array (
-
Graph
g
: A 2D listg
is initialized to keep track of next indices for odd and even jumps from each index. The first dimension corresponds to the index inarr
and the second dimension (0
or1
) corresponds to the type of jump. -
SortedDict
sd
: A SortedDict is used to efficiently find the next indices for jumps. As we iterate backward through the array (i
going fromn - 1
to0
), this structure allows us to:- Odd-numbered jumps: Use
sd.bisect_left(arr[i])
to find the smallest index wherearr[j]
is greater than or equal toarr[i]
. - Even-numbered jumps: Use
sd.bisect_right(arr[i]) - 1
to find the largest index wherearr[j]
is smaller than or equal toarr[i]
.
- Odd-numbered jumps: Use
-
Building the Graph
g
: For each indexi
, we updateg[i][1]
for odd jumps andg[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 insd
. -
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 from0
ton - 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small array arr = [5, 1, 3, 4, 2]
to illustrate the solution approach:
-
Initialization: We prepare a 2D list
g
whereg[i][0]
andg[i][1]
will store the next index for an even and an odd jump from the indexi
, respectively. We also create aSortedDict
namedsd
. -
Building the Graph: Start iterating from the end (
i = 4
) to the start (i = 0
) of the array:- For
i = 4
(value2
),sd
is empty, so no jumps are possible.g[4] = [-1, -1]
. - Insert
(2, 4)
intosd
. - For
i = 3
(value4
), the next odd jump goes to the smallest larger or equal value insd
(bisect_left(4)
), but there is none, sog[3][1] = -1
. For even jumps, the next jump is to the largest smaller or equal value insd
(bisect_right(4) - 1
), which is the index of value2
, sog[3][0] = 4
. - Insert
(4, 3)
intosd
. - For
i = 2
(value3
), the next odd jump is to4
and the next even jump is to2
. Sog[2] = [4, 3]
. - Insert
(3, 2)
intosd
. - For
i = 1
(value1
), the next odd jump is to3
and there is no even jump, sog[1] = [-1, 2]
. - Insert
(1, 1)
intosd
. - For
i = 0
(value5
), there are no larger or smaller values than5
insd
, sog[0] = [-1, -1]
.
- For
-
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 returnsFalse
becauseg[0][1] = -1
. dfs(1, 1)
returnsTrue
becauseg[1][1] = 2
and from index2
, an even jump leads to the end (dfs(2, 0)
returnsTrue
).dfs(3, 1)
returnsFalse
since no odd jump is possible from3
.dfs(4, 1)
also returnsFalse
since no jump is possible from4
.
- Start with index
-
Result: Count all
True
results fromdfs(i, 1)
fori
in[0, 1, 2, 3, 4]
to get the total number of "good" starting indices. In our example, the count is1
(only index1
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
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 forn
iterations, wheren
is the length ofarr
. In each iteration, twobisect
operations are performed onSortedDict
to find the next indices for odd and even jumps.- The
bisect_left
andbisect_right
operations on a BST have a time complexity ofO(log m)
, wherem
is the number of elements in the BST at the time of the query. In the worst case,m
can be as large asn
. - Inserting an element into the
SortedDict
also has a time complexity ofO(log n)
.
- The
-
The DFS function
dfs
could potentially be called for every starting positioni
with every jump typek
. As memoization is used, each pair(i, k)
will be computed at most once. Therefore, we can consider it to have a constant time complexityO(1)
for each call, after the initial computation. -
The final sum calls
dfs
for each starting positioni
with the initial jump type1
(odd jump), totalingn
calls todfs
. However, sincedfs
is memoized, the actual complexity of all these calls altogether isO(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 requireO(n * 2)
space since it stores results for each element and jump type (odd or even). This simplifies toO(n)
. -
The graph
g
is a 2D array with dimensionsn * 2
, also takingO(n)
space. -
The
SortedDict
can hold up ton
elements, so it also consumesO(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.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
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
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 Deque Intro If you'd prefer a video div class responsive iframe iframe 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 div The word monotonic means a list or
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.