# LeetCode 975: Odd Even Jump

## Problem Restatement

We are given an integer array `arr`.

From any starting index, we make jumps to the right. The jumps are numbered by jump count:

| Jump number | Type |
|---|---|
| `1st`, `3rd`, `5th`, ... | Odd jump |
| `2nd`, `4th`, `6th`, ... | Even jump |

For an odd jump from index `i`, we must jump to an index `j` such that:

```python
i < j
arr[i] <= arr[j]
```

Among all possible `j`, choose the one with the smallest possible `arr[j]`. If there is a tie, choose the smallest index `j`.

For an even jump from index `i`, we must jump to an index `j` such that:

```python
i < j
arr[i] >= arr[j]
```

Among all possible `j`, choose the one with the largest possible `arr[j]`. If there is a tie, choose the smallest index `j`.

A starting index is good if we can reach the last index by following these rules.

Return the number of good starting indices.

The official constraints are `1 <= arr.length <= 2 * 10^4` and `0 <= arr[i] < 10^5`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `arr` |
| Output | Number of good starting indices |
| Odd jump | Jump to the smallest value greater than or equal to current value |
| Even jump | Jump to the largest value less than or equal to current value |
| Tie rule | If values tie, use the smallest index |

Example function shape:

```python
def oddEvenJumps(arr: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
arr = [10, 13, 12, 14, 15]
```

Output:

```python
2
```

The good starting indices are `3` and `4`.

From index `3`, the first odd jump goes to index `4`.

Index `4` is already the last index, so it is good.

Example 2:

```python
arr = [2, 3, 1, 1, 4]
```

Output:

```python
3
```

The good starting indices are `1`, `3`, and `4`.

Example 3:

```python
arr = [5, 1, 3, 4, 2]
```

Output:

```python
3
```

The good starting indices are `1`, `2`, and `4`.

## First Thought: Simulate From Every Index

A direct idea is to start from every index and simulate jumps.

For each jump, we search all later indices to find the required destination.

For odd jumps, search for the smallest value greater than or equal to `arr[i]`.

For even jumps, search for the largest value less than or equal to `arr[i]`.

This can be too slow.

There are `n` possible starts, and each jump search may scan `O(n)` elements. We need to precompute jump destinations efficiently.

## Key Insight

Separate the problem into two parts.

First, compute:

```python
next_odd[i]
```

the index reached by an odd jump from `i`.

Also compute:

```python
next_even[i]
```

the index reached by an even jump from `i`.

Then use dynamic programming:

```python
odd[i] = can reach the end from i when the next jump is odd
even[i] = can reach the end from i when the next jump is even
```

The last index is always good:

```python
odd[n - 1] = True
even[n - 1] = True
```

Then:

```python
odd[i] = even[next_odd[i]]
even[i] = odd[next_even[i]]
```

if those next jumps exist.

## Computing Next Odd Jumps

For odd jumps, we need the smallest value to the right that is greater than or equal to `arr[i]`.

If multiple indices have that same value, choose the smallest index.

We can compute this with sorting and a monotonic stack.

Sort indices by:

```python
(arr[i], i)
```

This puts smaller values first. For equal values, smaller indices come first.

Then use a stack to assign next greater-or-equal destinations.

When we scan sorted indices, if the current index is greater than the stack top, then the current index is the correct next odd jump for that stack-top index.

## Computing Next Even Jumps

For even jumps, we need the largest value to the right that is less than or equal to `arr[i]`.

Sort indices by:

```python
(-arr[i], i)
```

This puts larger values first. For equal values, smaller indices come first.

Then use the same monotonic stack process.

This assigns next lower-or-equal destinations.

## Helper Idea

The same helper can compute next jumps from an ordering of indices.

```python
def make_next(indices):
    stack = []
    result = [-1] * n

    for index in indices:
        while stack and index > stack[-1]:
            result[stack.pop()] = index
        stack.append(index)

    return result
```

Why this works:

The sorted order guarantees value priority.

The stack logic guarantees the destination is to the right and has the smallest possible index among valid destinations.

## Algorithm

1. Let `n = len(arr)`.
2. Build `next_odd`:
   - Sort indices by `(arr[i], i)`.
   - Run the monotonic stack helper.
3. Build `next_even`:
   - Sort indices by `(-arr[i], i)`.
   - Run the same helper.
4. Create arrays:

```python
odd = [False] * n
even = [False] * n
```

5. Set:

```python
odd[n - 1] = True
even[n - 1] = True
```

6. Process indices from right to left:
   - If `next_odd[i] != -1`, set `odd[i] = even[next_odd[i]]`.
   - If `next_even[i] != -1`, set `even[i] = odd[next_even[i]]`.
