Next greater element in an array
Given an array of integers(positive or negative), print the next greater element of all elements in the array. If there is no greater element then print null.
Next greater element of an array element array[i], is an integer array[j], such that
1. array[i] is less than array[j]
2. i is less than j
3. j - i is minimum
i.e. array[j] is the first element on the right of array[i] which is greater than array[i].
Algorithm 1 (Naive):
For every element, iterate over array elements on the right to find the first element which is greater than the current element.
If the end of array is reached, then next greater element for the current element is null.
Time Complexity: O(n^2)
Space Complexity: O(1)
Algorithm 2 (Optimized):
Traverse the array once.
1: If the stack is empty or array[i] is less than stack.top, push the array[i] on the stack.
2: While array[i] is greater than stack.top,
Pop top element & print 'Next Greater Element of top is array[i]'.
3: Push array[i] on the stack.
4: Repeat steps 2-3 till the end of array is reached.
5: Finally, print null as next greater element for all remaining stack elements.
Time Complexity: O(n)
Space Complexity: O(n)
Code and Algorithm Visualization: http://www.ideserve.co.in/learn/next-...
Website: http://www.ideserve.co.in
Facebook: / ideserve.co.in
