Skip to content
AI360Xpert
Back to Stack
Easy

Next Greater Element I

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`.

Examples

Input:nums1 = [4,1,2], nums2 = [1,3,4,2]
Output:[-1,3,-1]
For 4 in nums1, there is no greater element in nums2. For 1, the next greater is 3. For 2, there is no greater element.

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.

Approach

For each element in `nums1`, find its index in `nums2`. Then, starting from that index in `nums2`, scan to the right to find the first element that is strictly greater than the current element. If found, add it to the result array; otherwise, add -1.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(1)

m is the length of nums1, n is the length of nums2.

Solution.java
class Solution {    public int[] nextGreaterElement(int[] nums1, int[] nums2) {        int[] res = new int[nums1.length];                for (int i = 0; i < nums1.length; i++) {            int target = nums1[i];            int nextGreater = -1;            boolean found = false;                        for (int j = 0; j < nums2.length; j++) {                if (nums2[j] == target) {                    found = true;                }                if (found && nums2[j] > target) {                    nextGreater = nums2[j];                    break;                }            }                        res[i] = nextGreater;        }                return res;    }}