7. Return the number of `True` values in `odd`.

We count `odd` because the first jump from a starting index is jump number `1`, which is odd.

## Correctness

The sorted-index helper computes the correct odd and even jump destinations.

For odd jumps, sorting by `(arr[i], i)` considers candidate destinations in increasing value order, and for equal values in increasing index order. Therefore, the first valid right-side candidate assigned to an index is exactly the required smallest value greater than or equal to `arr[i]`, with the smallest index tie-break.

For even jumps, sorting by `(-arr[i], i)` considers candidate destinations in decreasing value order, and for equal values in increasing index order. Therefore, the first valid right-side candidate assigned to an index is exactly the required largest value less than or equal to `arr[i]`, with the smallest index tie-break.

After jump destinations are known, the dynamic programming recurrence is direct. If the next jump from index `i` is odd, we must go to `next_odd[i]`, and after that the next jump is even. So `odd[i]` is true exactly when `even[next_odd[i]]` is true. The even case is symmetric.

The last index is reachable from itself with no further jumps, so both `odd[n - 1]` and `even[n - 1]` are true.

Since the DP processes indices from right to left and every jump goes to a larger index, all needed future states are already computed. Therefore, `odd[i]` correctly tells whether starting at `i` can reach the end. Counting true values in `odd` gives exactly the number of good starting indices.

## Complexity

Let `n = len(arr)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting indices dominates |
| Space | `O(n)` | Next-jump arrays, DP arrays, and stack |

## Implementation

```python
class Solution:
    def oddEvenJumps(self, arr: list[int]) -> int:
        n = len(arr)

        def make_next(indices: list[int]) -> list[int]:
            result = [-1] * n
            stack = []

            for index in indices:
                while stack and index > stack[-1]:
                    result[stack.pop()] = index

                stack.append(index)

            return result

        odd_order = sorted(range(n), key=lambda i: (arr[i], i))
        even_order = sorted(range(n), key=lambda i: (-arr[i], i))

        next_odd = make_next(odd_order)
        next_even = make_next(even_order)

        odd = [False] * n
        even = [False] * n

        odd[-1] = True
        even[-1] = True

        for i in range(n - 2, -1, -1):
            if next_odd[i] != -1:
                odd[i] = even[next_odd[i]]

            if next_even[i] != -1:
                even[i] = odd[next_even[i]]

        return sum(odd)
```

## Code Explanation

The helper builds next-jump destinations:

```python
def make_next(indices: list[int]) -> list[int]:
```

It receives indices in the correct value order.

The stack stores indices whose jump target has not been found yet:

```python
stack = []
```

When the current index is to the right of the stack top:

```python
while stack and index > stack[-1]:
    result[stack.pop()] = index
```

the current index becomes that previous index's jump destination.

For odd jumps:

```python
odd_order = sorted(range(n), key=lambda i: (arr[i], i))
```

This handles smallest greater-or-equal value and smallest index tie-break.

For even jumps:

```python
even_order = sorted(range(n), key=lambda i: (-arr[i], i))
```

This handles largest smaller-or-equal value and smallest index tie-break.

The DP arrays mean:

```python
odd[i]
even[i]
```

whether we can reach the end from index `i` when the next jump is odd or even.

The last index is always reachable:

```python
odd[-1] = True
even[-1] = True
```

Then we fill states from right to left:

```python
for i in range(n - 2, -1, -1):
```

If an odd jump exists:

```python
odd[i] = even[next_odd[i]]
```

If an even jump exists:

```python
even[i] = odd[next_even[i]]
```

Finally:

```python
return sum(odd)
```

counts good starting indices.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.oddEvenJumps([10, 13, 12, 14, 15]) == 2
    assert s.oddEvenJumps([2, 3, 1, 1, 4]) == 3
    assert s.oddEvenJumps([5, 1, 3, 4, 2]) == 3

    assert s.oddEvenJumps([1]) == 1
    assert s.oddEvenJumps([1, 2, 3, 4]) == 2
    assert s.oddEvenJumps([4, 3, 2, 1]) == 1
    assert s.oddEvenJumps([2, 2, 2]) == 3
    assert s.oddEvenJumps([1, 3, 2, 4, 5]) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[10,13,12,14,15]` | Main example |
| `[2,3,1,1,4]` | Duplicate values and tie handling |
| `[5,1,3,4,2]` | Mixed odd and even jumps |
| `[1]` | Last index is good by default |
| Increasing array | Only some starts can alternate successfully |
| Decreasing array | Only last index is good |
| All equal values | Every index can jump to the next index |
| Mixed increasing values | Checks DP propagation |