Next Greater Element I
Task example: Next Greater Element I
For each value in nums1, locate it in nums2 and return the first strictly larger value to its right. Return -1 if none exists. Keep the answers in nums1 order.
nums1 = [4,1,2], nums2 = [1,3,4,2] answer = [-1,3,-1]
Both arrays contain unique integers, and nums1 is a subset of nums2. The task allows 1 ≤ m ≤ n ≤ 1000 and values from 0 to 10000. The demo accepts up to 24 values per array.
View LeetCode 496Brute force: video explanation
nums1 = [4,1,2], nums2 = [1,3,4,2] answer = [-1,3,-1]
Prefer reading? Follow the steps below.
- For each x in nums1, find its position in nums2. Start j one position to the right.
- Skip values that are not greater than x. Stop at the first greater value and append it, or append -1 if j reaches the end.
- For query 1, the answer is 3, not 4: we need the first larger value to the right, not the largest. Queries 4 and 2 return -1.
Time complexity · O(mn)
Let m = len(nums1) and n = len(nums2). Finding a position and scanning to the right take O(n) per query, giving O(mn) worst-case time.
Space complexity · O(1)
O(1) extra space excludes the required O(m) answer list. Including the output, total space is O(m).
Monotonic stack + map: video explanation
nums1 = [4,1,2], nums2 = [1,3,4,2] answer = [-1,3,-1]
Prefer reading? Follow the steps below.
- Scan nums2 once. Keep unresolved values on a stack, decreasing from bottom to top. Unique values let us use a value as a dictionary key.
- For each new x, pop smaller values from the top and record greater[previous] = x. Then push x. The first larger value arriving resolves each pending value.
- Look up each query in nums1 order. Use -1 for missing keys. Here the map has 1 → 3 and 3 → 4, so queries [4,1,2] return [-1,3,-1].
Unlike repeated brute-force searches, the stack resolves each value once. The map separates scan order from query order.
Time complexity · O(m + n)
O(m + n) time with average O(1) dictionary operations: each nums2 value is pushed once and popped at most once, followed by m lookups.
Space complexity · O(n)
The stack and map use O(n) extra space in total, excluding the O(m) output list.