Implement Stack with O(n) time

Question

Implement a stack data structure that supports push and pop operations with a time complexity of O(n). The stack should allow for the addition of elements to the top and the removal of elements from the top, while ensuring that the operations maintain the correct order of elements. Your implementation should include methods for pushing an element onto the stack and popping the top element off, returning the popped value.

Codemia · Accepted Answer

To implement a stack with O(n) time complexity for push and pop operations, we need to recognize that traditional stack implementations (using arrays or linked lists) usually allow O(1) time complexity for both operations. However, here, we are required to ensure that the order of elements is maintained after each operation, which implies that we will need to utilize an auxiliary data structure to achieve the desired behavior. The challenge is to implement the stack such that every push or pop operation involves potentially shifting elements, leading to O(n) complexity.

We can utilize a list to represent the stack and implement the push and pop operations such that each operation manages the order of elements. The approach is as follows:

1. **Initialization**: Create an empty list to represent the stack.
2. **Push Operation**: When pushing an element, append it to the end of the list. This operation will take O(1) time, but to meet the requirement, we will then reverse the list to maintain the correct order, which takes O(n).
3. **Pop Operation**: To pop an element, we will again reverse the list to ensure the top of the stack is the last element, remove that element, and reverse the list back to maintain the stack order. This will also take O(n) time.

For example, if we push elements 1, 2, and 3 sequentially, the list after each push would look like this:
- Push 1: [1]  → Reverse: [1]
- Push 2: [1, 2] → Reverse: [2, 1]
- Push 3: [2, 1, 3] → Reverse: [3, 2, 1]
Thus, popping will give us 3 first, maintaining the stack behavior.

Here is the Python implementation of the stack:

```python
class Stack:
    def __init__(self):
        self.stack = []

def push(self, value):
        self.stack.append(value)
        self.stack.reverse()  # Maintain order

def pop(self):
        if not self.stack:
            return None  # Handle empty stack
        top_value = self.stack.pop()
        self.stack.reverse()  # Maintain order
        return top_value

# Example Usage:
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # Output: 2
stack.push(3)
print(stack.pop())  # Output: 3
```

The time complexity for both push and pop operations is O(n) because we are reversing the list after each operation. The space complexity is O(n) as well because we are storing each element in the stack list. Given the constraints that the stack may contain up to n elements, this approach holds within acceptable limits.

1. **Empty Stack Pop**: Attempting to pop from an empty stack should return `None` or raise an appropriate exception. This ensures that we handle boundary conditions correctly.
2. **Multiple Pushes**: Pushing a large number of elements should still maintain the correct order without crashing, so we need to ensure that our implementation can handle the maximum expected input size.
3. **Single Element Operations**: Testing with a single element (push and pop) should return that element correctly and maintain the stack's behavior.

Implement Stack with O(n) time

Zscaler

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Zscaler Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string