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

Time Complexity: Next Greater Element Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the next greater element changes as the input size grows.

How does the algorithm handle larger arrays efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void nextGreaterElement(int arr[], int n, int result[]) {
    int stack[n];
    int top = -1;
    for (int i = n - 1; i >= 0; i--) {
        while (top != -1 && stack[top] <= arr[i]) {
            top--;
        }
        result[i] = (top == -1) ? -1 : stack[top];
        stack[++top] = arr[i];
    }
}
    

This code finds the next greater element for each item in the array using a stack.

Identify Repeating Operations

• Primary operation: A single loop running from the end to the start of the array.
• How many times: The loop runs once for each element, so n times.
• Inside the loop: The while loop pops elements from the stack, but each element is pushed and popped at most once.

How Execution Grows With Input

As the input size grows, each element is processed once, and stack operations happen at most once per element.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find the next greater element grows linearly with the number of elements.

Common Mistake

[X] Wrong: "The nested while loop makes this algorithm O(n²)."

[OK] Correct: Each element is pushed and popped only once, so the total work inside the while loops across all iterations is still proportional to n.

Interview Connect

Understanding this linear time stack approach shows you can solve problems efficiently by avoiding repeated work, a key skill in coding interviews.

Self-Check

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