Skip to main content

496. Next Greater Element I

easy

For each element of one array, find the next greater element in a second array. The cleanest monotonic-stack drill — and the foundation for harder NGE variants.

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

Problem

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1. Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

Examples

Example 1

Input
nums1 = [4,1,2], nums2 = [1,3,4,2]
Output
[-1,3,-1]

Explanation: The next greater element for each value of nums1 is as follows: - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2

Input
nums1 = [2,4], nums2 = [1,2,3,4]
Output
[3,-1]

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force is O(n*m). Acceptable for the constraints, but the interviewer is looking for monotonic stack.

Hint 2

Precompute a map from value to its next greater element by scanning nums2 once with a monotonic decreasing stack.

Hint 3

While scanning nums2, the elements on the stack are still 'waiting' for their next greater. As soon as you see a value larger than the top, pop it and record value -> larger.

Hint 4

Final pass: for each value in nums1, look it up in the map; default to -1.

Solution approach

Reveal approach

Two phases. Phase 1: build a hash map 'nextGreater' from value to its next greater in nums2. Scan nums2 left to right with a monotonic decreasing stack of values. For each x: while the stack is non-empty and stack.top() < x, pop top y and record nextGreater[y] = x. Push x. Anything still on the stack at the end has no next greater. Phase 2: map nums1's values through the dictionary, defaulting to -1 for entries not in the map. Total O(n + m) time and O(n) space — n = len(nums2), m = len(nums1). This is the warm-up for circular-array and 2D variants.

Complexity

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

Related patterns

  • stack
  • monotonic-stack
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Next Greater Element I and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →