CareerCup

int[] replaceNextHigher(int[] arr) {
	int temp;
	for(int i=0; i< arr.length; i++) {
		temp = arr[i];
		for(int j=i+1;j<arr.length;j++) {
			if(arr[j] > temp) {
				arr[i] = arr[j];
				break;
			}
		}
	}
	return arr;
}

share my O(n) solution:

public static int[] replaceNextHigher(int[] nums){
        if(nums == null || nums.length<=1){
            return nums;
        }
        
        Deque<Integer> deque = new ArrayDeque<>();
        int[] array = new int[nums.length];
        for(int i = nums.length-1;i>=0;i--){
            if(i==nums.length-1){
                array[i]=nums[i];
                deque.offer(nums[i]);
            }else{
                
                while(!deque.isEmpty()&&nums[i]>=deque.peekFirst()){
                    deque.pollFirst();
                }
                if(deque.isEmpty()){
                    array[i] = nums[i];
                }else{
                    array[i]=deque.peekFirst();
                }
                deque.offerFirst(nums[i]);
            }
        }
        
        return array;
    }

public static void main(String args[]) throws Exception {
		int arr[] = { 1, 2, 3, 4, 9, 5, 6 };
		nextHigherElem(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static int[] nextHigherElem(int arr[]) {
		int op[] = new int[arr.length];
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = arr.length - 1; i >= 0; i--) {
			while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
				stack.pop();
			}
			if (!stack.isEmpty()) {
				op[i] = arr[stack.peek()];
			} else {
				op[i] = -1;
			}
			stack.push(i);
		}
		System.arraycopy(op, 0, arr, 0, arr.length);
		return arr;
	}

I m not sure why to use any exotic structures for this problem, I can think of the solution below:
a) Copy the whole array into a temporary array and sort it.
b) Iterate through each element in original array and do binary search in the sorted array to give last occurrence - not the element - but the occurrence i.e. index of the element in the sorted array. Then you get next bigger by sorted[ lastOccurrence + 1 ] if lastOccurrence < originalarray.length - 1.
Replace the original 's element with this one.

Complexity :
Space = O(n)
Time = O(nlogn) for sort
O(nlogn) for replace. - because for each i in n there is a binary search with log n time.

import java.util.Stack;
import java.util.Arrays;

public class NextHigher
{
	public static void main(String[] args)
	{
		int[] a = {10, 5, 2, 1, 4, 6, 7};
		//int[] a = {1, 2, 3};
		//int[] a = {5, 4, 3, 2, 1};
		//int[] a = {1, 1, 1};
		NextHigher n = new NextHigher();
		System.out.println(Arrays.toString(n.populateNextHigher(a)));
	}	

	public int[] populateNextHigher(int[] a)
	{
		Stack<Integer> stack = new Stack<>();
		int[] res = new int[a.length];
		for(int i = a.length-1;i>=0;i--)
		{
			if(stack.isEmpty())
			{
				stack.push(a[i]);
				res[i] = a[i];
			}
			else
			{
				while(!stack.isEmpty() && stack.peek()<a[i])
					stack.pop();
				if(!stack.isEmpty())
					res[i] = stack.peek();
				else
					res[i] = a[i];
				stack.push(a[i]);
			}
		}
		return res;
	}
}

@koustav.adorable. Looks like it doesn't work for 3, 7, 5.

We can build a Binary Search Tree, keeping mapping of idx_in_orig_array => node_in_bst.
Then, we iterate through the array. We remove the BST node of the i-th element in the array. We do a search in the BST to find the value which is next higher of the value of the i-th element. We replace the i-th element with the next higher value, if any. Then, we do the same for the next element.
Worst case time is O(N^2), because the BST can degrade into a list, and searching for the next higher value would be O(N). But expected time would be something like O(N log N).