previous most recent bigger element in array

Question

I try to solve the following problem. Given an array of real numbers [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1] for every element I need to find most recent previous bigger element in the array.

For example there is nothing bigger then first element (7) so it has NaN. For the second element (2) 7 is bigger. So in the end the answer looks like:

[NaN, 7, 7, NaN, 8, 8, 8, 8, 7, 4, 3, 1]. Of course I can just check all the previous elements for every element, but this is quadratic in terms of the number of elements of the array.

My another approach was to maintain the sorted list of previous elements and then select the first element bigger then current. This sounds like a log linear to me (am not sure). Is there any better way to approach this problem?

Answer 1

Here's one way to do it

create a stack which is initially empty
for each number N in the array
{
    while the stack is not empty
    {
        if the top item on the stack T is greater than N
        {
            output T (leaving it on the stack)
            break
        }
        else
        {
            pop T off of the stack
        }
    }
    if the stack is empty
    {
        output NAN
    }
    push N onto the stack
}

Taking your sample array [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1], here's how the algorithm would solve it.

stack           N             output  
-               7               NAN 
7               2               7
7 2             4               7
7 4             8               NAN
8               1               8
8 1             1               8
8 1             6               8
8 6             7               8
8 7             4               7
8 7 4           3               4
8 7 4 3         1               3

The theory is that the stack doesn't need to keep small numbers since they will never be part of the output. For example, in the sequence 7, 2, 4, the 2 is not needed, because any number less than 2 will also be less than 4. Hence the stack only needs to keep the 7 and the 4.

Complexity Analysis

The time complexity of the algorithm can be shown to be O(n) as follows:

1. there are exactly n pushes (each number in the input array is pushed onto the stack once and only once)
2. there are at most n pops (once a number is popped from the stack, it is discarded)
3. there are at most n failed comparisons (since the number is popped and discarded after a failed comparison)
4. there are at most n successful comparisons (since the algorithm moves to the next number in the input array after a successful comparison)
5. there are exactly n output operations (since the algorithm generates one output for each number in the input array)

Hence we conclude that the algorithm executes at most 5n operations to complete the task, which is a time complexity of O(n).

Answer 2

We can keep for each array element the index of the its most recent bigger element. When we process a new element x, we check the previous element y. If y is greater then we found what we want. If not, we check which is the index of the most recent bigger element of y. We continue until we find our needed element and its index. Using python:

a = [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1]
idx, result = [], []
for i, v in enumerate(a, -1):
    while i >= 0 and v >= a[i]:
        i = idx[i]
    idx.append(i)
    result.append(a[i] if i >= 0 else None)

Result:

[None, 7, 7, None, 8, 8, 8, 8, 7, 4, 3]

The algorithm is linear. When an index j is unsuccessfully checked because we are looking for the most recent bigger element of index i > j then from now on i will point to a smaller index than j and j won't be checked again.