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 elemen
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. \n```\npublic class Solution {\n    public int[] nextGreaterElements(int[] nums) {\n\n        //Case when array is empty\n        if(nums.length == 0) return nums;\n      \n        int[] result = new int[nums.length];\n\n        //Assuming array to be non-cyclical, last element does not have next larger element\n        result[nums.length - 1] = -1;\n\n        //Case when only one element is there in array     \n        if(result.length == 1) return result;\n\n        for (int i = nums.length - 2; i >= 0; i--){   \n            //Starting from next element\n            int k = i + 1;\n\n            //Keep tracking next larger element until you find it or you find element with no next larger element\n            while(nums[i] >= nums[k] && result[k] != -1){\n                k = result[k];\n            }\n            \n            //If next larger element is found, store index      \n            if(nums[k] > nums[i]) result[i] = k;\n            //If not found, it doesn't have next larger element\n            else result[i] = -1;\n        }\n        \n        //Second iteration assuming cyclical array, last element can also have next larger element\n        for (int i = nums.length - 1; i >= 0; i--){   \n\n            //If next larger element assuming non-cyclical array already exists, continue\n            if(result[i] != -1) continue;\n      \n            //Case when i + 1 is greater than length of array: when on last element\n            int k = (i + 1) % nums.length;\n\n            //Keep tracking next larger element until you find it or you find element with no next larger element\n            while(nums[i] >= nums[k] && result[k] != -1){\n                k = result[k];\n            }\n\n            //If next larger element is found, store it's index\n            if(nums[k] > nums[i]) result[i] = k;\n            //If not found, it doesn't have next larger element\n            else result[i] = -1;\n        }\n\n        //Replace indices with actual values\n        for(int i = 0; i < nums.length; i++){\n            if(result[i] != -1) result[i] = nums[result[i]];\n        }\n\n        return result;\n    }\n}\n```
[]