Python Algorithm Practice - CCC Prep Part 2: Answer Key 🗺️

Complete solutions with explanations, step-by-step breakdowns, and complexity analysis.

---

Exercise 0: Grid Sum 🔢

Problem: Return the sum of all numbers in a 2D grid.

Approach

Use nested loops to visit every cell and accumulate the sum.

Steps

1. Initialize total = 0
2. Loop through each row in the grid
3. Loop through each number in the current row
4. Add the number to total
5. Return total

Solution

def grid_sum(grid):
    total = 0
    for row in grid:
        for num in row:
            total += num
    return total

Alternative Solution (One-liner)

def grid_sum_alternative(grid):
    return sum(sum(row) for row in grid)

Time Complexity

O(rows × cols) - Must visit every cell once

Space Complexity

O(1) - Only using a single variable for accumulation

Test Results

print(grid_sum([[1, 2, 3], [4, 5, 6]]))  # Output: 21
print(grid_sum([[10, -5], [3, 7], [2, -1]]))  # Output: 16

---

Exercise 1: Find Maximum in Grid 🔍

Problem: Return the largest number in the entire grid.

Approach

Track the maximum value while scanning all cells with nested loops.

Steps

1. Initialize max_val to the first element grid[0][0]
2. Loop through each row in the grid
3. Loop through each number in the current row
4. If number is greater than max_val, update max_val
5. Return max_val

Solution

def grid_maximum(grid):
    max_val = grid[0][0]  # Start with first element
    for row in grid:
        for num in row:
            if num > max_val:
                max_val = num
    return max_val

Alternative Solution

def grid_maximum_alternative(grid):
    return max(max(row) for row in grid)

Time Complexity

O(rows × cols) - Must scan every cell to find maximum

Space Complexity

O(1) - Only tracking one variable

Test Results

print(grid_maximum([[3, 7, 2], [9, 1, 5], [4, 8, 6]]))  # Output: 9
print(grid_maximum([[-5, -2], [-10, -1], [-3, -7]]))  # Output: -1

---

Exercise 2: Count Specific Value 📊

Problem: Count how many times a target value appears in the grid.

Approach

Scan every cell and count matches to the target value.

Steps

1. Initialize count = 0
2. Loop through each row in the grid
3. Loop through each number in the current row
4. If number equals target, increment count
5. Return count

Solution

def count_value(grid, target):
    count = 0
    for row in grid:
        for num in row:
            if num == target:
                count += 1
    return count

Time Complexity

O(rows × cols) - Must check every cell

Space Complexity

O(1) - Only using a counter variable

Test Results

grid = [[1, 2, 1], [3, 1, 2], [1, 3, 1]]
print(count_value(grid, 1))  # Output: 5
print(count_value(grid, 3))  # Output: 2
print(count_value(grid, 5))  # Output: 0

---

Exercise 3: Row and Column Sums 🧮

Problem: Return a tuple containing (list of row sums, list of column sums).

Approach

• Row sums: Iterate through each row and sum its elements
• Column sums: For each column index, sum all elements in that column

Steps

1. Get dimensions: rows = len(grid), cols = len(grid[0])
2. Calculate row sums:
   • Create empty list row_sums
   • For each row, sum all elements and append to row_sums
3. Calculate column sums:
   • Create empty list col_sums
   • For each column index col:
     • Initialize col_sum = 0
     • For each row index row, add grid[row][col] to col_sum
     • Append col_sum to col_sums
4. Return (row_sums, col_sums)

Solution

def sum_rows_and_cols(grid):
    rows = len(grid)
    cols = len(grid[0])
    
    # Calculate row sums
    row_sums = []
    for row in grid:
        row_sums.append(sum(row))
    
    # Calculate column sums
    col_sums = []
    for col in range(cols):
        col_sum = 0
        for row in range(rows):
            col_sum += grid[row][col]
        col_sums.append(col_sum)
    
    return (row_sums, col_sums)

Time Complexity

O(rows × cols) - Visit each cell once for row sums, once for column sums

Space Complexity

O(rows + cols) - Storing two lists (row sums and column sums)

Test Results

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(sum_rows_and_cols(grid))
# Output: ([6, 15, 24], [12, 15, 18])

grid2 = [[1, 1], [2, 2], [3, 3]]
print(sum_rows_and_cols(grid2))
# Output: ([2, 4, 6], [6, 6])

---

Exercise 4: Find Position 📍

Problem: Return the position (row, col) of the first occurrence of target. Return None if not found.

Approach

Scan the grid left-to-right, top-to-bottom until the target is found.

Steps

1. Loop through each row index from 0 to len(grid)
2. Loop through each column index from 0 to len(grid[0])
3. If grid[row][col] equals target, return (row, col)
4. If loop completes without finding target, return None

Solution

def find_position(grid, target):
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] == target:
                return (row, col)
    return None

Time Complexity

O(rows × cols) - Worst case: target is last cell or doesn't exist

Space Complexity

O(1) - No additional data structures needed

Test Results

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(find_position(grid, 5))   # Output: (1, 1)
print(find_position(grid, 7))   # Output: (2, 0)
print(find_position(grid, 10))  # Output: None

---

Exercise 5: Check Neighbors 🧭

Problem: Count how many of the 4 adjacent cells (up, down, left, right) equal a target value.

Approach

Check all 4 directions from the given position, counting matches while respecting grid boundaries.

Steps

1. Get grid dimensions: rows, cols
2. Initialize count = 0
3. Define 4 directions: [(-1, 0), (1, 0), (0, -1), (0, 1)] (up, down, left, right)
4. For each direction (dr, dc):
   • Calculate new position: new_row = row + dr, new_col = col + dc
   • Check if within bounds: 0 <= new_row < rows and 0 <= new_col < cols
   • If valid and grid[new_row][new_col] == value, increment count
5. Return count

Solution

def count_neighbors(grid, row, col, value):
    rows = len(grid)
    cols = len(grid[0])
    count = 0
    
    # Define 4 directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for dr, dc in directions:
        new_row = row + dr
        new_col = col + dc
        
        # Check if within bounds
        if 0 <= new_row < rows and 0 <= new_col < cols:
            if grid[new_row][new_col] == value:
                count += 1
    
    return count

Time Complexity

O(1) - Always checks exactly 4 neighbors (constant time)

Space Complexity

O(1) - Fixed number of variables

Test Results

grid = [[1, 2, 1], [2, 5, 2], [1, 2, 1]]
print(count_neighbors(grid, 1, 1, 2))  # Output: 4
print(count_neighbors(grid, 0, 0, 2))  # Output: 1
print(count_neighbors(grid, 1, 1, 1))  # Output: 0

---

Exercise 6: Simple Recursion - Countdown 🚀

Problem: Print numbers from n down to 1 using recursion (no loops).

Approach

Use recursion with a base case to stop at 0.

Steps

1. Base case: If n == 0, return (stop recursing)
2. Recursive case:
   • Print the current value n
   • Call countdown(n - 1) to handle remaining numbers

Solution

def countdown(n):
    if n == 0:  # Base case
        return
    
    print(n)
    countdown(n - 1)  # Recursive call

Recursion Tree (countdown(3))

countdown(3)
  print(3)
  └─ countdown(2)
       print(2)
       └─ countdown(1)
            print(1)
            └─ countdown(0)
                 return (base case)

Time Complexity

O(n) - Makes n recursive calls

Space Complexity

O(n) - Call stack depth is n

Test Results

countdown(5)
# Output:
# 5
# 4
# 3
# 2
# 1

---

Exercise 7: Recursive Sum 🔢

Problem: Return the sum of all elements from a given index to the end of the list using recursion.

Approach

Use recursion to break down the problem: sum = current element + sum of remaining elements.

Steps

1. Base case: If index >= len(numbers), return 0 (no more elements)
2. Recursive case: Return numbers[index] + recursive_sum(numbers, index + 1)

Solution

