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.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

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

Constraints:

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

Follow up: Could you find an O(nums1.length + nums2.length) solution?

Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3 ! number of elements in nums1
    integer, parameter :: m = 4 ! number of elements in nums2
    integer, dimension(n) :: nums1 = [4, 1, 2] ! subset of nums2
    integer, dimension(m) :: nums2 = [1, 3, 4, 2]
    integer, dimension(n) :: ans

    call solve(nums1, nums2, ans)

    write (*, '(A)') 'ans = ', ans

contains

    subroutine solve(nums1, nums2, ans)
        implicit none
        integer, intent(in) :: nums1(:), nums2(:)
        integer, intent(out) :: ans(:)
        integer :: i, j, k

        do i = 1, size(nums1)
            j = 1
            k = 1
            do while (k <= size(nums2))
                if (nums1(i) == nums2(k)) then
                    exit
                end if
                k = k + 1
            end do
            if (k > size(nums2)) then
                ans(i) = -1
            else
                ans(i) = nums2(k+1)
            end if
        end do
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module next_greater_element
implicit none
contains
function next_greater_element(nums1, nums2) result(ans)
integer, intent(in) :: nums1(:), nums2(:)
integer :: ans(size(nums1))
! Initialize the answer array with -1
ans = -1
! Loop through the elements of nums1
do i = 1, size(nums1)
! Find the index of the current element in nums2
j = index(nums2, nums1(i))
! If the element is not found, continue to the next iteration
if (j == 0) cycle
! If the element is found, check if there is a greater element to the right
if (j < size(nums2) .and. nums2(j+1) > nums2(j)) then
! If there is a greater element to the right, set the answer
ans(i) = nums2(j+1)
else
! If there is no greater element to the right, set the answer to -1
ans(i) = -1
endif
enddo
end function
end module

program test
use next_greater_element
implicit none
integer, parameter :: nums1(3) = [4, 1, 2]
integer, parameter :: nums2(4) = [1, 3, 4, 2]
integer :: ans(size(nums1))
ans = next_greater_element(nums1, nums2)
write (*,*) ans
end program
🌐 Data from online sources 
def next_greater_element(nums1, nums2):
    next_greater = {}
    stack = []

    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    return [next_greater.get(n, -1) for n in nums1]

The algorithm uses a stack, following these steps: 1. Initialize an empty stack. 2. Iterate through nums2 elements: a. While the stack is not empty and the top of the stack is less than the current nums2 element, add the next greater element of the top of the stack as the current nums2 element and pop it. b. Push the current nums2 element into the stack. 3. For every element in nums1, get the next greater element found in step 2 or -1 if no such element was found. 4. Return the result array.

The key point is using the stack to keep track of the previous elements that still need to find their next greater element while iterating nums2 in a single pass. This ensures that the algorithm runs in linear O(n) time complexity.

🌐 Data from online sources 
#include <vector>
#include <stack>
#include <unordered_map>

std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::unordered_map<int, int> nextGreater;
    std::stack<int> stk;

    for (int num : nums2) {
        while (!stk.empty() && stk.top() < num) {
            nextGreater[stk.top()] = num;
            stk.pop();
        }
        stk.push(num);
    }

    std::vector<int> result(nums1.size());
    for (size_t i = 0; i < nums1.size(); ++i) {
        result[i] = nextGreater.count(nums1[i]) ? nextGreater[nums1[i]] : -1;
    }

    return result;
}

The algorithm uses a stack, following these steps: 1. Initialize an empty stack. 2. Iterate through nums2 elements: a. While the stack is not empty and the top of the stack is less than the current nums2 element, add the next greater element of the top of the stack as the current nums2 element and pop it. b. Push the current nums2 element into the stack. 3. For every element in nums1, get the next greater element found in step 2 or -1 if no such element was found. 4. Return the result array.

The key point is using the stack to keep track of the previous elements that still need to find their next greater element while iterating nums2 in a single pass. This ensures that the algorithm runs in linear O(n) time complexity.