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


  • 5
    G

    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;
                //If not found, it doesn't have next larger element
                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;
                //If not found, it doesn't have next larger element
                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;
        }
    }
    

Log in to reply
 

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