Difficulty: EasyStack

Next Greater Element I

Problem in Plain English

For each value in nums1, find that same value in nums2 and report the first larger value to its right, or -1 when none exists. A single decreasing stack over nums2 answers every query in linear time.

Problem Statement

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.

The answer is the first larger value by position, not the largest value in the suffix or the smallest larger value. Follow-up: solve in $O(m + n)$ time, where m = nums1.length and n = nums2.length.

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]

4 has no greater element to its right in nums2. 1 is followed by 3. 2 sits at the end with nothing after it.

Example 2

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

2 is followed by 3. 4 is the last element, so nothing greater follows it.

Example 3

Input: nums1 = [0], nums2 = [0]
Output: [-1]

At the smallest valid size, the only value has no position to its right. Zero is an ordinary query value.

Example 4

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

For 2 and 1, the first larger value encountered is 5. Although 3 is smaller than 5 and larger than either query, it occurs later and is not the answer. The maximum value 5 has no greater value to its right.

Intuition

A value waits until the first larger value arrives to its right. In Example 1, 1 meets 3, then 3 meets 4; 4 and the final 2 never meet a larger value. Keep unresolved values in decreasing order on a stack: a new value can settle several smaller waiting values at once. Because all values are unique, a map keyed by value can later answer nums1 in its own order.

Approaches

Scan Each Target

Solution Details

Reveal Scan Each Target: intuition, complexity, and code

Intuition

For each query, first find its unique position in nums2, then scan positions strictly to its right until the first larger value appears. The direct search follows the definition, but repeats position searches and suffix scans for many queries.

Step-by-Step Logic

Create an empty answer array. For each target in nums1, find its position in nums2 by a left-to-right search; Example 1 locates 4 at index 2.
Initialize this query answer to -1, then inspect indices after the target in increasing order. For 4, index 3 holds 2, which is too small, so retain -1.
Stop immediately on the first value greater than the target. For 1 at index 0, index 1 holds 3, so record 3 without inspecting later candidates.
Append the answer and repeat for the next query. For 2 at index 3, the suffix is empty and the answer stays -1.
Return answers in nums1 order: [-1,3,-1]. Do not reorder them to match nums2.

Why It Works

Uniqueness and subset membership guarantee that the position search finds exactly the correct occurrence. The suffix scan visits every allowed candidate in increasing position order and no forbidden candidate. Before each visit, all earlier suffix values have failed the strict greater-than test. Therefore the first passing value is exactly the next greater element; if no value passes, none exists and -1 is correct. Appending one result per target preserves query order.

Dry Run

Scan Each Target: variable states at each step
Query	Phase / index	Value inspected	State / answer so far
4	locate j=0	1	not target; []
4	locate j=1	3	not target; []
4	locate j=2	4	found index 2; candidate -1
4	suffix j=3	2	2 is not greater; candidate -1
4	suffix exhausted	none	append -1; [-1]
1	locate j=0	1	found index 0; candidate -1
1	suffix j=1	3	3 is greater; stop and append; [-1,3]
2	locate j=0	1	not target; [-1,3]
2	locate j=1	3	not target; [-1,3]
2	locate j=2	4	not target; [-1,3]
2	locate j=3	2	found index 3; candidate -1
2	suffix empty; return	none	[-1,3,-1]

Complexity Analysis

Time Complexity

O(m \cdot n)

Space Complexity

O(1)

Let m = nums1.length and n = nums2.length. Each query can inspect up to n positions to locate its target and another n suffix positions, giving O(mn) worst-case time. Only counters and a candidate use extra storage, so auxiliary space is O(1); the returned result contains m integers and occupies O(m) space. Neither input is changed.

Code

Solution.java

1class Solution {2    public int[] nextGreaterElement(int[] nums1, int[] nums2) {3        int[] answer = new int[nums1.length];4        for (int i = 0; i < nums1.length; i++) {5            int index = 0;6            while (nums2[index] != nums1[i]) index++;7            int greater = -1;8            for (int j = index + 1; j < nums2.length; j++) {9                if (nums2[j] > nums1[i]) {10                    greater = nums2[j];11                    break;12                }13            }14            answer[i] = greater;15        }16        return answer;17    }18}

Hints

Hint 1

Each answer only depends on what sits to the right of the value inside nums2.

Hint 2

While scanning nums2 left to right, keep the values that have not yet met a greater element.

Hint 3

A decreasing stack plus a value-to-answer map resolves every query in one pass over nums2.

Edge Cases

A query for the last element of nums2, such as 2 in Example 1, always answers -1 since nothing follows it.
A strictly decreasing nums2 leaves every value unresolved, so every query answers -1.
A strictly increasing nums2 resolves every value immediately against its right neighbour.
Boundary values 0 and 10000 are legal; a membership test must not confuse zero with an absent key.
A single arrival can pop many waiting values, such as 5 after [2,1]; keep popping until the decreasing order is restored.

Common Mistakes and Interview Tips

Searching from the left of the value instead of strictly to its right, which can return an element that comes before it.
Accepting an equal value as the answer instead of requiring a strictly greater element.
Forgetting the -1 default for values that stay on the stack, which drops the queries with no greater element.
Popping only one smaller entry with if instead of while leaves earlier queries unresolved: in [2,1,5], arrival 5 settles both 1 and 2.
Returning the largest suffix value or the smallest larger value ignores position: [2,5,3] must give 5 for query 2.
Reusing a value-keyed map when duplicate values are allowed is unsafe; this problem guarantees uniqueness, while duplicate variants need index-based tracking.

Key Takeaway

A monotonic stack resolves next-greater questions in one pass: smaller values wait on the stack until the arrival that settles them.