Recording Smallest-So-Far Values in NumPy Array

Let's say I have a NumPy array like:

import numpy as np

x = np.array([1, 5, 4, 2, 3, 6, 7, 5, np.inf, np.inf, np.inf, 4, 2, 8, 3, 5, 9, 2, 3, 4])

And starting at i = 9, I want to traverse each element toward i = 0 and then to record the "smallest-so-far" numbers along the way along with the index of those numbers. In this example:

left_val = []
left_idx = []
min_so_far = np.inf
for i in range(9, -1, -1):
    if x[i] < min_so_far:
        left_val.append(x[i])
        left_idx.append(i)
        min_so_far = x[i]

The left min-so-far values are [5, 3, 2, 1] and they are located at indices [7, 4, 3, 0].

You can also traverse toward the right:

right_val = []
right_idx = []
min_so_far = np.inf
for i in range(9, x.shape[0]):
    if x[i] < min_so_far:
        right_val.append(x[i])
        right_idx.append(i)
        min_so_far = x[i]

The right min-so-far values are [4, 2] and they are located at index [11, 12]

Is there a faster way to do this min_so_far search when the length of x is much larger?

You can do something like this:

def right_mins(x):
    # To avoid leading infs, truncate some more
    start = np.argmax(np.isfinite(x))
    y = np.minimum.accumulate(x[start:])
    idx = np.r_[0, np.flatnonzero(np.diff(y)) + 1] + start
    return x[idx], idx

def left_mins(x):
    y, idx = right_mins(x[::-1])
    return y, x.size - 1 - idx

You can apply these functions directly to the slices that you want, e.g.:

>>> left_mins(x[:10])
(array([5., 3., 2., 1.]), array([7, 4, 3, 0]))
>>> n, i = right_mins(x[9:])
>>> n, i + 9
(array([4., 2.]), array([11, 12]))