Next Greater Element

INTRODUCTION

The Next Greater Element problem is to find the next greater element for each element in an array. For each element in the array, we need to find the nearest element on the right side that is greater than the current element.

We can solve this problem using a stack data structure. The basic idea is to iterate through the array from right to left and maintain a stack of elements that are larger than the current element. We compare each element with the top of the stack and keep popping elements from the stack until we find a greater element or the stack becomes empty.

Here's the Python code to solve the Next Greater Element problem:

def next_greater_element(nums):
    stack = []  # Stack to store elements
    
    result = [-1] * len(nums)  # Initialize the result array with -1
    
    # Iterate through the array from right to left
    for i in range(len(nums)-1, -1, -1):
        # Pop elements from the stack until we find a greater element or the stack becomes empty
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If a greater element is found, store it in the result array
        if stack:
            result[i] = stack[-1]
        
        # Push the current element to the stack
        stack.append(nums[i])
    
    return result

Let's test the function with an example:

nums = [4, 3, 7, 2, 1, 5, 9, 8]
result = next_greater_element(nums)
print("Input:", nums)
print("Next Greater Elements:", result)

Output:

Input: [4, 3, 7, 2, 1, 5, 9, 8]
Next Greater Elements: [7, 7, 9, 5, 5, 9, -1, -1]

In this example, the input array is [4, 3, 7, 2, 1, 5, 9, 8]. The next greater elements for each element in the array are [7, 7, 9, 5, 5, 9, -1, -1].

The time complexity of this algorithm is O(n), where n is the length of the input array. We iterate through the array once, and each element is pushed and popped from the stack at most once. The space complexity is O(n) as we use a stack to store elements and the result array to store the next greater elements.

Here's an example of a LeetCode question that can be solved using the concept of Next Greater Element:

LeetCode Problem: 496. Next Greater Element I

Problem Description: You are given two arrays, nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, you need to find its next greater element in nums2.

The Next Greater Element I problem can be solved using the Next Greater Element concept we discussed earlier. Here's the Python code to solve this problem:

def next_greater_element(nums1, nums2):
    stack = []  # Stack to store elements and their next greater elements
    next_greater = {}  # Dictionary to store the next greater element for each element in nums2
    
    # Iterate through nums2 to find the next greater element for each element
    for num in nums2:
        # Pop elements from the stack and update their next greater element
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        # Push the current element to the stack
        stack.append(num)
    
    # For elements that do not have a next greater element, set their value to -1
    while stack:
        next_greater[stack.pop()] = -1
    
    # Find the next greater element for each element in nums1
    result = []
    for num in nums1:
        result.append(next_greater[num])
    
    return result

Let's test the function with an example:

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
result = next_greater_element(nums1, nums2)
print("nums1:", nums1)
print("nums2:", nums2)
print("Next Greater Elements:", result)

Output:

nums1: [4, 1, 2]
nums2: [1, 3, 4, 2]
Next Greater Elements: [-1, 3, -1]

In this example, nums1 is [4, 1, 2] and nums2 is [1, 3, 4, 2]. The next greater element for 4 is -1, for 1 is 3, and for 2 is -1.

The time complexity of this algorithm is O(n + m), where n is the length of nums1 and m is the length of nums2. We iterate through nums2 to find the next greater element for each element, which takes O(m) time. Then, we find the next greater element for each element in nums1, which takes O(n) time. The space complexity is O(m) as we use a stack and a dictionary to store elements and their next greater elements in nums2.