def recursive_sum(numbers, index):
    if index >= len(numbers):  # Base case
        return 0
    
    # Recursive case: current element + sum of remaining elements
    return numbers[index] + recursive_sum(numbers, index + 1)

Recursion Tree (recursive_sum([1,2,3], 0))

recursive_sum([1,2,3], 0)
  return 1 + recursive_sum([1,2,3], 1)
               return 2 + recursive_sum([1,2,3], 2)
                            return 3 + recursive_sum([1,2,3], 3)
                                         return 0 (base case)
                            = 3 + 0 = 3
               = 2 + 3 = 5
  = 1 + 5 = 6

Time Complexity

O(n) - Makes n recursive calls where n = length - index

Space Complexity

O(n) - Call stack depth proportional to number of elements

Test Results

print(recursive_sum([1, 2, 3, 4, 5], 0))  # Output: 15
print(recursive_sum([1, 2, 3, 4, 5], 2))  # Output: 12 (3+4+5)
print(recursive_sum([10, 20, 30], 1))     # Output: 50 (20+30)

---

Exercise 8: Flood Fill 🎨

Problem: Change a cell and all connected cells of the same color to a new color (like paint bucket tool).

Approach

Use DFS recursion to spread the color change to all connected cells.

Steps

1. Store original_color = grid[row][col]
2. If original_color == new_color, return grid (nothing to change)
3. Define recursive helper function fill(r, c):
   • Base cases (when to stop):
     • If out of bounds, return
     • If cell is not the original color, return
   • Recursive case:
     • Change grid[r][c] to new_color
     • Recursively call fill() on all 4 neighbors
4. Call fill(row, col) to start the process
5. Return modified grid

Solution

def flood_fill(grid, row, col, new_color):
    rows = len(grid)
    cols = len(grid[0])
    original_color = grid[row][col]
    
    # If already the target color, nothing to do
    if original_color == new_color:
        return grid
    
    def fill(r, c):
        # Base cases
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != original_color:
            return
        
        # Change color
        grid[r][c] = new_color
        
        # Recursively fill neighbors
        fill(r - 1, c)  # up
        fill(r + 1, c)  # down
        fill(r, c - 1)  # left
        fill(r, c + 1)  # right
    
    fill(row, col)
    return grid

Visual Example

Before flood_fill(grid, 0, 0, 2):
1 1 1
1 0 1
1 1 1

After:
2 2 2
2 0 2
2 2 2

Time Complexity

O(rows × cols) - Worst case: fill entire grid

Space Complexity

O(rows × cols) - Call stack depth in worst case (entire grid connected)

Test Results

grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
result = flood_fill(grid, 0, 0, 2)
# Result: [[2, 2, 2], [2, 0, 2], [2, 2, 2]]

grid2 = [[1, 1, 0], [1, 0, 0], [0, 0, 1]]
result2 = flood_fill(grid2, 0, 0, 5)
# Result: [[5, 5, 0], [5, 0, 0], [0, 0, 1]]

---

Exercise 9: Count Connected Components 🏝️

Problem: Count how many separate regions of a target value exist in the grid.

Approach

Use DFS to mark entire regions, counting each time we start a new DFS.

Steps

1. Create visited grid (all False initially)
2. Initialize region_count = 0
3. Define DFS helper function:
   • Base cases: out of bounds, already visited, or not target value → return
   • Mark current cell as visited
   • Recursively call DFS on all 4 neighbors
4. Main loop: For each cell in grid:
   • If cell equals target AND not visited:
     • Call DFS to mark entire connected region
     • Increment region_count
5. Return region_count

Solution

def count_regions(grid, target):
    if not grid:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    region_count = 0
    
    def dfs(row, col):
        # Base cases
        if (row < 0 or row >= rows or 
            col < 0 or col >= cols or 
            visited[row][col] or 
            grid[row][col] != target):
            return
        
        # Mark as visited
        visited[row][col] = True
        
        # Explore all 4 neighbors
        dfs(row - 1, col)  # up
        dfs(row + 1, col)  # down
        dfs(row, col - 1)  # left
        dfs(row, col + 1)  # right
    
    # Scan entire grid
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == target and not visited[row][col]:
                dfs(row, col)  # Mark entire region
                region_count += 1
    
    return region_count

