Next Greater Element in Python (Time Complexity: O(n))

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.

Given an array of integers nums, return an array containing the indices of the next greater element for each number in nums.

If a number doesn't have a next greater element, denote that with -1.

Example 1:

Input: nums = [1, 3, 2, 4]
Output: [1, 3, 3, -1]
Explanation: The next greater element for each value of nums is as follows:
- next greater element for 1 is 3 which is located at index 1
- next greater element for 3 is 4 which is located at index 3
- next greater element for 2 is 4 which is located at index 3
- 4 is the last and doesn't have a next greater element so we mark it with -1

Example 2:

Input: nums = [7, 3, 2, 6, 11, 9, 8, 10, 13]
Output: [4, 3, 3, 4, 8, 7, 7, 8, -1]

Understanding the Problem

The core challenge of this problem is to efficiently find the next greater element for each element in the array. This problem is significant in various applications such as stock price analysis, where you might want to know the next higher price after a given day.

Potential pitfalls include misunderstanding the requirement to find the "first" greater element to the right and not just any greater element.

Approach

To solve this problem, we can use a stack to keep track of the indices of the elements for which we are trying to find the next greater element. This approach ensures that we only pass through the array once, achieving a time complexity of O(n).

Naive Solution

A naive solution would involve using two nested loops to compare each element with every other element to its right. This would result in a time complexity of O(n^2), which is not efficient for large arrays.

Optimized Solution

The optimized solution uses a stack to keep track of the indices of elements for which we haven't found the next greater element yet. As we iterate through the array, we compare the current element with the element at the index stored at the top of the stack. If the current element is greater, we pop the index from the stack and record the current index as the next greater element for that index. We continue this process until the stack is empty or the current element is not greater than the element at the index stored at the top of the stack. Finally, we push the current index onto the stack.

Algorithm

Initialize an empty stack and an array `result` of the same length as `nums`, filled with -1.
Iterate through the array `nums` using an index `i`.
While the stack is not empty and the current element `nums[i]` is greater than the element at the index stored at the top of the stack, pop the index from the stack and set `result` at that index to `i`.
Push the current index `i` onto the stack.
After the loop, any indices left in the stack do not have a next greater element, so they remain -1 in the `result` array.

Code Implementation

def next_greater_elements(nums):
    # Initialize the result array with -1
    result = [-1] * len(nums)
    # Initialize an empty stack
    stack = []
    
    # Iterate through the array
    for i in range(len(nums)):
        # While stack is not empty and the current element is greater than the element
        # at the index stored at the top of the stack
        while stack and nums[i] > nums[stack[-1]]:
            # Pop the index from the stack
            index = stack.pop()
            # Set the result for this index to the current index
            result[index] = i
        # Push the current index onto the stack
        stack.append(i)
    
    return result

# Example usage
nums1 = [1, 3, 2, 4]
print(next_greater_elements(nums1))  # Output: [1, 3, 3, -1]

nums2 = [7, 3, 2, 6, 11, 9, 8, 10, 13]
print(next_greater_elements(nums2))  # Output: [4, 3, 3, 4, 8, 7, 7, 8, -1]

Complexity Analysis

The time complexity of this approach is O(n) because each element is pushed and popped from the stack at most once. The space complexity is also O(n) due to the stack and the result array.

Edge Cases

Potential edge cases include:

An empty array, which should return an empty array.
An array with all elements in descending order, where all elements should have a next greater element of -1.
An array with all elements the same, where all elements should have a next greater element of -1.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with a few elements.
Cases with all elements in ascending or descending order.
Cases with duplicate elements.
Edge cases like an empty array or a single element array.

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

Understand the problem requirements and constraints thoroughly.
Think about the most efficient way to solve the problem, considering both time and space complexity.
Break down the problem into smaller parts and solve each part step by step.
Practice similar problems to improve problem-solving skills and familiarity with different algorithms.

Conclusion

Understanding and solving the "Next Greater Element" problem is crucial for developing efficient algorithms. By using a stack, we can achieve an optimal solution with a time complexity of O(n). Practicing such problems helps in honing problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice, consider the following resources: