Posts Next Greater Element IV
Post
Cancel

Next Greater Element IV

Problem Description

You are given a 0-indexed array of non-negative integers nums. For each integer in nums, you must find its respective second greater integer.
The second greater integer of nums[i] is nums[j] such that:

  • j > i
  • nums[j] > nums[i]
  • There exists exactly one index k such that nums[k] > nums[i] and i < k < j.

If there is no such nums[j], the second greater integer is considered to be -1.

Return an integer array answer, where answer[i] is the second greater integer of nums[i].

leetcode

Solution

snapshot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    
    public int[] secondGreaterElement(int[] nums) {
        
        int n = nums.length;
        
        //nextGreater
        int nextGreater[] = new int[n];
        
        Stack<Integer> stack = new Stack<>();
        stack.push(n-1);
        
        //create nextGreater array (based on index) 
        for(int i=n-1; i>=0; i--){
            
            int current = i;
            
            while(!stack.isEmpty() && nums[current] >= nums[stack.peek()]){
                stack.pop();
            }
            
            if(stack.isEmpty()){
                nextGreater[i] = -1;
                stack.push(current);
            }else{
                nextGreater[i] = stack.peek();
                stack.push(current);
            }
            
        }
        
        int[] secondGreater = new int[n];
        for(int i=0; i<n; i++) secondGreater[i] = -1; //initialize
        
        for(int i=0; i<n; i++){
            
            if(nextGreater[i] == -1){
                secondGreater[i] = -1; continue;
            }
            
            //second greater will be after first greater element
            int j = nextGreater[i] + 1; 
            
            //look for second greater from j to n-1
            //if the element we are checking is less than arr[i], we directly move to next greater element of arr[j]
            while(j<n && j!=-1){
                if(nums[j] > nums[i]){
                    secondGreater[i] = nums[j];
                    break;
                }else{
                    j = nextGreater[j];
                }
            }
            
        }
        
        return secondGreater;
        
    }
    
}
This post is licensed under CC BY 4.0 by the author.