DSA 450 Notes

Problem Statement

Implement k stacks in a single array of size n. All stacks should be able to grow and shrink dynamically. The space should be used efficiently - a stack should only throw overflow when the entire array is full.

Example:

Array size n = 10, Number of stacks k = 3

push(2, 10)  -> Stack 2 gets element 10
push(0, 5)   -> Stack 0 gets element 5
push(1, 15)  -> Stack 1 gets element 15
push(2, 20)  -> Stack 2 gets element 20
pop(2)       -> Returns 20 from Stack 2

Approach 1: Divide Array Equally (Brute Force)

Intuition

Divide the array of size n into k equal parts. Each stack gets n/k slots. This is simple but wastes space - one stack might overflow while others have plenty of space.

Algorithm

Divide array into k equal parts, each of size n/k
Stack i uses indices [i*(n/k), (i+1)*(n/k) - 1]
Maintain separate top pointers for each stack
Each stack is independent and limited to its partition

java

public class KStacksBruteForce {
    private int[] arr;
    private int[] tops;
    private int n, k;
    private int stackSize;
    
    public KStacksBruteForce(int n, int k) {
        this.n = n;
        this.k = k;
        this.stackSize = n / k;
        this.arr = new int[n];
        this.tops = new int[k];
        
        for (int i = 0; i < k; i++) {
            tops[i] = i * stackSize - 1;
        }
    }
    
    public void push(int stackNum, int x) {
        int start = stackNum * stackSize;
        int end = start + stackSize - 1;
        
        if (tops[stackNum] >= end) {
            throw new RuntimeException("Stack " + stackNum + " Overflow");
        }
        
        arr[++tops[stackNum]] = x;
    }
    
    public int pop(int stackNum) {
        int start = stackNum * stackSize;
        
        if (tops[stackNum] < start) {
            throw new RuntimeException("Stack " + stackNum + " Underflow");
        }
        
        return arr[tops[stackNum]--];
    }
    
    public int top(int stackNum) {
        int start = stackNum * stackSize;
        
        if (tops[stackNum] < start) {
            throw new RuntimeException("Stack " + stackNum + " is empty");
        }
        
        return arr[tops[stackNum]];
    }
    
    public boolean isEmpty(int stackNum) {
        return tops[stackNum] < stackNum * stackSize;
    }
    
    public static void main(String[] args) {
        KStacksBruteForce ks = new KStacksBruteForce(9, 3);
        
        ks.push(0, 10);
        ks.push(0, 20);
        ks.push(1, 30);
        ks.push(2, 40);
        
        System.out.println("Pop from stack 0: " + ks.pop(0)); // 20
        System.out.println("Pop from stack 1: " + ks.pop(1)); // 30
        System.out.println("Pop from stack 2: " + ks.pop(2)); // 40
    }
}

Complexity Analysis

Time Complexity: O(1) for all operations
Space Complexity: O(n*k) conceptually wastes space as each stack is limited

Approach 2: Using Free List (Optimal)

Intuition

Instead of dividing the array, use a free list to track available slots. Each slot can belong to any stack. Use two auxiliary arrays:

next[]: For each index, stores the next index in same stack OR next free slot
top[]: Stores the top index for each stack

Algorithm

Initialize all slots as free, linking them: next[i] = i+1
Maintain freeTop pointing to first free slot
On push: use freeTop slot, update freeTop to next[freeTop], link new slot to stack's top
On pop: add slot back to free list, update stack's top to next of popped slot

java

public class KStacks {
    private int[] arr;     // Actual array to store elements
    private int[] next;    // For occupied: next in stack, For free: next free
    private int[] top;     // Top index for each stack
    private int freeTop;   // Index of first free slot
    private int n, k;
    
    public KStacks(int n, int k) {
        this.n = n;
        this.k = k;
        
        arr = new int[n];
        next = new int[n];
        top = new int[k];
        
        // Initialize all slots as free
        for (int i = 0; i < n - 1; i++) {
            next[i] = i + 1;
        }
        next[n - 1] = -1;
        
        // All stacks are empty initially
        for (int i = 0; i < k; i++) {
            top[i] = -1;
        }
        
        // First free slot is 0
        freeTop = 0;
    }
    
    public void push(int stackNum, int x) {
        if (isFull()) {
            throw new RuntimeException("Stack Overflow - All stacks full");
        }
        
        // Get index of first free slot
        int i = freeTop;
        
        // Update freeTop to next free slot
        freeTop = next[i];
        
        // Store the element
        arr[i] = x;
        
        // Link this slot to previous top of this stack
        next[i] = top[stackNum];
        
        // Update top of this stack
        top[stackNum] = i;
    }
    
    public int pop(int stackNum) {
        if (isEmpty(stackNum)) {
            throw new RuntimeException("Stack " + stackNum + " Underflow");
        }
        
        // Get index of top element
        int i = top[stackNum];
        
        // Update top to next element in stack
        top[stackNum] = next[i];
        
        // Add this slot to free list
        next[i] = freeTop;
        freeTop = i;
        
        return arr[i];
    }
    
    public int peek(int stackNum) {
        if (isEmpty(stackNum)) {
            throw new RuntimeException("Stack " + stackNum + " is empty");
        }
        return arr[top[stackNum]];
    }
    
    public boolean isEmpty(int stackNum) {
        return top[stackNum] == -1;
    }
    
    public boolean isFull() {
        return freeTop == -1;
    }
    
    public static void main(String[] args) {
        KStacks ks = new KStacks(10, 3);
        
        // Push elements to different stacks
        ks.push(2, 15);
        ks.push(2, 45);
        ks.push(0, 11);
        ks.push(1, 17);
        ks.push(0, 39);
        ks.push(1, 49);
        
        System.out.println("Popped from stack 2: " + ks.pop(2)); // 45
        System.out.println("Popped from stack 1: " + ks.pop(1)); // 49
        System.out.println("Popped from stack 0: " + ks.pop(0)); // 39
        
        // Stack 2 can use more space now
        ks.push(2, 100);
        ks.push(2, 200);
        ks.push(2, 300);
        
        System.out.println("Top of stack 2: " + ks.peek(2)); // 300
    }
}

Complexity Analysis

Time Complexity: O(1) for all operations
Space Complexity: O(n + k) - n for array and next[], k for top[]

Key Takeaways

Free list approach allows optimal space utilization - any stack can grow until array is full
The next[] array serves dual purpose: links elements in a stack AND tracks free slots
Think of free slots as a "free stack" - freeTop is its top, next[] links free slots
When pushing: remove from free list, add to stack
When popping: remove from stack, add to free list
This is O(1) for all operations with O(n + k) extra space
The brute force division approach wastes space and is not practical for uneven usage patterns

Implement N stacks in an Array

Problem Statement

Approach 1: Divide Array Equally (Brute Force)

Intuition

Algorithm

Complexity Analysis

Approach 2: Using Free List (Optimal)

Intuition

Algorithm

Complexity Analysis

Key Takeaways