Empty Slot/Gap Stack
Empty Slot/Gap Stack problems involve a vertical stack with multiple empty slots. You must determine positions of boxes and empties using constraints about gaps between boxes and relationships involving empties.
What You'll Learn
Introduction to Empty Slot/Gap Stack
Empty Slot/Gap Stack problems involve a vertical stack with multiple empty slots. You must determine positions of boxes and empties using constraints about gaps between boxes and relationships involving empties.
Prerequisites
How to Solve Empty Slot/Gap Stack Problems
Step 1: Determine total positions (N) and number of boxes (M)
Step 2: Identify known positions of boxes and empties
Step 3: Apply constraints about boxes (e.g., 'X and Y have exactly k entities between')
Step 4: Apply constraints about empties (e.g., 'T is immediately above second empty')
Step 5: Use elimination to determine positions of remaining boxes and empties
Step 6: Answer the specific question
Example Problem
Example: 7 positions, 5 boxes P-T, 2 empties. Q at top, P at bottom. One empty at position 2. R and S have exactly 2 entities between. T immediately above second empty. Find T's position. Solution: Step 1: pos1=P, pos7=Q, pos2=Empty Step 2: Second empty at X, T at X+1 Step 3: Try X=4: T=5, R and S at 3 and 6 → between = positions 4,5 (Empty,T) = 2 entities ✓ Step 4: T at position 5 Answer: Position 5
Pro Tips & Tricks
- Empty positions are 'entities' when counting between boxes
- Total entities between positions = number of positions between them
- Both boxes and empties count as entities
- The 'second empty' refers to order by position number, not by any other property
- Draw the stack with placeholders for unknown positions
- Systematically test possible positions for unknown empties
Shortcut Methods to Solve Faster
Common Mistakes to Avoid
Practice Worksheets
Practice makes perfect! Work through these worksheets to master Empty Slot/Gap Stack. Each worksheet contains 20 questions with detailed explanations. Start from Worksheet 1 and progress through increasing difficulty levels.
Exam Importance
Empty Slot/Gap Stack is an important topic for various competitive exams. Here's how frequently it appears:
Ready to Master Empty Slot/Gap Stack?
Start with Worksheet 1 and work your way up to expert level! Each worksheet includes: