Elements relationship in array

Input: A unsorted array of size n.
Output: An array of size n.
Relationship:Elements of input array and output array have 1:1 correspondence.Output[i] is equal to the input[j] (j>i) which is smaller than input[i] and jth is nearest to ith (i.e. first element which is smaller).If no such element exists for Input[i] then output[i]=0.

Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0

Algorithm :

Push first element to stack.
While iterating over the array,
if the element is smaller than stack top, push it to stack along with index.
if the element is larger than stack top, pop till current element
is smaller than stack top and for all the popped indices store the
current element.

time complexity: o(n)
space complexity: o(n)

The same technique is used to solve largest rectangle in a histogram

Solution :

getSortedArray(int[] IN) {

int n = IN.length;

int[] OUT = new int[n];

Stack stack = new Stack();

for (int i = n - 1; i >= 0; i--) {

while (!stack.isEmpty() && IN[i] <= (Integer) stack.peek()) { stack.pop(); } if (stack.isEmpty()) { OUT[i] = 0; stack.add(IN[i]); continue; } if (IN[i] > (Integer) stack.peek()) {

OUT[i] = (Integer) stack.peek();

stack.push(IN[i]);

continue;

}
}

}