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 or equal to 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 two things: 1. It is the one with the smallest value that is >= to the current value since we sorted by values. 2. When there is a tie, it is the nearest in the original array since we sorted by index when value ties.

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)