Efficient algorithm to replace list of integers with nearest bigger element

Question

The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of toString().

Given an unsorted list of integers, design a O(n) algorithm to transform the list such that the integers are replaced by the next bigger integer on their right. If there is no bigger integer on its right, the integer remains the same.

For example [2,1,4,5,3,6,7,9,4,8] becomes [4,4,5,6,6,7,9,9,8,8].

I have come out with an algorithm after a long time, but a recent test case reveals that my algorithm doesn't cover all cases. Here is my attempt written in Java. Can anyone suggest the algorithm for this problem?

Answer 1

The issue is how to find "the next bigger integer on their right", which sounds like a stack operation.

Here is the algorithm in its essence.

1. Create an empty stack.
2. Iterate over the given list of integers from left to right.
   1. Push the current integer to the stack.
   2. While the top of the stack is smaller than the next integer in the list, replace the integer in the list that corresponds to the top of the stack by that next integer in the list followed by popping the stack.

The idea of the algorithm is to let the stack store the integers for which we have not found their next bigger integers yet, in the natural order in which they have been examined. Those integers will be strictly decreasing.

---

In the actual implementation, in order to locate the integer in the given list that corresponds to the top of the stack, the indices of the integers should be stored in the stack instead of the integer themselves.

Here is code in Python:

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

For readers who does not use Python, s[-1] is the last element of the list s.

---

Since each index of the given list is appended once and popped at most once and the last index is not even included, the time-complexity of the algorithm is $O(n)$, where $n$ is the length of the given list.