Algorithm to replace integers in array by the nearest bigger integer on their right

Question

How do you solve this problem in O(n) time?

Given an unsorted array of integers, design algorithms to transform the array such that the integers are replaced by the nearest bigger integer on their right. If there is no bigger integer on its right, the integer remains the same. For example, the following array of integers

2 1 4 5 3 6 7 9 4 8

should become

4 4 5 6 6 7 9 9 8 8

Answer 1

• Init Stack of integers

• From left to right.

• Pop from stack while element is smaller, and replace it with the current

• Add id of element to stack

Note that the stack will be strictly decreasing. And that each element is popped/added max 1 time. Hence O(N)

Example code in Python:

l = [2, 1, 4, 5, 3, 6, 7, 9, 4, 8]
s = [0]
for i in range(1, len(l)):
    while s and l[i] > l[s[-1]]:
        l[s.pop()] = l[i]
    s.append(i)