DSA 450 Notes

Problem Statement

Given a N x N maze with 0s and 1s, where 0 represents a blocked cell and 1 represents an open cell. A rat starts from the source (0, 0) and has to reach the destination (N-1, N-1). The rat can move in four directions: Up (U), Down (D), Left (L), Right (R). Find all possible paths from source to destination.

Example:

Input:
maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [1, 1, 0, 0],
  [0, 1, 1, 1]
]

Output: ["DDRDRR", "DRDDRR"]

Explanation:
Path 1: Down -> Down -> Right -> Down -> Right -> Right
Path 2: Down -> Right -> Down -> Down -> Right -> Right

Approach 1: Brute Force (Simple Recursion)

Intuition

Try all possible paths from source to destination by exploring all four directions at each cell. Mark cells as visited to avoid cycles, and backtrack when a path doesn't lead to the destination.

Algorithm

Start from (0, 0) and explore all four directions
For each direction, check if the move is valid (within bounds, cell is 1, not visited)
If valid, mark as visited, add direction to path, and recurse
If destination reached, store the path
Backtrack by unmarking the cell

java

import java.util.*;

class Solution {
    public void solve(int row, int col, int[][] maze, int n, 
                      String path, List<String> result) {
        // Base case: reached destination
        if (row == n - 1 && col == n - 1) {
            result.add(path);
            return;
        }
        
        // Mark current cell as visited
        maze[row][col] = 0;
        
        // Try all four directions: Down, Left, Right, Up
        // Down
        if (row + 1 < n && maze[row + 1][col] == 1) {
            solve(row + 1, col, maze, n, path + 'D', result);
        }
        // Left
        if (col - 1 >= 0 && maze[row][col - 1] == 1) {
            solve(row, col - 1, maze, n, path + 'L', result);
        }
        // Right
        if (col + 1 < n && maze[row][col + 1] == 1) {
            solve(row, col + 1, maze, n, path + 'R', result);
        }
        // Up
        if (row - 1 >= 0 && maze[row - 1][col] == 1) {
            solve(row - 1, col, maze, n, path + 'U', result);
        }
        
        // Backtrack
        maze[row][col] = 1;
    }
    
    public List<String> findPath(int[][] maze, int n) {
        List<String> result = new ArrayList<>();
        if (maze[0][0] == 0 || maze[n-1][n-1] == 0) {
            return result;
        }
        solve(0, 0, maze, n, "", result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(4^(n²)) - At each cell, we have 4 choices
Space Complexity: O(n²) - Recursion stack depth can go up to n² in worst case

Approach 2: Optimal (Using Direction Arrays)

Intuition

Use direction arrays to make the code cleaner and more maintainable. This approach is essentially the same time complexity but with cleaner implementation.

Algorithm

Use direction arrays for movement (dr, dc) and direction characters
Iterate through all directions using a loop
This makes it easier to add or modify directions

java

import java.util.*;

class Solution {
    private int[] dr = {1, 0, 0, -1};  // Down, Left, Right, Up
    private int[] dc = {0, -1, 1, 0};
    private char[] dir = {'D', 'L', 'R', 'U'};
    
    public void solve(int row, int col, int[][] maze, int n, 
                      String path, List<String> result, boolean[][] visited) {
        // Base case: reached destination
        if (row == n - 1 && col == n - 1) {
            result.add(path);
            return;
        }
        
        // Try all four directions
        for (int i = 0; i < 4; i++) {
            int newRow = row + dr[i];
            int newCol = col + dc[i];
            
            if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n &&
                maze[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                visited[row][col] = true;
                solve(newRow, newCol, maze, n, path + dir[i], result, visited);
                visited[row][col] = false;
            }
        }
    }
    
    public List<String> findPath(int[][] maze, int n) {
        List<String> result = new ArrayList<>();
        boolean[][] visited = new boolean[n][n];
        
        if (maze[0][0] == 0 || maze[n-1][n-1] == 0) {
            return result;
        }
        
        solve(0, 0, maze, n, "", result, visited);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(4^(n²)) - At each cell, we have 4 choices
Space Complexity: O(n²) - For visited array and recursion stack

Key Takeaways

Backtracking Pattern: Mark visited, explore, unmark (backtrack)
Direction Arrays: Using dr[], dc[] arrays makes code cleaner and extensible
Lexicographical Order: Direction order (D, L, R, U) ensures lexicographically sorted paths
Early Termination: Check if start/end cells are blocked before starting
Visited Tracking: Essential to avoid infinite loops in paths that can revisit cells
Classic Backtracking: Foundation for understanding more complex maze/path problems

Rat in a maze Problem

Problem Statement

Approach 1: Brute Force (Simple Recursion)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Using Direction Arrays)

Intuition

Algorithm

Complexity Analysis

Key Takeaways