Visual Example

Grid:
1 1 0 0
1 0 0 1
0 0 1 1

Regions of 1:
Region 1: (0,0), (0,1), (1,0)
Region 2: (1,3)
Region 3: (2,2), (2,3)

Total: 3 regions

Time Complexity

O(rows × cols) - Visit each cell at most twice (once in main loop, once in DFS)

Space Complexity

O(rows × cols) - Visited array + call stack in worst case

Test Results

grid1 = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1]]
print(count_regions(grid1, 1))  # Output: 3

grid2 = [[2, 2, 3], [2, 3, 3], [3, 3, 3]]
print(count_regions(grid2, 3))  # Output: 1
print(count_regions(grid2, 2))  # Output: 1

---

Exercise 10: Maze Path Finder 🗺️

Problem: Determine if a path exists from current position to bottom-right corner.

Approach

Use DFS recursion to explore all possible paths. Return True if ANY path reaches the destination.

Steps

1. Base case - Success: If at destination (rows-1, cols-1) and it's a path (1), return True
2. Base cases - Failure: Return False if:
   • Out of bounds
   • Current cell is a wall (0)
   • Already visited this cell
3. Recursive case:
   • Mark current cell as visited
   • Try moving in all 4 directions
   • If ANY direction returns True, return True
   • If all directions fail, return False

Solution

def has_path(maze, row, col, visited):
    rows = len(maze)
    cols = len(maze[0])
    
    # Base case: reached destination
    if row == rows - 1 and col == cols - 1:
        return maze[row][col] == 1  # Must be a valid path cell
    
    # Base cases: invalid position
    if (row < 0 or row >= rows or 
        col < 0 or col >= cols or 
        maze[row][col] == 0 or 
        (row, col) in visited):
        return False
    
    # Mark as visited
    visited.add((row, col))
    
    # Try all 4 directions
    if has_path(maze, row - 1, col, visited):  # up
        return True
    if has_path(maze, row + 1, col, visited):  # down
        return True
    if has_path(maze, row, col - 1, visited):  # left
        return True
    if has_path(maze, row, col + 1, visited):  # right
        return True
    
    # No path found from this cell
    return False

Visual Example

Maze:
1 0 1
1 1 1
0 0 1

Path exists: (0,0)→(1,0)→(1,1)→(1,2)→(2,2) ✓

Time Complexity

O(rows × cols) - Visit each cell at most once

Space Complexity

O(rows × cols) - Visited set + recursion call stack

Test Results

maze1 = [[1, 0, 1], [1, 1, 1], [0, 0, 1]]
visited1 = set()
print(has_path(maze1, 0, 0, visited1))  # Output: True

maze2 = [[1, 0, 1], [0, 0, 1], [0, 0, 1]]
visited2 = set()
print(has_path(maze2, 0, 0, visited2))  # Output: False

---

🎓 Challenge: Shortest Path Length (BFS)

Problem: Find the length of the shortest path from top-left to bottom-right. Return -1 if no path exists.

Approach

Use BFS with a queue to explore level-by-level, guaranteeing the shortest path.

Steps

1. Handle edge case: If starting cell is a wall, return -1
2. Initialize BFS:
   • Create queue with starting position: deque([(0, 0, 1)]) (row, col, distance)
   • Create visited set: {(0, 0)}
3. BFS loop: While queue is not empty:
   • Dequeue: row, col, dist = queue.popleft()
   • Check destination: If at bottom-right, return dist
   • Explore neighbors: For each of 4 directions:
     • Calculate new position
     • If valid, unvisited, and a path:
       • Mark as visited
       • Enqueue (new_row, new_col, dist + 1)
4. If queue empties without finding destination, return -1

Solution

from collections import deque

def shortest_path_length(maze):
    if not maze or maze[0][0] == 0:
        return -1
    
    rows = len(maze)
    cols = len(maze[0])
    
    # BFS setup
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    
    while queue:
        row, col, dist = queue.popleft()
        
        # Check if reached destination
        if row == rows - 1 and col == cols - 1:
            return dist
        
        # Explore all 4 neighbors
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_row = row + dr
            new_col = col + dc
            
            # Check if valid and unvisited
            if (0 <= new_row < rows and 
                0 <= new_col < cols and
                maze[new_row][new_col] == 1 and
                (new_row, new_col) not in visited):
                
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, dist + 1))
    
    return -1  # No path found

BFS Visualization

Maze:
1 1 0
0 1 0
0 1 1

BFS explores in waves (by distance):
Distance 1: (0,0)
Distance 2: (0,1)
Distance 3: (1,1)
Distance 4: (2,1)
Distance 5: (2,2) ← Destination reached!

Why BFS Guarantees Shortest Path

BFS explores cells in order of increasing distance from the start. The first time we reach the destination is guaranteed to be via the shortest path.

Time Complexity

O(rows × cols) - Visit each cell at most once

Space Complexity

O(rows × cols) - Queue and visited set can contain all cells

Test Results

maze1 = [[1, 1, 0], [0, 1, 0], [0, 1, 1]]
print(shortest_path_length(maze1))  # Output: 5

maze2 = [[1, 0, 1], [1, 1, 1], [0, 0, 1]]
print(shortest_path_length(maze2))  # Output: 5

maze3 = [[1, 0], [0, 1]]
print(shortest_path_length(maze3))  # Output: -1

---

📊 Key Patterns Summary

Grid Traversal Patterns

1. Full Scan (Nested Loops)

for row in range(rows):
    for col in range(cols):
        # Process grid[row][col]

• Use when: Need to visit every cell
• Complexity: O(rows × cols)

2. DFS Recursion (Flood Fill, Connected Components)

def dfs(row, col):
    if out_of_bounds or invalid or visited:
        return
    visited.add((row, col))
    dfs(row-1, col)  # up
    dfs(row+1, col)  # down
    dfs(row, col-1)  # left
    dfs(row, col+1)  # right

• Use when: Need to explore all connected cells
• Complexity: O(rows × cols)
• Space: O(rows × cols) for call stack

3. BFS with Queue (Shortest Path)

queue = deque([(start_row, start_col, 0)])
visited = {(start_row, start_col)}
while queue:
    row, col, dist = queue.popleft()
    for each neighbor:
        if valid and unvisited:
            queue.append((new_row, new_col, dist+1))

• Use when: Need shortest path or level-by-level exploration
• Complexity: O(rows × cols)
• Space: O(rows × cols) for queue

Recursion Checklist

✅ Base Case - When to stop (prevents infinite recursion) ✅ Recursive Case - How to break down the problem ✅ Progress - Each call must get closer to base case

DFS vs BFS Comparison

Feature	DFS	BFS
Implementation	Recursion or Stack	Queue
Exploration	Deep first	Level by level
Best for	Any path, all paths	Shortest path
Space	O(depth)	O(width)

Boundary Checking Pattern

Always validate before accessing grid:

if 0 <= row < rows and 0 <= col < cols:
    # Safe to access grid[row][col]

Common Mistakes to Avoid

❌ Forgetting base case in recursion → infinite loop ❌ Not checking boundaries → index out of range ❌ Not tracking visited cells → infinite loops in DFS ❌ Using DFS when shortest path needed → use BFS instead ❌ Modifying grid during iteration without copying

---

💡 Practice Tips

1. Draw it out - Sketch the grid and trace your algorithm by hand
2. Start small - Test with 2×2 or 3×3 grids first
3. Check edge cases - Empty grids, single cell, all blocked, all open
4. Verify complexity - Count nested loops and recursive calls
5. Use meaningful names - visited, row, col better than v, i, j

Good luck with CCC Question 5! 🚀