Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2454.html

2454. Next Greater Element IV

  • Difficulty: Hard.
  • Related Topics: Array, Binary Search, Stack, Sorting, Heap (Priority Queue), Monotonic Stack.
  • Similar Questions: Next Greater Element I, Replace Elements with Greatest Element on Right Side.

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, C++, Python)

  • class Solution {
        public int[] secondGreaterElement(int[] nums) {
            Deque<Integer> stk = new ArrayDeque<>();
            PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
            int n = nums.length;
            int[] ans = new int[n];
            Arrays.fill(ans, -1);
            for (int i = 0; i < n; ++i) {
                int v = nums[i];
                while (!q.isEmpty() && q.peek()[0] < v) {
                    ans[q.peek()[1]] = v;
                    q.poll();
                }
                while (!stk.isEmpty() && nums[stk.peek()] < v) {
                    q.offer(new int[] {nums[stk.peek()], stk.pop()});
                }
                stk.push(i);
            }
            return ans;
        }
    }
    
  • using pii = pair<int, int>;
    
    class Solution {
    public:
        vector<int> secondGreaterElement(vector<int>& nums) {
            stack<int> stk;
            priority_queue<pii, vector<pii>, greater<pii>> q;
            int n = nums.size();
            vector<int> ans(n, -1);
            for (int i = 0; i < n; ++i) {
                int v = nums[i];
                while (!q.empty() && q.top().first < v) {
                    ans[q.top().second] = v;
                    q.pop();
                }
                while (!stk.empty() && nums[stk.top()] < v) {
                    q.push({nums[stk.top()], stk.top()});
                    stk.pop();
                }
                stk.push(i);
            }
            return ans;
        }
    };
    
  • class Solution:
        def secondGreaterElement(self, nums: List[int]) -> List[int]:
            stk = []
            q = []
            ans = [-1] * len(nums)
            for i, v in enumerate(nums):
                while q and q[0][0] < v:
                    ans[q[0][1]] = v
                    heappop(q)
                while stk and nums[stk[-1]] < v:
                    heappush(q, (nums[stk[-1]], stk.pop()))
                stk.append(i)
            return ans
    
    
  • func secondGreaterElement(nums []int) []int {
    	stk := []int{}
    	q := hp{}
    	n := len(nums)
    	ans := make([]int, n)
    	for i := range ans {
    		ans[i] = -1
    	}
    	for i, v := range nums {
    		for len(q) > 0 && q[0].v < v {
    			ans[q[0].i] = v
    			heap.Pop(&q)
    		}
    		for len(stk) > 0 && nums[stk[len(stk)-1]] < v {
    			heap.Push(&q, pair{nums[stk[len(stk)-1]], stk[len(stk)-1]})
    			stk = stk[:len(stk)-1]
    		}
    		stk = append(stk, i)
    	}
    	return ans
    }
    
    type pair struct{ v, i int }
    
    type hp []pair
    
    func (h hp) Len() int { return len(h) }
    func (h hp) Less(i, j int) bool {
    	a, b := h[i], h[j]
    	return a.v < b.v
    }
    func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
    func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
    func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
    

Explain:

nope.

Complexity:

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

All Problems

All Solutions