To see the question, click here.

Naive Approach

The idea is to iterate through each element in nums1 and then search for this element in nums2. Once found, look for the next greater element in nums2 by scanning the elements following the found element. If a greater element is found, update the corresponding position in the result array ans. If no greater element is found after the current element in nums2, the default value -1 remains in the result array for that position.

// TC: O(n*m) where n is the length of nums1 and m is the length of nums2
// SC: O(n)

import java.util.Arrays;

public class NextGreaterElementI {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        Arrays.fill(ans, -1);

        for (int i = 0; i < nums1.length; i++) {
            int curr = nums1[i];

            for (int j = 0; j < nums2.length; j++) {
                if (curr == nums2[j]) {
                    int nextGreat = curr;
                    for (int k = j + 1; k < nums2.length; k++) {
                        if (nums2[k] > nextGreat) {
                            nextGreat = nums2[k];
                            break;
                        }
                    }
                    if (nextGreat == curr) {
                        break;
                    }

                    ans[i] = nextGreat;
                    break;
                }
            }
        }

        return ans;
    }

    public static void main(String args[]) {
        NextGreaterElementI nge = new NextGreaterElementI();
        int[] nums1 = { 4, 1, 2 };
        int[] nums2 = { 1, 3, 4, 2 };
        int[] ans = nge.nextGreaterElement(nums1, nums2);
        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}

Performance

The time complexity of the nextGreaterElement method is O(n*m), where n is the length of nums1 , and m is the length of nums2. This is because, for each element in nums1, we iterate through nums2 to find the next greater element. The space complexity is O(n), where n is the length of nums1. This is because we create an array of size nums1.length to store the next greater elements.

Refined Approach

Instead of using those many variables, let us use a boolean flag found to indicate when we've located the element from nums1 in nums2. Once found, we continue iterating through nums2 to find the next greater element, and if found, we update ans and break out of the loop.

// TC: O(n*m) where n is the length of nums1 and m is the length of nums2
// SC: O(n)

import java.util.Arrays;

public class NextGreaterElementI {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        Arrays.fill(ans, -1);

        for (int i = 0; i < nums1.length; i++) {
            boolean found = false;
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    ans[i] = nums2[j];
                    break;
                }
            }
        }

        return ans;
    }

    public static void main(String args[]) {
        NextGreaterElementI nge = new NextGreaterElementI();
        int[] nums1 = { 4, 1, 2 };
        int[] nums2 = { 1, 3, 4, 2 };
        int[] ans = nge.nextGreaterElement(nums1, nums2);
        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}

Performance

The time complexity of the nextGreaterElement method is O(n*m), where n is the length of nums1 , and m is the length of nums2. This is because there are two nested loops, one iterating through nums1 and the other through nums2. The space complexity is O(n). This is because the ans array has the same length as nums1, and no additional data structures are used.

Efficient Approach

Let us use the concept of monotonic stack to solve this problem. The idea is pretty simple. For each element in nums2, we check if it is greater than the elements currently in the stack (which represent elements we've seen but haven't found a next greater element for yet). If so, we pop those elements from the stack and record the current element as their next greater element in a hash map. We then push the current element onto the stack. After processing all elements in nums2, the hash map will contain the next greater element for each element in nums2. When we iterate through nums1, we look up each element in the hash map to find its next greater element, defaulting to -1 if it doesn't have one.

// TC: O(n+m) where n is the length of nums1 and m is the length of nums2
// SC: O(n)

import java.util.HashMap;
import java.util.Stack;

public class NextGreaterElementI {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> nextGreater = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                nextGreater.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = nextGreater.getOrDefault(nums1[i], -1);
        }

        return ans;
    }

    public static void main(String args[]) {
        NextGreaterElementI nge = new NextGreaterElementI();
        int[] nums1 = { 4, 1, 2 };
        int[] nums2 = { 1, 3, 4, 2 };
        int[] ans = nge.nextGreaterElement(nums1, nums2);
        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}

The time complexity of this code is O(n + m), where n is the length of nums1, and m is the length of nums2. This is because we iterate through both arrays once to populate the nextGreater map and then iterate through nums1 to retrieve the corresponding values. The space complexity is O(m) because we use a HashMap to store the next greater element for each element in nums2 and a Stack to keep track of elements in nums2.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.