Next Greater Element IV - Practice Coding Problems

Next Greater Element IV - Problem

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

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].

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,4,3]

› Output: [4,3,-1,-1]

💡 Note: For 1: greater elements are 2,4,3 → second greater is 4. For 2: greater elements are 4,3 → second greater is 3. For 4 and 3: no second greater element exists.

Example 2 — All Decreasing

$ Input: nums = [5,4,3,2,1]

› Output: [-1,-1,-1,-1,-1]

💡 Note: In a decreasing array, no element has a greater element to its right, so all results are -1.

Example 3 — All Increasing

$ Input: nums = [1,2,3,4,5]

› Output: [3,4,5,-1,-1]

💡 Note: For 1: greater are 2,3,4,5 → second is 3. For 2: greater are 3,4,5 → second is 4. For 3: greater are 4,5 → second is 5.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,2,4,3] with indices

Find Second Greater

For each element, find the second element greater than it

Result

Output [4,3,-1,-1] showing second greater for each

Key Takeaway

🎯 Key Insight: Use two monotonic stacks to track first and second greater elements efficiently in O(n) time

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use two monotonic stacks to efficiently track the first and second greater elements. The optimal approach uses two stacks to process elements in O(n) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Monotonic Stacks	O(n)	O(n)	Use two stacks to track first and second greater elements efficiently
Brute Force	O(n²)	O(1)	For each element, scan right to find the second greater element

Two Monotonic Stacks — Algorithm Steps

Step 1: Use stack1 to find next greater elements
Step 2: When popping from stack1, move to stack2
Step 3: When finding greater element for stack2, that's the second greater

Visualization

Tap to expand

Step-by-Step Walkthrough

Stack1 finds next greater

Maintain monotonic decreasing stack

Move to Stack2

When element is popped, move to second stack

Stack2 finds second greater

Second stack finds the final answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* nums, int numsSize, int* result) {
    int stack1[1000], top1 = -1;
    int stack2[1000], top2 = -1;
    
    for (int i = 0; i < numsSize; i++) {
        result[i] = -1;
        
        // Check stack2 for second greater elements
        while (top2 >= 0 && nums[i] > nums[stack2[top2]]) {
            int idx = stack2[top2--];
            result[idx] = nums[i];
        }
        
        // Check stack1 for next greater elements
        while (top1 >= 0 && nums[i] > nums[stack1[top1]]) {
            int idx = stack1[top1--];
            stack2[++top2] = idx;  // Move to stack2 to wait for second greater
        }
        
        stack1[++top1] = i;
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int result[1000];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    solution(nums, size, result);
    
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", result[i]);
        if (i < size - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each element pushed/popped from stacks at most once

✓ Linear Growth

Space Complexity

O(n)

Two stacks can hold up to n elements in worst case

⚡ Linearithmic Space

24.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Monotonic Stacks — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler