Find next greater element for subset

You are given two integer arrays `query` and `nums`. - All elements in `nums` are distinct. - Every element in `query` also appears in `nums`. For each value `x` in `query`, find the **next greater element** of `x` in `nums`: the first element to the right of `x`'s position in `nums` that is strictly greater than `x`. If no such element exists, return `-1` for that `x`. Return an array `ans` of the same length as `query`, where `ans[i]` is the next greater element for `query[i]`. Example: - `query = [4, 1, 2]`, `nums = [1, 3, 4, 2]` → `ans = [-1, 3, -1]` ### Bounded Array Version For the method `Solution.nextGreaterElement(nums1, nums2)`, use `nums1` as `query` and `nums2` as `nums`. The result has exactly the same meaning as above, with these explicit input guarantees: - `1 <= len(nums1) <= len(nums2) <= 1000`. - All values are integers from `0` through `10000`, inclusive. - Values are unique within each array, and every value in `nums1` occurs in `nums2`. - Both arrays use zero-based indexing. Return the greater **value**, not its index or the distance to it, in `nums1` order. The uniqueness requirement for `nums1` belongs to this bounded version. The original `query` wording above does not prohibit repeated queries; repeating a query simply repeats its answer. No wrapping from the right edge to the left is allowed in either version. For `nums1 = [2, 4]` and `nums2 = [1, 2, 3, 4]`, return `[3, -1]`. For `nums1 = [2]` and `nums2 = [2, 5, 3]`, return `[5]`: the first greater value is 5 even though a smaller greater value appears later. ### Clarifying Questions - Does “next” mean the closest greater value by magnitude? No; it means the first qualifying position to the right. - Can an answer come from the left of the queried position? No, and the array is not circular. - Must the returned array follow the query order? Yes, including queries with no greater element, whose result is `-1`. ### What a Strong Answer Covers - Finds the first strictly greater value on the right for each query. - Handles decreasing arrays, the final position, and reordered queries correctly. - Explains why no earlier qualifying position is skipped and accounts for total work across both arrays. ### Follow-up Questions Can you solve the bounded version in `O(len(nums1) + len(nums2))` time?