DSA 450 Notes

Problem Statement

Implement two stacks in a single array efficiently. Both stacks should be able to grow until the entire array is full (not just half of it).

Example:

Array size: 10
Stack1: push(1), push(2)  -> Uses indices 0, 1
Stack2: push(10), push(20) -> Uses indices 9, 8

Stack1: [1, 2, _, _, _, _, _, _, 20, 10] :Stack2 (grows towards center)

Approach 1: Divide Array in Two Halves (Brute Force)

Intuition

Simply divide the array into two halves. First stack uses the first half (0 to n/2-1), second stack uses the second half (n/2 to n-1). This is simple but wasteful as one stack might overflow while the other has space.

Algorithm

Divide array of size n into two halves
Stack1 uses indices [0, n/2-1], Stack2 uses [n/2, n-1]
Stack1 grows left to right, Stack2 also grows left to right in its half
Each stack can only use n/2 space even if other stack is empty

java

public class TwoStacksBruteForce {
    private int[] arr;
    private int capacity;
    private int top1, top2;
    private int mid;
    
    public TwoStacksBruteForce(int n) {
        capacity = n;
        arr = new int[n];
        mid = n / 2;
        top1 = -1;
        top2 = mid - 1;
    }
    
    public void push1(int x) {
        if (top1 >= mid - 1) {
            throw new RuntimeException("Stack1 Overflow");
        }
        arr[++top1] = x;
    }
    
    public void push2(int x) {
        if (top2 >= capacity - 1) {
            throw new RuntimeException("Stack2 Overflow");
        }
        arr[++top2] = x;
    }
    
    public int pop1() {
        if (top1 < 0) {
            throw new RuntimeException("Stack1 Underflow");
        }
        return arr[top1--];
    }
    
    public int pop2() {
        if (top2 < mid) {
            throw new RuntimeException("Stack2 Underflow");
        }
        return arr[top2--];
    }
    
    public static void main(String[] args) {
        TwoStacksBruteForce ts = new TwoStacksBruteForce(10);
        ts.push1(1);
        ts.push1(2);
        ts.push2(10);
        ts.push2(20);
        System.out.println("Pop from Stack1: " + ts.pop1()); // 2
        System.out.println("Pop from Stack2: " + ts.pop2()); // 20
    }
}

Complexity Analysis

Time Complexity: O(1) for all operations
Space Complexity: O(n), but wastes space as each stack limited to n/2

Approach 2: Two Ends Approach (Optimal)

Intuition

Start Stack1 from the beginning (index 0) and Stack2 from the end (index n-1). Stack1 grows towards right, Stack2 grows towards left. Both stacks can use the entire array space as long as they don't overlap.

Algorithm

Initialize top1 = -1 (Stack1 starts before index 0)
Initialize top2 = n (Stack2 starts after index n-1)
For push1: increment top1, check if top1 < top2
For push2: decrement top2, check if top1 < top2
Overflow when top1 + 1 == top2

java

public class TwoStacks {
    private int[] arr;
    private int capacity;
    private int top1, top2;
    
    public TwoStacks(int n) {
        capacity = n;
        arr = new int[n];
        top1 = -1;
        top2 = n;
    }
    
    public void push1(int x) {
        // Check for overflow (stacks meeting)
        if (top1 + 1 == top2) {
            throw new RuntimeException("Stack Overflow");
        }
        arr[++top1] = x;
    }
    
    public void push2(int x) {
        // Check for overflow (stacks meeting)
        if (top1 + 1 == top2) {
            throw new RuntimeException("Stack Overflow");
        }
        arr[--top2] = x;
    }
    
    public int pop1() {
        if (top1 < 0) {
            throw new RuntimeException("Stack1 Underflow");
        }
        return arr[top1--];
    }
    
    public int pop2() {
        if (top2 >= capacity) {
            throw new RuntimeException("Stack2 Underflow");
        }
        return arr[top2++];
    }
    
    public int peek1() {
        if (top1 < 0) {
            throw new RuntimeException("Stack1 is empty");
        }
        return arr[top1];
    }
    
    public int peek2() {
        if (top2 >= capacity) {
            throw new RuntimeException("Stack2 is empty");
        }
        return arr[top2];
    }
    
    public boolean isEmpty1() {
        return top1 < 0;
    }
    
    public boolean isEmpty2() {
        return top2 >= capacity;
    }
    
    public boolean isFull() {
        return top1 + 1 == top2;
    }
    
    public static void main(String[] args) {
        TwoStacks ts = new TwoStacks(10);
        
        // Push elements to both stacks
        ts.push1(1);
        ts.push1(2);
        ts.push1(3);
        ts.push2(10);
        ts.push2(20);
        ts.push2(30);
        
        System.out.println("Pop from Stack1: " + ts.pop1()); // 3
        System.out.println("Pop from Stack2: " + ts.pop2()); // 30
        System.out.println("Peek Stack1: " + ts.peek1());    // 2
        System.out.println("Peek Stack2: " + ts.peek2());    // 20
        
        // Test space efficiency
        ts.push1(4);
        ts.push1(5);
        ts.push1(6);
        ts.push1(7);
        
        System.out.println("Full: " + ts.isFull());
    }
}

Complexity Analysis

Time Complexity: O(1) for all operations
Space Complexity: O(n) with optimal space utilization - no wastage

Key Takeaways

Two-ends approach is optimal as it allows both stacks to use entire array space
Overflow occurs only when total elements in both stacks equal array size
Stack1 grows from left (0 to right), Stack2 grows from right (n-1 to left)
The condition top1 + 1 == top2 indicates array is full
This technique is useful when you need to minimize memory usage with multiple stacks
Cannot be easily extended to more than 2 stacks (see N stacks in array for that)

Implement 2 stack in an array

Problem Statement

Approach 1: Divide Array in Two Halves (Brute Force)

Intuition

Algorithm

Complexity Analysis

Approach 2: Two Ends Approach (Optimal)

Intuition

Algorithm

Complexity Analysis

Key Takeaways