Implement 3 stacks in 1 list

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

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

Initialization: Use a single list for storing the data for all three stacks.
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.
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.
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.

Problem#

Solution#

Method 1 - Using List#

Approach#

Code#

Complexity#