Implement Stack with O(1) space

Question

Implement a stack data structure that supports push, pop, and top operations with O(1) space complexity. Your stack should be able to handle integer values and should provide methods to retrieve the top element and check if the stack is empty. Ensure that all operations are performed in constant time.

Codemia · Accepted Answer

In this problem, we need to implement a stack with operations that have O(1) time complexity and utilize O(1) space complexity. The stack must support the following operations: `push`, `pop`, and `top`, along with a method to check if the stack is empty. The challenge is to maintain the stack's behavior without using additional data structures that would increase space complexity. Utilizing a linked list or an array would typically require O(n) space for storing elements, which contradicts our space requirement. Instead, we can achieve this by leveraging the properties of the stack itself, particularly by manipulating the existing stack structure to allow for efficient access to the `top` element while ensuring that we don't exceed space constraints.

To implement the stack while adhering to the O(1) space complexity, we can use a single class to represent the stack. We will maintain a pointer to the top element of the stack and use a `top_value` variable to keep track of the last pushed value. This allows us to perform the `top` operation in constant time without needing to traverse the stack. Here’s a step-by-step breakdown:
1. **Initialization**: Create a class `Stack` with a constructor that initializes `top_value` and a pointer to the top node (let’s call it `top_node`).
2. **Push Operation**: When pushing a new value, we can create a new node and set its value to `top_value`. We then make this new node the new `top_node` and update `top_value` with the pushed value.
3. **Pop Operation**: To pop an element, we simply move the `top_node` pointer to the previous node (the one below the current top) and update `top_value` accordingly.
4. **Top Operation**: The `top` method will return the `top_value` directly.
5. **Is Empty Operation**: This will check if `top_node` is `None`.

Here's the Python implementation of the above approach:
```python
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.top_node = None
        self.top_value = None

def push(self, value):
        new_node = Node(value)
        new_node.next = self.top_node
        self.top_node = new_node
        self.top_value = value

def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        value = self.top_value
        self.top_node = self.top_node.next
        if self.top_node:
            self.top_value = self.top_node.value
        else:
            self.top_value = None
        return value

def top(self):
        if self.is_empty():
            raise IndexError("Top from empty stack")
        return self.top_value

def is_empty(self):
        return self.top_node is None
```
This implementation ensures all operations are performed in O(1) time and uses O(1) space.

The time complexity for all operations (push, pop, top, and is_empty) is O(1) since these operations involve a constant number of steps regardless of the number of elements in the stack. The space complexity is also O(1) as we are not using any additional data structures that grow with the number of elements. The only space used is for the node objects, which are part of the stack structure itself and do not count against our space complexity requirement.

Several edge cases must be considered:
1. **Pop from an empty stack**: This should raise an `IndexError` to signify that we cannot remove an element from an empty stack.
2. **Top on an empty stack**: Similar to pop, this should also raise an `IndexError` to indicate that there’s no element to retrieve.
3. **Multiple operations**: Ensure that after multiple pushes and pops, the `top` and `is_empty` methods still function correctly. For example, pushing several elements and then popping all should leave the stack empty and return the correct top values during operations.

Implement Stack with O(1) space

Databricks

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

Databricks 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