Dry Run Guidelines for DSA

Dry Run Techniques, Tricks, and Guidelines for DSA 

Dry running an algorithm means manually simulating the code step-by-step with sample inputs to see how it behaves. It's like test-driving a car before buying it 🚗—you want to check if everything works as expected before running it in an actual program.

1️⃣ Golden Rule: Use a Table for Dry Running

A table helps track values of variables at each step. Here’s a basic example:

Example: Find the sum of an array

arr = [1, 2, 3]
sum = 0
for num in arr:
    sum += num
print(sum)  # Output: 6

📌 Dry Run Table:

✅ Trick: Always maintain a table with variables to see the flow of execution.

2️⃣ Debugging with a Pen & Paper 📝

Sometimes, don’t rush to run the code—write it down and manually go through the steps.
🔹 Break the logic into small steps
🔹 Identify loops and conditions
🔹 Track changes in variables manually

3️⃣ Use Sample Test Cases

For every algorithm, test with:
✅ Smallest Input (Edge case: n=0, n=1)
✅ General Case (n=5, n=10)
✅ Worst Case (Largest input n=10⁶ for performance testing)

Example:
💡 Binary Search (on [2, 4, 6, 8, 10] to find 8)

1. Middle = 6 → Too small, move right
2. Middle = 8 → Found!

✅ Trick: Run step-by-step on different inputs.

4️⃣ Track Loop Iterations Using Index Pointers 🔢

For loops & recursion, always track the changing index.

Example: Reverse a string

s = "abc"
print(s[::-1])  # Output: "cba"

📌 Dry Run Table (Two-Pointer Approach)

✅ Tip: If there are two pointers (left & right), track their movements.

5️⃣ Identify Base Cases for Recursion

If using recursion, always track the base case to prevent infinite calls.

Example: Factorial Calculation

def fact(n):
    if n == 0: return 1
    return n * fact(n - 1)

print(fact(3))  # Output: 6

📌 Dry Run Steps:

• fact(3) = 3 * fact(2)
• fact(2) = 2 * fact(1)
• fact(1) = 1 * fact(0)
• fact(0) = 1 (Base Case)
• Backtrack & Multiply: 3 * 2 * 1 * 1 = 6

✅ Tip: If recursion is tricky, expand calls manually.

6️⃣ Break Conditions Down Step by Step 🛠️

For if-else statements, test each branch separately.

Example: Find if a number is even or odd

num = 5
if num % 2 == 0:
    print("Even")
else:
    print("Odd")

📌 Test Cases:

✅ Tip: Check both possible paths (if & else).

7️⃣ Watch Out for Off-by-One Errors (OBOE) 🚨

Looping mistakes happen when you go one step too far.

Example: Print numbers from 1 to 5

for i in range(1, 6):
    print(i)  # Correct

⚠️ Mistake:

for i in range(1, 5):
    print(i)  # Stops at 4, should be range(1,6)

✅ Tip: Always double-check the loop start and end.

8️⃣ Understand Algorithm Complexity (Big-O) 🔥

While dry running, check:

• O(1): Direct lookups (e.g., HashMap)
• O(log N): Binary Search (reducing by half)
• O(N): Looping through data
• O(N²): Nested loops

📌 Example:
🔹 Finding max in an array → O(N)
🔹 Checking if a number exists in sorted array (Binary Search) → O(log N)

✅ Tip: If a loop is inside another loop, check if it’s O(N²) slow.

9️⃣ Dry Run Trick for Recursion with Stack Simulation 📚

For recursion, think of it like a stack (LIFO - Last In, First Out).

Example: Reverse a string using recursion

def rev(s):
    if len(s) == 0:
        return ""
    return rev(s[1:]) + s[0]  # Recurse + append first letter

print(rev("abc"))  # Output: "cba"

📌 Call Stack:

rev("abc") → rev("bc") + "a"
rev("bc")  → rev("c") + "b"
rev("c")   → rev("") + "c"
rev("")    → ""

✅ Tip: Always write out recursion calls in stack order.

🔟 Final Checklist for Dry Running Any Algorithm

✔ Use a Table to track variables
✔ Write Down Iterations for loops
✔ Test Edge Cases (smallest, largest, empty input)
✔ Manually Expand Recursion
✔ Check Loop Boundaries (Off-by-One errors)
✔ Understand Complexity (Big-O)

Would you like a dry-run example for a specific problem? 🚀