DSA 450 Notes

Problem Statement

Given an m×n matrix where some cells are blocked (marked as 0) and others are open (marked as 1), find the longest path from a given source cell to a destination cell. You can move in four directions: up, down, left, right. Each cell can be visited at most once.

Example:

Input:
matrix = [
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [1, 1, 0, 1, 1, 0, 1, 1, 0, 1],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
source = (0, 0), destination = (2, 9)

Output: 24
Explanation: The longest path avoids blocked cells and visits maximum cells.

Approach 1: Brute Force (DFS with Backtracking)

Intuition

Use DFS to explore all possible paths from source to destination. Track the path length and update the maximum when destination is reached. Backtrack to explore all alternatives.

Algorithm

Start from source with path length 1
Mark current cell as visited
Try all 4 directions
If destination reached, update maximum length
Backtrack by unmarking cell

java

import java.util.*;

class Solution {
    private int[] dr = {-1, 0, 1, 0};
    private int[] dc = {0, 1, 0, -1};
    private int maxLen;
    
    public void dfs(int[][] matrix, int row, int col, int destRow, int destCol,
                    int len, boolean[][] visited) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // Reached destination
        if (row == destRow && col == destCol) {
            maxLen = Math.max(maxLen, len);
            return;
        }
        
        visited[row][col] = true;
        
        // Try all 4 directions
        for (int i = 0; i < 4; i++) {
            int newRow = row + dr[i];
            int newCol = col + dc[i];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                matrix[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                dfs(matrix, newRow, newCol, destRow, destCol, len + 1, visited);
            }
        }
        
        visited[row][col] = false;  // Backtrack
    }
    
    public int longestPath(int[][] matrix, int srcRow, int srcCol,
                           int destRow, int destCol) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        if (matrix[srcRow][srcCol] == 0 || matrix[destRow][destCol] == 0) {
            return -1;
        }
        
        maxLen = Integer.MIN_VALUE;
        boolean[][] visited = new boolean[m][n];
        
        dfs(matrix, srcRow, srcCol, destRow, destCol, 1, visited);
        
        return maxLen == Integer.MIN_VALUE ? -1 : maxLen;
    }
}

Complexity Analysis

Time Complexity: O(4^(m×n)) - Exponential exploration
Space Complexity: O(m×n) - Visited array and recursion stack

Approach 2: Optimal (DFS with Memoization - Limited Applicability)

Intuition

For longest path, standard DP/memoization doesn't work directly due to the visited constraint. However, we can use BFS for shortest path and verify longest is needed.

For this problem, backtracking is the standard approach.

java

import java.util.*;

class Solution {
    private int[] dr = {-1, 0, 1, 0};
    private int[] dc = {0, 1, 0, -1};
    
    public int dfs(int[][] matrix, int row, int col, int destRow, int destCol,
                   boolean[][] visited) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        if (row == destRow && col == destCol) {
            return 1;
        }
        
        visited[row][col] = true;
        int maxPath = -1;
        
        for (int i = 0; i < 4; i++) {
            int newRow = row + dr[i];
            int newCol = col + dc[i];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                matrix[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                
                int pathLen = dfs(matrix, newRow, newCol, destRow, destCol, visited);
                if (pathLen != -1) {
                    maxPath = Math.max(maxPath, pathLen + 1);
                }
            }
        }
        
        visited[row][col] = false;
        return maxPath;
    }
    
    public int longestPath(int[][] matrix, int srcRow, int srcCol,
                           int destRow, int destCol) {
        if (matrix[srcRow][srcCol] == 0 || matrix[destRow][destCol] == 0) {
            return -1;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        
        return dfs(matrix, srcRow, srcCol, destRow, destCol, visited);
    }
}

Complexity Analysis

Time Complexity: O(4^(m×n)) - Still exponential
Space Complexity: O(m×n) - Visited array

Key Takeaways

Longest Path is Hard: NP-complete in general graphs
Backtracking Required: Must explore all paths due to visited constraint
No DP Shortcut: Standard memoization doesn't work for longest path
4-Directional: Up, down, left, right movement
Return -1: When no path exists
Path Length: Number of cells visited (not edges)

Longest Possible Route in a Matrix with Hurdles

Problem Statement

Approach 1: Brute Force (DFS with Backtracking)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (DFS with Memoization - Limited Applicability)

Intuition

Complexity Analysis

Key Takeaways