Implement Two Stacks in One Array

Pattern:

Idea:

Variations :

---

💻 Code

class TwoStacks:

    def __init__(self, n):
        self.arr = [0] * n
        self.size = n
        self.top1 = -1
        self.top2 = n

    def push1(self, x):
        if self.top1 + 1 == self.top2:
            raise OverflowError("Stack Overflow")

        self.top1 += 1
        self.arr[self.top1] = x

    def push2(self, x):
        if self.top1 + 1 == self.top2:
            raise OverflowError("Stack Overflow")

        self.top2 -= 1
        self.arr[self.top2] = x

    def pop1(self):
        if self.top1 == -1:
            return -1

        x = self.arr[self.top1]
        self.top1 -= 1
        return x

    def pop2(self):
        if self.top2 == self.size:
            return -1

        x = self.arr[self.top2]
        self.top2 += 1
        return x

Time complexity - O(1)

Aux. Space complexity - O(1)

---

Implement Two Stacks in One Array

Tags: #Stack #Arrays #InPlace #DataStructures #SpaceOptimization #Interview-Pattern #FAANG

Problem Statement

Design a data structure that implements two independent stacks using a single array of size n.

Operations should support:

• push1(x)
• push2(x)
• pop1()
• pop2()

All operations must run in O(1) time.

---

Core Insight

Instead of splitting the array into two fixed halves, let the two stacks grow towards each other.

• Stack 1 starts from index 0 and grows right.
• Stack 2 starts from index n−1 and grows left.

This dynamically shares unused space between both stacks.

This is the optimal space-efficient implementation.

---

Why Not Divide the Array into Two Halves?

Suppose n = 10.

Fixed Partition

If Stack 1 grows to 6 elements while Stack 2 has only 1, Stack 1 overflows despite free space existing.

Dynamic Growth

Both stacks use the entire array efficiently.

---

Data Structure

Maintain:

• arr → shared array
• top1 → top of Stack 1
• top2 → top of Stack 2

Initial state:

Variable	Value
top1	-1
top2	n

Index:

0 1 2 3 4 5 6 7 8 9
                  ↑
top2 = 10

top1 = -1

---

Push Operations

Push into Stack 1

Before inserting, ensure one free cell exists.

Condition:

def push1(self, x):
    if self.top1 + 1 == self.top2:
        raise OverflowError

    self.top1 += 1
    self.arr[self.top1] = x

Push into Stack 2

def push2(self, x):
    if self.top1 + 1 == self.top2:
        raise OverflowError

    self.top2 -= 1
    self.arr[self.top2] = x

---

Pop Operations

Pop Stack 1

def pop1(self):
    if self.top1 == -1:
        return -1

    x = self.arr[self.top1]
    self.top1 -= 1
    return x

Pop Stack 2

def pop2(self):
    if self.top2 == self.size:
        return -1

    x = self.arr[self.top2]
    self.top2 += 1
    return x

---

Complete Python Implementation

class TwoStacks:

    def __init__(self, n):
        self.arr = [0] * n
        self.size = n
        self.top1 = -1
        self.top2 = n

    def push1(self, x):
        if self.top1 + 1 == self.top2:
            raise OverflowError("Stack Overflow")

        self.top1 += 1
        self.arr[self.top1] = x

    def push2(self, x):
        if self.top1 + 1 == self.top2:
            raise OverflowError("Stack Overflow")

        self.top2 -= 1
        self.arr[self.top2] = x

    def pop1(self):
        if self.top1 == -1:
            return -1

        x = self.arr[self.top1]
        self.top1 -= 1
        return x

    def pop2(self):
        if self.top2 == self.size:
            return -1

        x = self.arr[self.top2]
        self.top2 += 1
        return x

---

Dry Run

Initial

_ _ _ _ _ _ _ _

top1 = -1
top2 = 8

push1(10)

10 _ _ _ _ _ _ _

top1 = 0

push1(20)

10 20 _ _ _ _ _ _

push2(90)

10 20 _ _ _ _ _ 90

push2(80)

10 20 _ _ _ _ 80 90

The stacks grow toward each other.

---

Overflow Condition

Overflow occurs only when both tops meet.

10 20 30 40 50 60
         ↑↑

Condition:

if top1 + 1 == top2:

There is no free space remaining.

This is superior to checking individual stack sizes.

---

Correctness

Invariant

At every moment:

Therefore:

• Stack 1 occupies [0 ... top1]
• Stack 2 occupies [top2 ... n−1]
• Free space is exactly between them.

All push/pop operations preserve this invariant.

---

Complexity

Operation	Time	Auxiliary Space
push1	O(1)	O(1)
push2	O(1)	O(1)
pop1	O(1)	O(1)
pop2	O(1)	O(1)

---

Common Mistakes

1. Splitting the Array into Two Halves

This wastes memory and causes premature overflow.

2. Incorrect Overflow Check

Wrong:

if top1 == top2:

Correct:

if top1 + 1 == top2:

The two tops should never occupy the same cell.

3. Wrong Initial Value of top2

Correct initialization:

top1 = -1
top2 = n

Not n−1, because Stack 2 is initially empty.

---

Pattern Recognition

This is a classic space optimization interview problem.

General principle:

• Two independent structures
• Shared contiguous storage
• Grow from opposite directions
• Detect collision as overflow

The reusable invariant is:

Maintaining this single condition guarantees both stacks operate correctly in constant time while utilizing the entire array.