Solution that extends the idea of next greater element in an array using stack


  • 0
    S

    This might not be the best solution but extends the idea of normal application of stack to find next greater element in an array

        /** Two traversal approach
         *  First traversal: Find next greater using stack
         *  Second Traversal: If the stack is empty, if the element at the top is less than current element, pop and include in result
         */
        public int[] nextGreaterElements(int[] nums) {
            Stack<Integer> s = new Stack<Integer>();
             int []result = new int[nums.length];
            for (int i = 0; i<nums.length;i++){
                
                if (s.isEmpty()||nums[s.peek()]>=nums[i]) s.push(i);
                else{
                    while (!s.isEmpty()&&nums[i]>nums[s.peek()]){
                        result[s.pop()] = nums[i];
                    }
                    s.push(i);
                }
            }
            if (s.isEmpty()){
                return result;
            }
            else{
                for (int i = 0; i<nums.length && !s.isEmpty();i++){
                
                    if (nums[s.peek()]>=nums[i]) continue;
                    else{
                           while (!s.isEmpty()&&nums[i]>nums[s.peek()]){
                            result[s.pop()] = nums[i];
                        } 
                    }
                    
                }
            }
            while(!s.isEmpty()){
                        result[s.pop()] = -1;
            }
            return result;
        }
    

Log in to reply
 

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