Again we are given an array of integers. We want to compute, for each index $i$, the first index $j$ to the right of $i$ where the array contains a greater number. We call this the next greater element. Formally:

\begin{align*} \nge(i) := \begin{cases} \min \{i+1 \leq j \lt n \ | \ A[j] \gt A[i] \} & \textnormal{ if such a $j$ exists}\\ n & \textnormal{else. } \end{cases} \end{align*} Or, pictorially:

The array $\nge$ we want to compute should store a pointer for every $i$ to the first index to the right where we encounter a larger number:

Problem Given an array of integers, compute the NGE array as just described.

Input: a single line containing $n$ integers.

Output: a single line containing $n$ integers, namely $\nge(i)$ for each $0 \leq i \lt n$.

Sample Input:

8 6 4 8 9 13 6 8 9 7 5 8 11 4 5 12

Sample Output:

4 3 3 4 5 16 7 8 12 11 11 12 15 14 15 16

Test cases

Before starting to code, you should think of a handful of test cases (unless this is during an actual competition). Write them into a file and use them to test your algorithm later on.

Exercise Write test cases for this problem. In particular,

the above example;
an increasing array;
a decreasing array;

a program that generates somehow random instances. For example, like

python generate-random-test-cases.py 10 -20 20                                    
-9 18 19 -14 2 -10 12 -16 14 18

For each test case (except the large ones generated randomly), compute the answer by hand and write it into a file. Produce a pair file like increasing-array-length-11.in and increasing-array-length-11.out.

A quadratic algorithm

It should be simple to come up with a quadratic algorithm for this problem. Iterate $i=0,...,n-1$ and for each $i$, run a second loop $j=i+1,...,n$ to find the smallest $j \geq i+1$ with $A[j] \gt A[i]$.

def compute_nge(array):
    n = len(array)
    nge = [0] * n 
    for i in range(n):
        j = i+1
        while (j < n and array[j] <= array[i]):
            j = j+1
        nge[i] = j
    return nge

array = list(map(int, input().split()))
nge = compute_nge(array)

for j in nge:
    print(j, end=' ')
print()

A linear time algorithm

We scan the array from right to left. We keep a stack of indices $i$ with the following property: after having processed index $j$, the top element on the stack is $i$; if $k$ is on the stack and $k \lt n$, then the element below $k$ in the stack is $\nge(k)$. Thus, the first couple of elements on the stack (starting from the top) are \begin{align*} i, \nge(i), \nge(\nge(i)), \nge(\nge(\nge(i))), \dots, n \ . \end{align*} The stack always ends with $n$. For example, after having processed index $9$ in the above example, the stack should be $[9, 11, 12, 15,16]$ (with top of stack to the left).

How do we process a new index? For example, when processing $8$, we should now somehow find out that $\nge(8) = 12$. Note that $\nge(8)$ is on the stack, and it is the first element on the stack (counting from top) that is greater than $8$. In general, the idea is to pop elements from the stack until we find an index $j$ with $A[i] \lt A[j]$. It would then hold that $j = \nge(i)$ and we can now simply push $i$ on the stack.

The works if the $\nge$ of $i$ is in the stack.

Theorem If $i+1$ is the top element of the stack then $\nge(i)$ is in the stack.

Proof. Let $k = \nge(i)$. Now since both $i+1$ and $n$ are on the stack, if $k$ is not on the stack, then it is between two elements of the stack: $j \lt k \lt l$ with $j$ and $l$ on the stack and $l = \nge(j)$. Since $k = \nge(i)$ it holds that everything $A[i:k]$ is less or equal $A[i]$. In particular $A[j] \leq A[i]$. But then \begin{align*} A[j] \leq A[i] \tag{because $j \lt \nge(i)$} \\ A[i] \lt A[k] \tag{because $k = \nge(i)$} \end{align*} and thus, by transitivity $A[j] \lt A[k]$. This is a contradiction because $\nge(j) = l$ and thus all entries between $j$ and $l$ must be smaller than $A[j]$, including $A[k]$. $\square$

Problem Implement the above idea with a stack to achieve a linear time algorithm for the Next-Greater-Element problem.

Test your algorithm by comparing it to the solution computed by the quadratic implementation above.