Skip to main content

25. Next Greater Element IV

hardAsked at Confluent

For each index find the second next greater element to the right — Confluent uses it because monotonic-stack chaining mirrors backpressure handling across two log positions inside a Kafka partition.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a 0-indexed array nums, for each index i return the second strictly greater element to its right. If no such element exists, return -1 for that index.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Examples

Example 1

Input
nums=[2,4,0,9,6]
Output
[9,6,6,-1,-1]

Example 2

Input
nums=[3,3]
Output
[-1,-1]

Approaches

1. Brute force two scans per i

For every i walk right counting strict-greater elements; return the 2nd or -1.

Time
O(n^2)
Space
O(1)
for (let i=0;i<n;i++){let c=0,ans=-1; for(let j=i+1;j<n;j++) if(nums[j]>nums[i]){c++; if(c===2){ans=nums[j]; break;}} out[i]=ans;}

Tradeoff:

2. Two monotonic stacks

Maintain stack s (still looking for first greater) and stack t (already found first, looking for second). Pop from s into a buffer when the current beats it, then move buffer to t after iteration. Pop from t when current beats it and record result.

Time
O(n)
Space
O(n)
function secondGreaterElement(nums) {
  const n = nums.length, out = new Array(n).fill(-1);
  const s = [], t = [];
  for (let i = 0; i < n; i++) {
    while (t.length && nums[t[t.length-1]] < nums[i]) out[t.pop()] = nums[i];
    const buf = [];
    while (s.length && nums[s[s.length-1]] < nums[i]) buf.push(s.pop());
    while (buf.length) t.push(buf.pop());
    s.push(i);
  }
  return out;
}

Tradeoff:

Confluent-specific tips

Confluent loves when you connect the two-stack handoff to staged backpressure across partitions — call out that exactly-once semantics require both stacks be in the same state store so a consumer-group rebalance can't lose half the chain.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Next Greater Element IV and other Confluent interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →