LeetCode 496: Next Greater Element I Solution in Python – A Step-by-Step Guide

What Is LeetCode 496: Next Greater Element I?

In LeetCode 496: Next Greater Element I, you’re given two integer arrays: nums1 (a subset of nums2) and nums2. Your task is to find, for each element in nums1, the next greater element to its right in nums2—the first element larger than it—or return -1 if none exists. For example, with nums1 = [4, 1, 2] and nums2 = [1, 3, 4, 2], the result is [-1, 3, -1]: 4 has no greater element after it in nums2, 1’s next greater is 3, and 2’s is -1 (none after). It’s like searching a treasure trail for the next bigger prize, using one map to guide another.

Problem Statement

• Input:
• nums1 (List[int])—array of integers (subset of nums2).
• nums2 (List[int])—array of integers.
• Output: List[int]—next greater element in nums2 for each nums1 element, or -1 if none.
• Rules:
• For each x in nums1, find first y > x to its right in nums2.
• nums1 elements are unique and present in nums2.
• Return -1 if no greater element exists.

Constraints

• \( 1 \leq nums1.length \leq nums2.length \leq 1000 \).
• \( 0 \leq nums1[i], nums2[i] \leq 10^4 \).
• All integers in nums1 and nums2 are unique.
• All integers of nums1 appear in nums2.

Examples to Get Us Started

• Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
• Output: [-1,3,-1] (4 → -1, 1 → 3, 2 → -1).
• Input: nums1 = [2,4], nums2 = [1,2,3,4]
• Output: [3,-1] (2 → 3, 4 → -1).
• Input: nums1 = [1,2,3], nums2 = [1,2,3]
• Output: [-1,-1,-1] (No greater elements).

Understanding the Problem: Seeking the Next Prize

To solve LeetCode 496: Next Greater Element I in Python, we need to find, for each element in nums1, the next greater element to its right in nums2, returning -1 if none exists, leveraging that nums1 is a subset of nums2. A naive approach—searching rightward for each nums1 element—could be O(n * m) (n = nums1 length, m = nums2 length), slow for large arrays. The key? Use a monotonic stack to preprocess nums2 in O(m) time, mapping each element to its next greater, then look up nums1 values in O(n), achieving O(n + m) total time. We’ll explore:

• Best Solution (Monotonic Stack with Mapping): O(n + m) time, O(m) space—fast and optimal.
• Alternative Solution (Brute Force Search): O(n * m) time, O(1) space—simple but slow.

Let’s dive into the stack solution—it’s the seeker’s clever compass we need.

Best Solution: Monotonic Stack with Mapping

Why This Is the Best Solution

The monotonic stack with mapping is the top pick because it’s O(n + m) time (n = nums1 length, m = nums2 length) and O(m) space, efficiently solving the problem by using a stack to preprocess nums2 once, building a map of each element to its next greater element, then quickly looking up answers for nums1. It avoids repeated searches by leveraging the stack’s ability to track increasing elements. It’s like scanning the big map with a compass, marking each treasure’s next big find in one pass—smart and swift!

How It Works

Here’s the strategy:

• Step 1: Build next greater map for nums2:
• Use a stack to keep elements in increasing order.
• For each num in nums2:
• Pop stack while top < num, map top to num.
• Push num onto stack.
• Map remaining stack elements to -1.
• Step 2: Lookup nums1 in map:
• For each x in nums1, append map[x] to result.
• Step 3: Return result list.
• Why It Works:
• Stack ensures each element maps to first greater element rightward.
• Single pass over nums2, O(1) lookups for nums1.

Step-by-Step Example

Example: nums1 = [4,1,2], nums2 = [1,3,4,2]

• Step 1: Build map:
• Stack = [], map = {}.
• 1: Stack = [1].
• 3: 1 < 3, pop 1, map[1] = 3, push 3, Stack = [3].
• 4: 3 < 4, pop 3, map[3] = 4, push 4, Stack = [4].
• 2: 4 > 2, push 2, Stack = [4, 2].
• End: map[4] = -1, map[2] = -1.
• Map: {1: 3, 3: 4, 4: -1, 2: -1}.
• Step 2: Lookup:
• 4 → -1.
• 1 → 3.
• 2 → -1.
• Result: [-1, 3, -1].

