2454. Next Greater Element IV

Problem

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.

• For example, in the array [1, 2, 4, 3], the second greater integer of 1 is 4, 2 is 3, and that of 3 and 4 is -1.

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

  Example 1:

Input: nums = [2,4,0,9,6]
Output: [9,6,6,-1,-1]
Explanation:
0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2.
1st index: 9 is the first, and 6 is the second integer greater than 4, to the right of 4.
2nd index: 9 is the first, and 6 is the second integer greater than 0, to the right of 0.
3rd index: There is no integer greater than 9 to its right, so the second greater integer is considered to be -1.
4th index: There is no integer greater than 6 to its right, so the second greater integer is considered to be -1.
Thus, we return [9,6,6,-1,-1].

Example 2:

Input: nums = [3,3]
Output: [-1,-1]
Explanation:
We return [-1,-1] since neither integer has any integer greater than it.

  Constraints:

• 1 <= nums.length <= 105

• 0 <= nums[i] <= 109

Solution (Java)

class Solution {
    Stack<Integer> st = new Stack<>();
    public int[] secondGreaterElement(int[] nums) {
        st = new Stack<>();
        int arr[] = getNG(nums); 
        PriorityQueue<int[]> pq[] = new PriorityQueue[nums.length];

        for(int i = 0;i<nums.length;i++){
            pq[i] = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        }
        int[] res = new int[arr.length];

        for(int i = 0;i<nums.length;i++){            
            if(arr[i]==-1){
                res[i] = -1;
                continue;  
            } 
            pq[arr[i]].add(new int[]{nums[i],i});
        }

        st.clear();


        for(int i = arr.length-1;i>=0;i--){

            if(st.isEmpty()){
               while(!pq[i].isEmpty()){
                   res[pq[i].remove()[1]] = -1;
               } 
            }
            else{

                while(!pq[i].isEmpty()){
                    int[] x = pq[i].remove();

                    while(!st.isEmpty() && x[0]>=st.peek()){
                        st.pop();
                    }

                    if(st.isEmpty()){
                        res[x[1]] = -1;
                    }
                    else{
                        res[x[1]] = st.peek();
                    }
                }
            }
            st.push(nums[i]);
        }

        return res;
    }

    public int[] getNG(int[] arr){
        st.clear();
        int[] res = new int[arr.length];

        for(int i = arr.length-1;i>=0;i--){

            if(st.isEmpty()){
                res[i] = -1;
            }
            else{
                while(!st.isEmpty() && arr[st.peek()]<=arr[i]){
                    st.pop();
                }

                if(st.isEmpty()){
                    res[i] = -1;
                }
                else{
                    res[i] = st.peek();
                }
            }
            st.push(i);
        }
        return res;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).