Next greater element iv

Array Binary Search Stack Sorting Heap (Priority Queue) Monotonic Stack

41.5% acceptance

Feb 25, 2026

749

You are given a 0-indexed array of non-negative integers nums. For each integ er 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]. *

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn second_greater_element(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut ans = vec![-1i32; n];
    // s1: indices waiting for first greater
    // s2: indices that found first greater, waiting for second
    let mut s1: Vec<usize> = Vec::new();
    let mut s2: Vec<usize> = Vec::new();
    for i in 0..n {
      // Process s2: elements that already found first greater, now check second
      let mut tmp: Vec<usize> = Vec::new();
      while s2.last().map(|&j| nums[j] < nums[i]).unwrap_or(false) {
        let j = s2.pop().unwrap();
        ans[j] = nums[i];
      }
      // Process s1: elements that haven't found first greater yet
      while s1.last().map(|&j| nums[j] < nums[i]).unwrap_or(false) {
        tmp.push(s1.pop().unwrap());
      }
      // Elements in tmp found their first greater (nums[i]), now need second greater
      // Insert into s2 in correct order (s2 is also decreasing by value)
      while !tmp.is_empty() {
        s2.push(tmp.pop().unwrap());
      }
      s1.push(i);
    }
    ans
  }
}