Skip to content

975. Odd Even Jump

Problem

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.

Solution

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.

Algorithms

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.

Code

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]:
                dq.pop()
            if len(dq) > 0:
                larger[i] = dq[-1]
            dq.append(i)

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

        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)