Question: Find out next increasing value of each element in this below array.
int[] array = { 5, 2, 7, 10, 4, 12}
e.g)
5's nextIncreasingValue: 7
2's nextIncreasingValue: 7
7's nextIncreasingValue: 10
...
12's nextIncreasingValue: -1
Implementation:
for(int i = 0; i < array.length; i++) {
int nextIncreasingValue = -1;
for (int j = i + 1; j < array.length; j++) {
if(array[j] > array[i]) {
nextIncreasingValue = array[j];
break;
}
}
PRINT("For " + i + "th next increasing value is: " + j)
}
Now I want to know the time complexity of this program, since each time inner for loop is skipping some of the elements on iteration. So it cannot be O(n^2) even in the worst case.
Kindly explain me what will be the time complexity?
O(n) Solution using stack:
Stack s = new Stack();
for(int i = 0; i < array.length; i++) {
while(!s.isEmpty() && array[i] > s.peek()) {
PRINT s.pop() NIV is array[i];
}
s.push(array[i]);
}
while(!s.isEmpty())
PRINT s.pop() NIV is -1;