# NO STACK: O(n) time complexity and O(1) space complexity using DP

• The idea is to use the array to be returned to store information rather than an extra Stack. We use the array called result to store index of next larger element and replace with actual values before returning it. In first iteration, we move from right to left and find next greater element assuming array to be non-cyclical. Then we do another iteration from right to left. This time, we assume array is cyclical and find next larger element for the elements that do not have next larger element if array is not cyclical.

``````public class Solution {
public int[] nextGreaterElements(int[] nums) {

//Case when array is empty
if(nums.length == 0) return nums;

int[] result = new int[nums.length];

//Assuming array to be non-cyclical, last element does not have next larger element
result[nums.length - 1] = -1;

//Case when only one element is there in array
if(result.length == 1) return result;

for (int i = nums.length - 2; i >= 0; i--){
//Starting from next element
int k = i + 1;

//Keep tracking next larger element until you find it or you find element with no next larger element
while(nums[i] >= nums[k] && result[k] != -1){
k = result[k];
}

//If next larger element is found, store index
if(nums[k] > nums[i]) result[i] = k;
else result[i] = -1;
}

//Second iteration assuming cyclical array, last element can also have next larger element
for (int i = nums.length - 1; i >= 0; i--){

//If next larger element assuming non-cyclical array already exists, continue
if(result[i] != -1) continue;

//Case when i + 1 is greater than length of array: when on last element
int k = (i + 1) % nums.length;

//Keep tracking next larger element until you find it or you find element with no next larger element
while(nums[i] >= nums[k] && result[k] != -1){
k = result[k];
}

//If next larger element is found, store it's index
if(nums[k] > nums[i]) result[i] = k;
else result[i] = -1;
}

//Replace indices with actual values
for(int i = 0; i < nums.length; i++){
if(result[i] != -1) result[i] = nums[result[i]];
}

return result;
}
}
``````

• @gaba.g26 Time Complexity is O(n^2) in worst case
Try with nums = {5,4,3,2,1,6} and see run time for
while(nums[i] >= nums[k] && result[k] != -1){
k = result[k];
}
it is O(n^2)

• Hi Ankit! This while loop will run 5 times in the iteration where I assume array to be non cyclical (first time) and 1 time when you run it assuming cyclical array (second time). So, O(N).

• @ankitjainb27 I tried this approach for similar problems and I think it is actually amortized O(n). To simplify, let's just work on a normal array, not circular.
For your example, the number of looks up when we run algorithm from right to left is {1, 1, 1, 1, 1, 1} since dp array allows us to only look to the right once.
A worse example is actually something like this {6, 1, 2, 3, 4, 5}. Since, for 6, we have to traverse right 5 times, but other elements only look up once they balance out.
Even if you add increasing or decreasing element to the left of 6, these new elements also need just 1 look up.
The worst example is something like sqrt(n) monotonically increasing subsequences of length sqrt(n) like {7, 8, 9, 4, 5, 6, 1, 2, 3}. Even then, each subsequence only have 1 element that need sqrt(n) look up, and sqrt(n) ^ 2 = n so once again the number of looks up balances out to O(n).
This is very informal so I would appreciate if anyone can help me do a formal evaluation/proof of this type of algorithm.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.