Array next element

Problem

Given an integer array replace each number with its next minimum number in the array. For example if input array is {3,4,2,6,5,1,8,4} output would be{2,2,1,5,1,0,4,0}

Brute force

Create a new array of same size. For each element start scanning the element from its immediate next index, till you first find a smaller element. In this way the complexity is O(n^2) and extra space of size n is used.

Better Solution

We will scan the array from right side to left side. We will maintain a stack to keep track of the next smaller elements. Starting from right we will take a number and try to put that number in the stack. We will always put the number on smaller numbers. So as long as stack top element is bigger than the given number we will keep popping the stack. At some point either a smaller element will appear or stack will become empty. At this point we will replace the array element with the top element of the stack or put zero if the stack is empty. This way we will try to put the number on stack then replace the number in the array and keep on moving from right to left. the complexity of this approach will be O(n). We can prove it by saying that we will only handle one number once in the array and the stack can not have more than n pop or n push.

Code

import java.util.LinkedList;

public class NextSmallInteger
{

 /**
  * given an array form another array where each element of previous
  * array is replaced with its next minimum number in the array
  * @param args
  */
 public static void main(String[] args)
 {
  int[] input={3,4,5,2,7,5,7,3,8,2,5,7,9,1,3};
  int[]output=new int[input.length];
  LinkedList<Integer> stack=new LinkedList<Integer>();
  for(int i=input.length-1;i>=0;--i)
  {
   int currentNum=input[i];
   if(stack.peek()==null)
   {
    output[i]=0;
    stack.push(currentNum);
    continue;
   }
   while(stack.size()!=0 && stack.peek()>=currentNum)
   {
    stack.pop();
   }
   output[i]=stack.peek()==null?0:stack.peek();
   stack.push(currentNum);
  }
  for(int i=0;i < output.length;++i)
  {
   System.out.print(output[i]+",");
  }
 }

}

Index