Java Solution Time Complexity: O(n)

#1 
public class Solution {
    public ArrayList<Integer> solve(ArrayList<Integer> a) {
        HashMap<Integer, LinkedList<Integer>> hm= new HashMap<>();
        for(int i=0; i<a.size(); i++) {
            int x=a.get(i);
            if(hm.containsKey(x)) {
                LinkedList< Integer> ll = hm.get(x);
                if(ll.size()==0) {
                    ll.add(x);
                    continue;
                }
                int ix=ll.get(0);
                a.set(ix, x+1);
                ll.remove();
                ll.addLast(i);
                if(hm.containsKey(x+1)) {
                    LinkedList< Integer> l = hm.get(x+1);
                    if(l.size()==0) {
                        l.add(x+1);
                        continue;
                    }
                    for(int j=0; j<l.size(); j++) {
                        if(l.get(j)>=ix) {
                            l.add(j, ix);
                            break;
                        }
                    }
                } else {
                    LinkedList< Integer> l = new LinkedList<>();
                    l.add(ix);
                    hm.put(x+1, l);
                }
            } else {
                LinkedList< Integer> l = new LinkedList<>();
                l.add(i);
                hm.put(x, l);
            }
        }
        return a;
    }
}