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


  • 7
    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;
        }
    }
    

  • 0
    A

    @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)


  • 0
    G

    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).


  • 0
    U

    @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.


Log in to reply
 

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