Leetcode – Next Greater Element I Solution in Python

Next Greater Element I is an intriguing problem that combines elements of array manipulation and stack data structures. Understanding and solving this problem is essential for grasping similar patterns in more complex questions. In this elaborate article, we will dissect the problem statement, explore different methods to tackle this problem in Python, and assess their complexities.

Problem Statement:

You are given two arrays (without duplicates) nums1 and nums2. For each element in nums1, find the next greater element in the nums2 array. The Next Greater Element of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number among the second array, so output -1.
    For number 1 in the first array, the next greater number is 3.
    For number 2 in the first array, there is no next greater number, so output -1.

Naive Approach: Brute Force

The most straightforward approach is to, for each element in nums1, traverse nums2 to find the next greater element.

def nextGreaterElement(nums1, nums2):
    result = []
    
    for num in nums1:
        index_in_nums2 = nums2.index(num)
        next_greater = -1
        
        for j in range(index_in_nums2 + 1, len(nums2)):
            if nums2[j] > num:
                next_greater = nums2[j]
                break
                
        result.append(next_greater)
    
    return result

This brute force approach has a time complexity of O(n*m), where n is the size of nums1 and m is the size of nums2.

Efficient Approach: Using Stack

An efficient approach involves using a stack data structure. The idea is to iterate through nums2 and keep pushing elements onto the stack until we find a number that is greater than the top of the stack. For each element in nums2, we check if the stack is non-empty and the current element is greater than the top of the stack. If both conditions are true, it means we have found the next greater element for the number at the top of the stack.

def nextGreaterElement(nums1, nums2):
    next_greater_map = {}
    stack = []
    
    # Building a map for next greater elements
    for num in nums2:
        while stack and num > stack[-1]:
            next_greater_map[stack.pop()] = num
        stack.append(num)
    
    # Constructing the result based on the map
    result = [next_greater_map.get(num, -1) for num in nums1]
    
    return result

This approach has a significantly better time complexity of O(n+m) due to the stack manipulation and the construction of a map for next greater elements.

Additional Insights:

The problem may initially seem trivial and one might be tempted to solve it using the brute force approach. However, the stack-based approach is an elegant solution that efficiently builds a map of next greater elements for all numbers in nums2. This demonstrates the importance of being familiar with different data structures and their properties, as they can often be the key to solving problems more efficiently.

Conclusion:

The Next Greater Element I problem is an excellent example to illustrate how the proper use of data structures, in this case, a stack, can significantly optimize the solution to a problem. It highlights the importance of understanding the characteristics and functionalities of different data structures and how they can be employed to simplify and streamline the solution.