What is the time and space complexity of Next Greater Element I?

Time complexity: O(n + m). Space complexity: O(n).

Next Greater Element I

Easy

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Next Greater Element I

Approach

Process nums2 with a monotonic decreasing stack. When current value is greater than stack top, it becomes the next greater element for popped values. Store this in a map, then answer nums1 queries from the map.

Complexity Analysis

Time: O(n + m)
Space: O(n)

Pattern

Monotonic Stack + Hash Map

Why It Works

The stack keeps values waiting for a larger element. The first value that pops them is their nearest greater element to the right.

Updated Mar 2026