Skip to content

975. Odd Even Jump


The core problem is: given an array of integers, for each number, find the smallest number on the right which is larger than it. Use the nearest if there is a tie.


If there is no smallest requirement, it is a monotonic stack problem. (Find the nearest one larger than the current one.) We can treat each element as a tuple of (index, value). We sort these tuples by value first, then index if tie. We got a new array. Now the problem becomes find the nearest element on the right whose index is larger than the current on the new array. It is solvable with monotonic stack. As long as it is the nearest, we have ensured it is the smallest larger one and the nearest in the original array.


Monotonic stack

Find the nearest one on the right, which is larger than the current one. The farther ones in the stack should be larger, the nearer ones should be smaller. So every element in the stack should either be large or be near. At least have one merit.


import collections

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        dq = collections.deque()
        acs = sorted([(value, i) for i, value in enumerate(A)])
        dcs = sorted([(-value, i) for i, value in enumerate(A)])
        larger = [-1] * len(A)
        smaller = [-1] * len(A)

        for value, i in acs[::-1]:
            while len(dq) > 0 and i > dq[-1]:
            if len(dq) > 0:
                larger[i] = dq[-1]

        for value, i in dcs[::-1]:
            while len(dq) > 0 and i > dq[-1]:
            if len(dq) > 0:
                smaller[i] = dq[-1]

        f = [[False] * len(A), [False] * len(A)]
        f[0][len(A) - 1] = f[1][len(A) - 1] = True
        # 0 is even, 1 is odd.
        for i in range(0, len(A) - 1)[::-1]:
            if smaller[i] != -1:
                f[0][i] = f[1][smaller[i]]
            if larger[i] != -1:
                f[1][i] = f[0][larger[i]]
        return f[1].count(True)