DSA Graphs, Backtracking and Dynamic Programming Practice

Practise BFS, DFS, shortest paths, topological sort, backtracking and dynamic programming.

Advanced8 problemsUpdated October 24, 2026

Review first: Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's Shortest Path, Topological Sort, Backtracking, 1D Dynamic Programming, 2D Dynamic Programming

1.Flood fill

Intermediate

Starting from cell (1, 1), change that cell and every connected cell (up, down, left, right) of the same colour to colour 2, like a paint bucket tool. Grid [[1, 1, 1], [1, 1, 0], [1, 0, 1]]. Print the rows.

Show hint

DFS with an explicit stack from the start cell. Record the original colour first, and stop if it already equals the new colour.

Show solution

Python

def flood_fill(grid, r, c, new):
    old = grid[r][c]
    if old == new:
        return grid
    stack = [(r, c)]
    while stack:
        i, j = stack.pop()
        if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == old:
            grid[i][j] = new
            stack.extend([(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)])
    return grid

for row in flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2):
    print(row)

Output

[2, 2, 2]
[2, 2, 0]
[2, 0, 1]

The bottom-right 1 is not connected to the start (only diagonally), so it keeps its colour.

2.Shortest path in a binary grid

Intermediate

In a grid of 0 (open) and 1 (wall), find the fewest cells on a path from the top-left to the bottom-right, moving in 8 directions (including diagonals). Return -1 if there is no path. Test [[0, 0, 0], [1, 1, 0], [1, 1, 0]].

Show hint

BFS from the start, counting path length in cells. Check both corners are open first.

Show solution

Python

from collections import deque

def shortest_path(grid):
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    queue = deque([(0, 0, 1)])
    seen = {(0, 0)}
    while queue:
        r, c, length = queue.popleft()
        if (r, c) == (n - 1, n - 1):
            return length
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not grid[nr][nc] and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    queue.append((nr, nc, length + 1))
    return -1

print(shortest_path([[0, 0, 0], [1, 1, 0], [1, 1, 0]]))
print(shortest_path([[0, 1], [1, 0]]))
print(shortest_path([[1, 0], [0, 0]]))

Output

4
2
-1

In the second grid the diagonal step from (0, 0) to (1, 1) is allowed, so the path has 2 cells.

3.Cheapest route

Advanced

Find the cheapest cost from "A" to every other city with Dijkstra's algorithm. Roads (one way, with costs): A→B 5, A→C 1, C→B 2, B→D 1, C→D 6, D→E 3.

Show hint

A heap of (cost, city) pairs; skip entries whose cost is larger than the best already known.

Show solution

Python

import heapq

roads = {"A": [("B", 5), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 6)], "D": [("E", 3)], "E": []}

def dijkstra(graph, start):
    dist = {city: float("inf") for city in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return dist

print(dijkstra(roads, "A"))

Output

{'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

A → C → B costs 3, cheaper than the direct road of 5, and every route to D and E goes through it.

4.Build order

Advanced

Packages depend on others: app needs ui and api, ui needs core, api needs core and db. Print a valid installation order (dependencies first) using Kahn's algorithm, taking ready packages in alphabetical order.

Show hint

Edges go from a dependency to the package that needs it. Keep the ready packages in a heap so the alphabetical rule is easy.

Show solution

Python

import heapq

needs = {"app": ["ui", "api"], "ui": ["core"], "api": ["core", "db"], "core": [], "db": []}

def build_order(needs):
    users = {p: [] for p in needs}
    remaining = {p: len(deps) for p, deps in needs.items()}
    for p, deps in needs.items():
        for d in deps:
            users[d].append(p)
    ready = [p for p, n in remaining.items() if n == 0]
    heapq.heapify(ready)
    order = []
    while ready:
        p = heapq.heappop(ready)
        order.append(p)
        for u in users[p]:
            remaining[u] -= 1
            if remaining[u] == 0:
                heapq.heappush(ready, u)
    return order if len(order) == len(needs) else None

print(build_order(needs))

Output

['core', 'db', 'api', 'ui', 'app']

5.Unique permutations

Advanced

Print all distinct orderings of [1, 1, 2] without generating duplicates and then removing them.

Show hint

Count how many of each value remain. At each position, try each distinct value that still has a count above zero.

Show solution

Python

from collections import Counter

def unique_permutations(nums):
    counts = Counter(nums)
    result, current = [], []
    def build():
        if len(current) == len(nums):
            result.append(current[:])
            return
        for value in sorted(counts):
            if counts[value]:
                counts[value] -= 1
                current.append(value)
                build()
                current.pop()
                counts[value] += 1
    build()
    return result

print(unique_permutations([1, 1, 2]))

Output

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Branching on distinct values (not positions) means equal values are never chosen in two different orders.

6.Minimum cost climbing stairs
Intermediate
Each step has a cost you pay when you stand on it. You may start on step 0 or 1 and climb 1 or 2 steps at a time; reaching beyond the last step is the top. Find the minimum total cost for [10, 15, 20] and [1, 100, 1, 1, 1, 100, 1, 1, 100, 1].
Show hint
The cost to reach step i is cost[i] + min(reach[i-1], reach[i-2]); the answer is the cheaper of the last two steps.
Show solution
Python
def min_cost(cost): a, b = cost[0], cost[1] for c in cost[2:]: a, b = b, c + min(a, b) return min(a, b) print(min_cost([10, 15, 20])) print(min_cost([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
Output
15 6

7.Grid paths with obstacles

Advanced

Count the paths from the top-left to the bottom-right of a grid, moving only right or down, where 1 marks a blocked cell. Test [[0, 0, 0], [0, 1, 0], [0, 0, 0]].

Show hint

2D DP where a blocked cell has 0 paths. A single row dp is enough if you update it left to right.

Show solution

Python

def paths(grid):
    cols = len(grid[0])
    dp = [0] * cols
    dp[0] = 1
    for row in grid:
        for c in range(cols):
            if row[c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[-1]

print(paths([[0, 0, 0], [0, 1, 0], [0, 0, 0]]))
print(paths([[0, 1], [0, 0]]))

Output

2
1

Before updating, dp[c] still holds the count from the row above; adding dp[c - 1] brings in the cell to the left.

8.Longest common subsequence

Advanced

Print the length of the longest common subsequence of "abcde" and "ace", and of "abc" and "def".

Show hint

dp[i][j] is the LCS of the first i and j characters: on a match take dp[i-1][j-1] + 1, otherwise the larger of dp[i-1][j] and dp[i][j-1].

Show solution

Python

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]

print(lcs("abcde", "ace"), lcs("abc", "def"))

Output

3 0

← All practice sets Learn Data Structures and Algorithms course →