Next Greater Element Using Stack in DSA Python - Time & Space Complexity

Time Complexity: Next Greater Element Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed changes when we find the next greater element for each item in a list using a stack.

How does the number of steps grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def next_greater_element(arr):
    stack = []
    result = [-1] * len(arr)
    for i, value in enumerate(arr):
        while stack and arr[stack[-1]] < value:
            index = stack.pop()
            result[index] = value
        stack.append(i)
    return result

This code finds the next greater number for each element in the list using a stack to keep track of indices.

Identify Repeating Operations

• Primary operation: The for-loop goes through each element once, and the while-loop pops elements from the stack when the current element is greater.
• How many times: Each element is pushed and popped at most once, so the total number of stack operations is at most 2n.

How Execution Grows With Input

As the list size grows, each element is handled a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 stack operations
100	About 200 stack operations
1000	About 2000 stack operations

Pattern observation: The operations grow roughly in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly in proportion to the number of elements in the list.

Common Mistake

[X] Wrong: "The nested while-loop makes this algorithm O(n²) because it looks like a loop inside a loop."

[OK] Correct: Each element is pushed and popped only once, so the total work inside the while-loop across the whole run is limited to n operations, not n².

Interview Connect

Understanding this pattern helps you solve many problems efficiently by using stacks to track previous elements, a skill often valued in coding challenges.

Self-Check

What if we changed the input to a linked list instead of an array? How would the time complexity change?