Code to replace list of integers with nearest bigger element

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 but I’m not really confident whether it is considered $O(n)$ and where I can improve on if it really is $O(n)$. Can anyone provide me with some feedback?

import java.util.*;

class Main {
    public static void main(String [] args) {
        ArrayList<Integer> lst = new ArrayList<>(List.of(2,1,4,5,3,6,7,9,4,8));
        replace2(lst);
        System.out.println(lst);
    }

    //O(n^2) algorithm
    public static void replace(int [] arr) {
        for (int i=0;i< arr.length;i++) {
            for (int j=i;j<arr.length;j++) {
                if (arr[i]<arr[j]) {
                    arr[i]= arr[j];
                    break;
                }
            }
        }
    }

    //O(n) algorithm
    public static void replace2(ArrayList<Integer> lst) {
        int index = 0;
        int seen =0;
        for (int i=0;i< lst.size()-1;i++) {
            boolean isBroken = false;
            if (lst.get(i) >= lst.get(i+1)) {//if the adjacent element is larger, find for next biggest
                for (int j=i;j < lst.size(); j++) {
                    if (lst.get(j) > lst.get(i)) {
                        index = j;
                        seen = lst.get(j);
                        isBroken = true;
                        break;
                    }
                }
                if (isBroken) {//if we have found the next biggest
                    for (int k=index-1;k>i-1;k--) {
                        if (lst.get(k) < seen) {
                            if (lst.get(k) < lst.get(i)) {
                                lst.set(k,seen);
                            } else {
                                int temp = lst.get(k);
                                lst.set(k,seen);
                                seen = temp;
                            }
                        }
                    }
                }


            } else {//the adjacent element is already bigger
                lst.set(i,lst.get(i+1));
            }
        }
    }
}

As I already mentioned in a comment there’s a bug in your replace2:
input list 3,1,2,4 should result in 4,2,4,4 instead of all 4’s since the 2 is the first bigger number on the right of number 1

Going for a List just for debugging seems odd to me. If you want to print a list to console you can use Arrays.toString(myArray) which looks exactly the same as myList.toString(). If you use a decent IDE you should be able to see the values clearly as well at a breakpoint. (I use IntelliJ and I know there are other IDE’s that do this as well). In this case I would stick to using an array.

Since I currently only have java 8 installed for work I had a little trouble porting your program to java 8 to test it. The List.of() isn’t available yet and any workaround to quickly initialise an explicit ArrayList gave me trouble. I instead changed all your ArrayList types to the more general List and it works. There’s no reason to limit your method to ArrayList only.
Generally it’s better to code using the interface instead of an explicit implementation. If at some point you would want to use a LinkedList instead of an ArrayList for example you can’t use your current method.

Idea for a correct solution:
Loop through the list from right to left. Store the relevant larger numbers in a stack. At each step of the loop update the stack to only contain relevant larger numbers and replace the current element with the first (= smallest) larger element.

More concretely (try yourself first, use this if you’re still stuck):

public static void replaceStack(int[] input) {
    if (input.length < 2) {
        return; //empty or 1 element list are trivial
    }
    Deque<Integer> largerKnown = new LinkedList<>(); //Java Stack implementation
    largerKnown.add(input[input.length - 1]); //last element is never replaced
    for (int i = input.length - 2; i >= 0; i--) { //loop from second to last downwards
        while (first element of stack is smaller) {
            remove first element from stack
        }
        if (largerKnown.isEmpty()) {
            largerKnown.addFirst(input[i]);
        } else {
            update the input[i] and add the old value of input[i] to the front of the stack
        }
    }
}

You’ll still have to actually implement parts of this algorithm yourself. It shouldn’t be that hard.