Problem

Implement 3 stacks using a single list:

1
2
3
4
5
6
7
8
9

class Stack:
    def __init__(self):
        self.list = []

    def pop(self, stack_number):
        pass

    def push(self, item, stack_number):
        pass

Examples

Example 1

Solution

Method 1 - Using List

We can use a single list to manage three stacks by using a simple indexing approach. By maintaining separate bounds and pointers (indices) for each stack within the list, we can manage where elements of each stack are pushed and popped.

Approach

  1. Initialization: Use a single list for storing the data for all three stacks.
  2. Push Operation:
    • Calculate the index where the item should be placed based on the stack number and the current size of that stack.
    • Insert the item at the derived index.
  3. Pop Operation:
    • Fetch the last item pushed to the specific stack based on the stack number.
    • Return the item and remove it from the list.
  4. Tracking: Maintain a list of three lists (bounds) to keep track of the current items in each stack.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class Solution {

    public static class Stack {
        private List<Integer> list;
        private List<List<Integer>> bounds;

        public Stack() {
            list = new ArrayList<>();
            bounds = new ArrayList<>(3);
            for (int i = 0; i < 3; i++) {
                bounds.add(new ArrayList<>());
            }
        }

        public void push(int item, int stackNumber) {
            if (stackNumber < 0 || stackNumber > 2) {
                throw new IllegalArgumentException("Invalid stack number");
            }
            int index = bounds.get(stackNumber).size();
            list.add(item);
            bounds.get(stackNumber).add(index);
        }

        public int pop(int stackNumber) {
            if (stackNumber < 0 || stackNumber > 2) {
                throw new IllegalArgumentException("Invalid stack number");
            }
            if (bounds.get(stackNumber).isEmpty()) {
                throw new IllegalStateException("Stack is empty");
            }
            int lastIndex = bounds.get(stackNumber).remove(bounds.get(stackNumber).size() - 1);
            return list.remove(lastIndex);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    class Stack:
        def __init__(self):
            self.list: List[int] = []
            self.bounds: List[List[int]] = [[] for _ in range(3)]

        def push(self, item: int, stack_number: int) -> None:
            if stack_number < 0 or stack_number > 2:
                raise ValueError("Invalid stack number")
            self.list.append(item)
            self.bounds[stack_number].append(len(self.list) - 1)

        def pop(self, stack_number: int) -> int:
            if stack_number < 0 or stack_number > 2:
                raise ValueError("Invalid stack number")
            if not self.bounds[stack_number]:
                raise IndexError(f"Stack {stack_number} is empty")
            index = self.bounds[stack_number].pop()
            return self.list.pop(index)

Complexity

  • ⏰ Time complexity: 
  • Push Operation: O(1) for inserting an element at the end of the list.
  • Pop Operation: O(1) for removing the last element from the list.
  • 🧺 Space complexity: O(n) where n is the total number of elements pushed across all three stacks.