In an unsorted array, replace every element by the first larger element to the right

Question

In an unsorted array, we have to replace every element by the first element to the right that is larger than the current element. If none of the elements to the right are bigger then it should be replaced with -1.

Example:

3  1  2  5  9  4  8   should be converted to
5  2  5  9 -1  8 -1

I can think of the trivial solution where we check every element with the entire array which is an Ο(n²) solution. Is there a better way to do this?

Answer 1

The main idea is to process the array in reverse order (from right to left). We make a few observations:

• If we are currently processing index i, k > j > i and A[k] ≤ A[j], then we call element k irrelevant, because it will never be the result for any of the elements 1, 2, ..., k
• The relevant elements right of an index i therefore form a monotonically strictly increasing subsequence of A[i+1..n-1].

In your example, the sequences of relevant elements would be from right to left:

       []    
      [8]
    [4,8]
      [9]
    [5,9]
  [2,5,9]
  [1,5,9]

It looks like a stack, and we can indeed use a stack to maintain this sequence between iterations.

When processing a new element, we first need to find the result for the array element. The observation is that the result is the topmost element on the stack that is not invalidated by the new element. Therefore we can just pop from the stack all elements that have become irrelevant. What is then on the top is our result. We can then push the new element because it is relevant by our definition.

stack = []
A = [3, 1, 2, 5, 9, 4, 8]
result = [-1]*len(A)
for i := len(A) - 1 to 0:
    # remove all elements made irrelevant by A[i]
    while not stack.empty() && stack.top() <= A[i]:
        stack.pop()
    # now the top of the stack is the result for index i
    if not stack.empty():
        R[i] = stack.top()
    # push the new element on the stack. The stack will still contain all relevant 
    # elements in increasing order from top to bottom
    stack.push(A[i])

The loop invariant for iteration i is "stack contains the subsequence of relevant elements to the right of index i". It is easy to verify and implies the correctness of this algorithm.

Every element is pushed and popped at most once, so we have a total runtime of Ο(n).

Answer 2

you can use a stack and the time complexity is O(N).

algo: Start from the left side and move towards right. When you pick an element form the array (lets say x) pop the stack till the elements from stack (lets say y ) has element greater than the array element i.e. x> y. Than push the element i.e. x to stack.

e.g. {40,50,11,32,55,68,75} . here s is stack.

40, as s is empty push it. s: 40

50, as s.peek() < 50 so pop 40 (40's greater element is 50) than push 50. s: 50

Next higher element of 40 - 50.

11, s.peek() > 11 so push 11. s: 50, 11

32, s.peek() < 32, so pop the element and now it's 50 which is greater than 32 hence push 32. s: 50 ,32

Next higher element of 11 - 32.

55, s.peek() < 55, so pop the element i.e. 32 than pop next as well as 50 < 55, than push 55. s: 55.

Next higher element of 32 - 55.

Next higher element of 50 - 55.

68, s.peek() < 68 so pop it and push 68. s: 68

75, s.peek() < 75 so pop it and push 75 s:75.

Next higher element of 68 - 75.

As the array does not have any element no just pop the stack say that for all the elements inside the array does not have greater element i.e. -1.

Next higher element of 75 - -1.

The same algo in code:

public static void fun(int[] a) {
    Stack<Integer> s = new Stack<Integer>();
    s.push(a[0]);

    for (int i = 1; i < a.length; i++) {
        if (s.peek() != null) {
            while (true) {
                if (s.peek() == null || s.peek() > a[i]) {
                    break;
                }
                System.out.println(s.pop() + ":" + a[i]);
            }
        }
        s.push(a[i]);
    }
    while (s.peek() != null) {
        System.out.println(s.pop() + ":" + -1);
    }
}