Odd Even Jump

Hard

Amazon

2 views

Topics:

ArraysDynamic Programming

You are given an integer array arr. From some starting index, you can make a series of jumps. The (1^st, 3^rd, 5^th, ...) jumps in the series are called odd-numbered jumps, and the (2^nd, 4^th, 6^th, ...) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.

You may jump forward from index i to index j (with i < j) in the following way:

During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
It may be the case that for some index i, there are no legal jumps.

A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).

Return the number of good starting indices.

Example 1:

Input: arr = [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of
jumps.

Example 2:

Input: arr = [2,3,1,1,4]
Output: 3
Explanation: 
From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:
During our 1st jump (odd-numbered), we first jump to i = 1 because arr[1] is the smallest value in [arr[1], arr[2], arr[3], arr[4]] that is greater than or equal to arr[0].
During our 2nd jump (even-numbered), we jump from i = 1 to i = 2 because arr[2] is the largest value in [arr[2], arr[3], arr[4]] that is less than or equal to arr[1]. arr[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3
During our 3rd jump (odd-numbered), we jump from i = 2 to i = 3 because arr[3] is the smallest value in [arr[3], arr[4]] that is greater than or equal to arr[2].
We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good.
In a similar manner, we can deduce that:
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.
In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some
number of jumps.

Example 3:

Input: arr = [5,1,3,4,2]
Output: 3
Explanation: We can reach the end from starting indices 1, 2, and 4.

Constraints:

1 <= arr.length <= 2 * 10⁴
0 <= arr[i] < 10⁵

Odd Even Jump

Hard

Amazon

2 views

Topics:

ArraysDynamic Programming

You are given an integer array arr. From some starting index, you can make a series of jumps. The (1^st, 3^rd, 5^th, ...) jumps in the series are called odd-numbered jumps, and the (2^nd, 4^th, 6^th, ...) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.

You may jump forward from index i to index j (with i < j) in the following way:

During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
It may be the case that for some index i, there are no legal jumps.

A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).

Return the number of good starting indices.

Example 1:

Input: arr = [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of
jumps.

Example 2:

Input: arr = [2,3,1,1,4]
Output: 3
Explanation: 
From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:
During our 1st jump (odd-numbered), we first jump to i = 1 because arr[1] is the smallest value in [arr[1], arr[2], arr[3], arr[4]] that is greater than or equal to arr[0].
During our 2nd jump (even-numbered), we jump from i = 1 to i = 2 because arr[2] is the largest value in [arr[2], arr[3], arr[4]] that is less than or equal to arr[1]. arr[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3
During our 3rd jump (odd-numbered), we jump from i = 2 to i = 3 because arr[3] is the smallest value in [arr[3], arr[4]] that is greater than or equal to arr[2].
We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good.
In a similar manner, we can deduce that:
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.
In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some
number of jumps.

Example 3:

Input: arr = [5,1,3,4,2]
Output: 3
Explanation: We can reach the end from starting indices 1, 2, and 4.

Constraints:

1 <= arr.length <= 2 * 10⁴
0 <= arr[i] < 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the array contain negative numbers or zeros?
Are duplicate values allowed in the array, and if so, how should they be handled?
If it's impossible to reach the end of the array from a starting index, what should the function return?
Could you clarify the behavior if the array is empty or contains only one element?

Brute Force Solution

Approach

The goal is to figure out how many starting positions let you reach the end by making specific jumps. We're going to try every possible jumping sequence from each starting position to see if it gets us to the end.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list of numbers.
From this starting number, consider two types of jumps: an odd jump and an even jump.
For the odd jump, find the smallest number in the remaining list that is greater than or equal to your current number. If there are ties, pick the leftmost one.
Then, jump to that number.
Now, for the even jump, find the largest number in the remaining list that is less than or equal to your current number. If there are ties, pick the leftmost one.
Then, jump to that number.
Alternate between making odd and even jumps. Odd, then even, then odd, and so on.
If, at any point, you cannot make a jump (because there are no numbers available that meet the jump criteria), this sequence doesn't work. Stop trying this sequence.
If you reach the end of the list by making these alternating jumps, then this starting position is a success. Mark it as such.
Repeat these steps for every single number in the list, trying all possible jumping sequences from each starting point.
Finally, count the number of starting positions that allowed you to successfully reach the end of the list by making these alternating jumps.

Code Implementation

def odd_even_jump(array):
    number_of_indices_that_reach_end = 0
    array_length = len(array)

    for start_index in range(array_length):
        current_index = start_index
        jump_count = 0
        can_reach_end = True

        while current_index < array_length - 1:
            #Determine if we need to make an odd or even jump based on jump count
            if jump_count % 2 == 0:
                next_index = find_next_odd_jump(array, current_index)
            else:
                next_index = find_next_even_jump(array, current_index)

            if next_index == -1:
                can_reach_end = False
                break

            current_index = next_index
            jump_count += 1

        if can_reach_end:
            number_of_indices_that_reach_end += 1

    return number_of_indices_that_reach_end

def find_next_odd_jump(array, current_index):
    next_index = -1
    min_value = float('inf')
    
    #Iterate through array from current index to find valid next odd jump
    for index in range(current_index + 1, len(array)):
        if array[index] >= array[current_index]:
            if array[index] < min_value:
                min_value = array[index]
                next_index = index

    return next_index

def find_next_even_jump(array, current_index):
    next_index = -1
    max_value = float('-inf')

    #Iterate through array from current index to find valid next even jump
    for index in range(current_index + 1, len(array)):
        if array[index] <= array[current_index]:
            if array[index] > max_value:
                max_value = array[index]
                next_index = index

    return next_index

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n starting positions in the array. For each starting position, it simulates jumps until it either reaches the end or gets stuck. In the worst case, from each starting position, it might need to examine almost all of the remaining elements to find the next jump (either the smallest greater or equal, or the largest less than or equal). This inner loop can take up to n steps in the worst case. Therefore, the overall time complexity is approximately n * n, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm implicitly uses two arrays, let's call them odd and even, of size N (where N is the length of the input array). These arrays are used to store boolean values indicating whether it's possible to reach the end of the array from a given index using an odd or even jump, respectively. Therefore, the auxiliary space required is directly proportional to the size of the input array, leading to a space complexity of O(N).

Optimal Solution

Approach

The key to solving this efficiently is to figure out for each position whether you can reach the end using only odd and even jumps. Instead of exploring every possible jump sequence, we pre-calculate reachability from each spot using a clever trick involving sorted positions.

Here's how the algorithm would work step-by-step:

Imagine you're trying to reach the end from different starting points.
For each starting point, you want to know: 'Can I reach the end with alternating odd and even jumps?'
To figure this out quickly, let's first find, for each starting point, what its next 'odd jump' location would be (the smallest value greater than or equal to the current value).
Do the same thing to find the next 'even jump' location (the largest value less than or equal to the current value).
Now, work backward from the end position. We know the end position can reach the end.
For each position, determine if you can reach the end based on its odd and even jump locations.
If an odd jump from the current position leads to a spot that *can* reach the end, then the current position *can* also reach the end using an odd jump first.
Similarly, If an even jump from the current position leads to a spot that *can* reach the end, then the current position *can* also reach the end using an even jump first.
Keep track of which positions can reach the end via odd jumps and even jumps.
Finally, check if the starting position can reach the end via an odd jump. The answer to the problem is how many starting positions can reach the end via the first odd jump.

Code Implementation

def odd_even_jump(array) -> int:
    array_length = len(array)
    odd_jump_reachable = [False] * array_length
    even_jump_reachable = [False] * array_length
    odd_jump_reachable[array_length - 1] = True
    even_jump_reachable[array_length - 1] = True

    def find_next_jump(is_odd):
        sorted_indices = sorted(range(array_length), key=lambda i: (array[i], -i if is_odd else i))
        next_jump = [0] * array_length
        stack = []
        for index in sorted_indices:
            while stack and index > stack[-1]:
                next_jump[stack.pop()] = index
            stack.append(index)
        return next_jump

    odd_jumps = find_next_jump(True)
    even_jumps = find_next_jump(False)

    # Work backwards to determine reachability
    for i in range(array_length - 2, -1, -1):

        # If an odd jump is possible, check reachability from there
        if odd_jumps[i] != 0:
            odd_jump_reachable[i] = even_jump_reachable[odd_jumps[i]]

        # If an even jump is possible, check reachability from there
        if even_jumps[i] != 0:
            even_jump_reachable[i] = odd_jump_reachable[even_jumps[i]]

    # Count starting positions that can reach the end via an odd jump
    reachable_count = sum(odd_jump_reachable)
    return reachable_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through each of the n positions in the input array. Inside the loop, it uses sorted data structures (TreeMap or similar) to efficiently find the next higher and next lower values, representing the odd and even jumps, respectively. The operations on these sorted data structures (insertion, search) take O(log n) time. Since these O(log n) operations are performed for each of the n positions, the overall time complexity is O(n log n).

Space Complexity

O(N) – The solution uses two boolean arrays, odd and even, each of size N, to store whether a position can reach the end with an odd or even jump, respectively. Additionally, a sorted array of indices is created, which can also take up to O(N) space. Therefore, the auxiliary space used is proportional to the input size N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return 0 as there are no jumps possible, indicating no starting index leads to the end.
Single element array	Return 1, as the single element is considered a 'good' starting index.
Array with all identical values	The next higher and next lower values will all point to the same index if one exists, potentially causing repeated jumps to the same location.
Array sorted in ascending order	The odd jumps will always go to the next element, and the even jumps may never find a suitable smaller value to jump to.
Array sorted in descending order	The even jumps will always go to the next element, and the odd jumps may never find a suitable larger value to jump to.
Large array size (performance)	Use efficient data structures and algorithms (e.g., TreeMap, dynamic programming) to avoid exceeding time limit.
Integer overflow when calculating indices or distances	Ensure calculations do not overflow by using appropriate data types or modulo operations where relevant.
No possible path to the end of the array	The algorithm should correctly identify that no index can reach the end and return the correct number of 'good' indices.