CompProg, Kapitel 2.2

2.2 Next greater element

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{array}{r} NGE (i) := {\begin{cases} min {i + 1 \leq j < n | A [j] > A [i]} & if such a j exists \\ n & else. \end{cases} \end{array}

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 2.2.1 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 < 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 2.2.2 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] > 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 < 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{array}{r} i, NGE (i), NGE (NGE (i)), NGE (NGE (NGE (i))), \dots, n . \end{array}$ 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] < 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 2.2.1 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 < k < 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{array}{r} (because j < NGE (i)) & A [j] \leq A [i] \\ (because k = NGE (i)) & A [i] < A [k] \end{array}$ and thus, by transitivity $A [j] < 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]$ . $◻$

Problem 2.2.3 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.