Example: nums1 = [2,4], nums2 = [1,2,3,4]

• Map: {1: 2, 2: 3, 3: 4, 4: -1}.
• Lookup: 2 → 3, 4 → -1.
• Result: [3, -1].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Step 1: Build next greater map for nums2
        stack = []
        next_greater = {}

        for num in nums2:
            # Pop elements smaller than current
            while stack and stack[-1] < num:
                next_greater[stack.pop()] = num
            stack.append(num)

        # Remaining stack elements have no greater
        while stack:
            next_greater[stack.pop()] = -1

        # Step 2: Lookup nums1 in map
        result = [next_greater[num] for num in nums1]

        # Step 3: Return result
        return result

• Line 4-5: Init stack and map.
• Line 7-11: Process nums2:
• Pop smaller elements, map to current num.
• Push current num.
• Line 14-16: Map remaining stack to -1.
• Line 19: Build result via map lookup.
• Line 22: Return result.
• Time Complexity: O(n + m)—single pass over nums2, O(n) lookup.
• Space Complexity: O(m)—stack and map.

It’s like a treasure-mapping compass!

Alternative Solution: Brute Force Search

Why an Alternative Approach?

The brute force search—O(n * m) time, O(1) space—checks each nums1 element by searching rightward in nums2 for the next greater element, iterating until found or end reached. It’s slow but intuitive, like manually scanning the big map for each small map spot. Good for small arrays or learning!

How It Works

• Step 1: For each x in nums1:
• Find x’s index in nums2.
• Step 2: Search right from index:
• Return first y > x, or -1 if none.
• Step 3: Build result list.
• Step 4: Return result.

Step-by-Step Example

Example: nums1 = [4,1], nums2 = [1,3,4,2]

• x = 4: Index 2, next = 2 < 4, end → -1.
• x = 1: Index 0, next = 3 > 1 → 3.
• Result: [-1, 3].

Code for Brute Force

Copy codeclass Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        for x in nums1:
            # Find x in nums2
            i = nums2.index(x)
            # Search right
            found = False
            for j in range(i + 1, len(nums2)):
                if nums2[j] > x:
                    result.append(nums2[j])
                    found = True
                    break
            if not found:
                result.append(-1)
        return result

• Line 4-15: For each x, search right in nums2, append next greater or -1.
• Time Complexity: O(n * m)—n lookups, up to m searches each.
• Space Complexity: O(1)—result array aside.

It’s a slow map scanner!

Comparing the Two Solutions

• Monotonic Stack (Best):
• Pros: O(n + m), fast, scalable.
• Cons: O(m) space.
• Brute Force (Alternative):
• Pros: O(n * m), simple.
• Cons: Slow for large m.

Stack wins for efficiency.

Edge Cases and Examples

• Input: nums1=[1], nums2=[1] → [-1].
• Input: nums1=[2], nums2=[1,2] → [-1].
• Input: nums1=[1,2], nums2=[2,1] → [-1,-1].

Stack handles all perfectly.

Complexity Recap

• Stack: Time O(n + m), Space O(m).
• Brute Force: Time O(n * m), Space O(1).

Stack’s the champ.

Key Takeaways

• Stack: Map in one pass.
• Brute Force: Search each time.
• Python Tip: Stacks optimize—see [Python Basics](/python/basics).

Final Thoughts: Seek That Treasure

LeetCode 496: Next Greater Element I in Python is a treasure-seeking array adventure. Monotonic stack with mapping is your fast compass, while brute force is a slow scan. Want more array quests? Try LeetCode 503: Next Greater Element II or LeetCode 739: Daily Temperatures. Ready to find some greater elements? Head to Solve LeetCode 496 on LeetCode and seek it today—your coding skills are treasure-ready!