Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0496 - Next Greater Element I
    0496 - Next Greater Element I
    0496 - Next Greater Element I
    0496 - Next Greater Element I

    0496 - Next Greater Element I

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/next-greater-element-i/

    Solution 1 - Brute Force

    For each element in nums1, find it in nums2, then scan to the right in nums2 for the first element greater than it. If no greater element is found, return -1 for that position.

    TimeComplexity:O(n⋅m)TimeComplexity: O(n \cdot m)TimeComplexity:O(n⋅m)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Monotonic Stack with Hash Map

    Iterate through nums2 and use a monotonic decreasing stack. For each element, while it is greater than the top of the stack, pop from the stack and record the current element as the next greater element in a hash map. Then look up results for each element in nums1.

    TimeComplexity:O(n+m)TimeComplexity: O(n + m)TimeComplexity:O(n+m)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0496.1 - Next Greater Element I - Solution 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """Next Greater Element Function"""
        result = []

        for num in nums1:
            found = False
            greater = -1
            for n in nums2:
                if n == num:
                    found = True
                elif found and n > num:
                    greater = n
                    break
            result.append(greater)

        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().nextGreaterElement([4, 1, 2], [1, 3, 4, 2]))  # [-1, 3, -1]
    print(Solution().nextGreaterElement([2, 4], [1, 2, 3, 4]))     # [3, -1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0496.2 - Next Greater Element I - Solution 2 - Monotonic Stack with Hash Map """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """Next Greater Element Function"""
        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(num, -1) for num in nums1]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().nextGreaterElement([4, 1, 2], [1, 3, 4, 2]))  # [-1, 3, -1]
    print(Solution().nextGreaterElement([2, 4], [1, 2, 3, 4]))     # [3, -1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()