DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Dry Run & Debug Approach

You've written code that looks correct, but it fails on some test cases. Or worse, you can't understand why it works. Sound familiar?

Dry running (manually tracing code) and systematic debugging are the most underrated skills in programming. Master these, and you'll spend 10x less time debugging.

Goal: Learn to trace through code like a computer and debug issues systematically.

Key Insight: If you can't dry run your code with a simple example, you don't truly understand it. Dry running turns mysterious bugs into obvious fixes.

What is Dry Running?

Dry running means manually executing code step-by-step, tracking all variables, just like a computer would.

Why Dry Run?

1. Verify Correctness

›Catch logic errors before running code
›Ensure algorithm works for edge cases

2. Understand Code

›See exactly what each line does
›Understand why algorithm works

3. Debug Efficiently

›Pinpoint exact line where logic fails
›Understand unexpected behavior

4. Interview Success

›Demonstrate understanding to interviewers
›Catch mistakes before submitting

The Dry Run Method

Follow these steps for any code:

Step 1: Choose a Simple Test Case

Pick an example that:

›Is small enough to trace manually (3-5 elements)
›Covers the main logic
›Isn't too trivial

Example: For array problems, use [3, 1, 4, 2] instead of [1, 2, 3]

Step 2: Set Up a Trace Table

Create columns for:

›Line number or step
›Each variable
›Important conditions
›Output/result

Step 3: Execute Line by Line

For each line:

›Update variable values
›Check conditions
›Record changes
›Note any output

Step 4: Verify Result

Check:

›Final output matches expected
›All variables have expected values
›No unexpected state

Example 1: Find Maximum in Array

Let's dry run this simple algorithm:

Python

Try it out

def find_max(arr):
    max_val = arr[0]          # Line 1
    
    for i in range(1, len(arr)):  # Line 2
        if arr[i] > max_val:      # Line 3
            max_val = arr[i]      # Line 4
    
    return max_val            # Line 5

# Test case
result = find_max([3, 1, 4, 2])

Dry Run Trace Table:

Input: arr = [3, 1, 4, 2]

Step	Line	i	arr[i]	max_val	Condition (arr[i] > max_val)	Action
1	1	-	-	3	-	Initialize max_val
2	2	1	1	3	-	Start loop
3	3	1	1	3	1 > 3 = False	Skip update
4	2	2	4	3	-	Next iteration
5	3	2	4	3	4 > 3 = True	Enter if
6	4	2	4	4	-	Update max_val
7	2	3	2	4	-	Next iteration
8	3	3	2	4	2 > 4 = False	Skip update
9	2	4	-	4	-	Loop ends
10	5	-	-	4	-	Return 4

Result: 4 (Correct!)

Verification: The algorithm correctly found the maximum value.

Example 2: Two Sum Problem

Let's dry run a more complex algorithm:

Python

Try it out

def two_sum(nums, target):
    seen = {}                           # Line 1
    
    for i, num in enumerate(nums):      # Line 2
        complement = target - num       # Line 3
        
        if complement in seen:          # Line 4
            return [seen[complement], i]  # Line 5
        
        seen[num] = i                   # Line 6
    
    return []                           # Line 7

# Test case
result = two_sum([2, 7, 11, 15], 9)

Dry Run Trace Table:

Input: nums = [2, 7, 11, 15], target = 9

Step	Line	i	num	complement	seen	Condition	Action
1	1	-	-	-	`{}`	-	Initialize empty map
2	2	0	2	-	`{}`	-	Start loop
3	3	0	2	7	`{}`	-	Calculate 9-2=7
4	4	0	2	7	`{}`	7 in `{}` = False	Skip return
5	6	0	2	7	`{2:0}`	-	Add 2→0 to map
6	2	1	7	-	`{2:0}`	-	Next iteration
7	3	1	7	2	`{2:0}`	-	Calculate 9-7=2
8	4	1	7	2	`{2:0}`	2 in `{2:0}` = True	Found!
9	5	1	7	2	`{2:0}`	-	Return [0, 1]

Result: [0, 1] (Correct!)

Verification: nums[0] + nums[1] = 2 + 7 = 9

Example 3: Binary Search

Let's dry run a recursive algorithm:

Python

Try it out

def binary_search(arr, target, left, right):
    if left > right:                    # Line 1
        return -1                       # Line 2
    
    mid = (left + right) // 2           # Line 3
    
    if arr[mid] == target:              # Line 4
        return mid                      # Line 5
    elif arr[mid] < target:             # Line 6
        return binary_search(arr, target, mid + 1, right)  # Line 7
    else:
        return binary_search(arr, target, left, mid - 1)   # Line 8

# Test case
result = binary_search([1, 3, 5, 7, 9], 7, 0, 4)

Dry Run with Recursion Tree:

Input: arr = [1, 3, 5, 7, 9], target = 7

Call 1: binarySearch(arr, 7, 0, 4)
  ├─ left=0, right=4, mid=2
  ├─ arr[2]=5, 5 < 7
  └─ Recurse right: binarySearch(arr, 7, 3, 4)
      |
      Call 2: binarySearch(arr, 7, 3, 4)
        ├─ left=3, right=4, mid=3
        ├─ arr[3]=7, 7 == 7
        └─ Return 3 ✓

Trace Table:

Call	left	right	mid	arr[mid]	Comparison	Action
1	0	4	2	5	5 < 7	Search right half
2	3	4	3	7	7 == 7	Return 3

Result: 3 (Correct!)

Verification: arr[3] = 7

Systematic Debugging Approach

When code doesn't work, follow this process:

Step 1: Reproduce the Bug

Actions:

›Identify the failing test case
›Run the code with that input
›Confirm the bug is consistent

Example:

Input: [1, 2, 3]
Expected: 6
Got: 3
Bug confirmed!

Step 2: Understand Expected vs Actual

Questions:

›What should happen?
›What actually happens?
›Where do they diverge?

Example:

Expected: Sum all elements → 1+2+3=6
Actual: Only returns first element → 3
Hypothesis: Not iterating through all elements

Step 3: Add Strategic Print Statements

Where to add prints:

›Before and after key operations
›Inside loops (with iteration number)
›At function entry/exit
›Variable changes

Python

Try it out

def buggy_sum(arr):
    total = 0
    print(f"Starting sum, arr={arr}")  # Entry point
    
    for i in range(len(arr)):
        print(f"  Iteration {i}: total={total}, arr[i]={arr[i]}")  # Loop state
        total += arr[i]
        print(f"  After add: total={total}")  # After operation
    
    print(f"Final total: {total}")  # Exit point
    return total

Step 4: Dry Run the Failing Case

Trace manually:

›Use the exact input that fails
›Follow every line
›Compare with expected behavior

Step 5: Form Hypothesis

Based on dry run:

›Identify where logic diverges
›Guess the root cause
›Predict the fix

Example:

Hypothesis: Loop starts at index 1 instead of 0
Evidence: First element is skipped
Fix: Change range(1, len(arr)) to range(len(arr))

Step 6: Test the Fix

After fixing:

›Run original failing test
›Run edge cases
›Run all test cases
›Verify no new bugs introduced

Common Bug Patterns

Pattern 1: Off-by-One Errors

Symptoms:

›Skipping first/last element
›Array index out of bounds
›Wrong final result

Example Bug:

Python

Try it out

# Bug: Skips last element
def sum_array_bug(arr):
    total = 0
    for i in range(len(arr) - 1):  # ❌ Should be len(arr)
        total += arr[i]
    return total

# Fix
def sum_array_fix(arr):
    total = 0
    for i in range(len(arr)):  # ✓ Correct
        total += arr[i]
    return total

# Dry run with [1, 2, 3]:
# Bug: i goes 0,1 → skips arr[2] → returns 3
# Fix: i goes 0,1,2 → includes all → returns 6

Pattern 2: Wrong Variable Update

Symptoms:

›Variable doesn't change as expected
›Infinite loops
›Wrong final state

Example Bug:

Python

Try it out

# Bug: Updates wrong variable
def find_max_bug(arr):
    max_val = arr[0]
    current = arr[0]  # Extra variable
    
    for num in arr:
        if num > max_val:
            current = num  # ❌ Updates wrong variable
    
    return max_val  # Returns unchanged value

# Fix
def find_max_fix(arr):
    max_val = arr[0]
    
    for num in arr:
        if num > max_val:
            max_val = num  # ✓ Updates correct variable
    
    return max_val

# Dry run with [3, 5, 1]:
# Bug: max_val stays 3, current becomes 5
# Fix: max_val becomes 5

Pattern 3: Wrong Condition

Symptoms:

›Logic executes at wrong time
›Missing cases
›Incorrect branching

Example Bug:

Python

Try it out

# Bug: Uses > instead of >=
def binary_search_bug(arr, target):
    left, right = 0, len(arr) - 1
    
    while left > right:  # ❌ Should be >=
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Fix
def binary_search_fix(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:  # ✓ Correct
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Dry run with [1, 3, 5], target=1:
# Bug: left=0, right=2, left>right is False, loop never runs
# Fix: left=0, right=2, left<=right is True, finds element

Debugging Checklist

When debugging, check:

Logic Issues:

› Are loop bounds correct? (off-by-one)
› Are conditions correct? (>, >=, <, <=, ==, !=)
› Are all variables initialized?
› Are variables updated correctly?
› Are edge cases handled?

Data Issues:

› Are indices within bounds?
› Are null/empty cases handled?
› Are data types correct?
› Are comparisons using correct operators?

Flow Issues:

› Does control flow match expectations?
› Are return statements in right places?
› Are break/continue used correctly?
› Are recursive base cases correct?

Tips for Effective Dry Running

Tip 1: Use Small Inputs

Bad: Dry run with array of 100 elements
Good: Dry run with [3, 1, 4] - small but non-trivial

Tip 2: Write It Down

Bad: Trace in your head
Good: Use paper or table - prevents mistakes

Tip 3: Be Methodical

Bad: Jump around code
Good: Execute line by line, no shortcuts

Tip 4: Check Edge Cases

Dry run with:

›Empty input
›Single element
›All same values
›Already sorted
›Reverse sorted

Tip 5: Trace Both Paths

For conditionals:

›Dry run when condition is true
›Dry run when condition is false

Interview Dry Run Strategy

When Asked to Dry Run:

Step 1: "Let me trace through with a simple example"

Step 2: Write the example clearly

Step 3: Create a simple table (or use space efficiently)

Step 4: Talk through each step aloud

Step 5: Highlight the result

Example:

Interviewer: Walk me through how this works

You: Let me trace through with [3, 1, 4]. Starting with max_val = 3.
     At i=1, arr[1]=1, 1 is not > 3, so skip.
     At i=2, arr[2]=4, 4 > 3, so update max_val to 4.
     Return 4, which is correct.

Key Takeaways

Dry Running:

›Execute code manually, step by step
›Use a trace table to track variables
›Verify logic with simple test cases
›Catch bugs before running code

Debugging:

›Reproduce the bug consistently
›Add strategic print statements
›Dry run the failing case
›Form hypothesis, test fix
›Check all test cases after fixing

Remember: If you can dry run it, you understand it. If you can't, you don't.

What's Next?

Now that you can dry run and debug:

›Testing Strategies - Write comprehensive tests
›Common Patterns - Practice dry running patterns
›Practice Problems - Apply dry running to real problems

Practice Exercise

Dry run this code with input [2, 7, 11, 15], target = 18:

Python

Try it out

def mystery(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return [i, j]
    return []

Create your trace table and find the answer!

Answer: [1, 2] (because arr[1] + arr[2] = 7 + 11 = 18)

Congratulations! You now have systematic dry running and debugging skills!

←

PreviousChoosing the Right Data Structure

NextArray Basics

→