Longest Increasing Path In A Matrix

                                            
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] memo = new int[m][n];
        int max = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, dfs(matrix, i, j, Integer.MIN_VALUE, memo));
            }
        }
        
        return max;
    }
    
    private int dfs(int[][] matrix, int i, int j, int prev, int[][] memo) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] <= prev) {
            return 0;
        }
        
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        
        int curr = matrix[i][j];
        int path = 0;
        path = Math.max(path, dfs(matrix, i + 1, j, curr, memo));
        path = Math.max(path, dfs(matrix, i - 1, j, curr, memo));
        path = Math.max(path, dfs(matrix, i, j + 1, curr, memo));
        path = Math.max(path, dfs(matrix, i, j - 1, curr, memo));
        
        memo[i][j] = 1 + path;
        return memo[i][j];
    }
}

                                            
class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """        
        def dfs(i, j):
            if not dp[i][j]:
                val = matrix[i][j]
                dp[i][j] = 1 + max(
                    dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
                    dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
                    dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
                    dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0
                )
            return dp[i][j]
        
        if not matrix or not matrix[0]:
            return 0
        
        M, N = len(matrix), len(matrix[0])
        dp = [[0] * N for _ in range(M)]
        
        return max(dfs(x, y) for x in range(M) for y in range(N))

                                            
int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {
    if (matrix == NULL || matrixSize == 0) return 0;
    
    int m = matrixSize, n = matrixColSize[0];
    int maxLen = 0;
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    int** dp = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        dp[i] = (int*)malloc(n * sizeof(int));
        memset(dp[i], 0, n * sizeof(int));
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            maxLen = fmax(maxLen, dfs(matrix, m, n, i, j, dp, dirs));
        }
    }
    
    for (int i = 0; i < m; i++) {
         free(dp[i]);
    }
    free(dp);
    
    return maxLen;
}

int dfs(int** matrix, int m, int n, int i, int j, int** dp, int dirs[4][2]) {
    if (dp[i][j] > 0) return dp[i][j];
    
    int maxLen = 1;
    for (int k = 0; k < 4; k++) {
        int x = i + dirs[k][0], y = j + dirs[k][1];
        if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
            maxLen = fmax(maxLen, 1 + dfs(matrix, m, n, x, y, dp, dirs));
        }
    }
    
    dp[i][j] = maxLen;
    return maxLen;
}

                                            
public class Solution {
    public int LongestIncreasingPath(int[][] matrix) 
    {
        // Check if the matrix is empty or null
        if (matrix == null || matrix.Length == 0)
            return 0;
        
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        
        int[][] cache = new int[rows][];
        for (int i = 0; i < rows; i++)
        {
            cache[i] = new int[cols];
        }
        
        int maxPath = 0;
        
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                maxPath = Math.Max(maxPath, DFS(matrix, i, j, cache));
            }
        }
        
        return maxPath;
    }
    
    private int DFS(int[][] matrix, int i, int j, int[][] cache)
    {
        if (cache[i][j] != 0)
            return cache[i][j];
        
        int[][] directions = {new int[]{0, 1}, new int[]{0, -1}, new int[]{1, 0}, new int[]{-1, 0}};
        int max = 1;
        
        foreach (int[] dir in directions)
        {
            int x = i + dir[0];
            int y = j + dir[1];
            
            if (x >= 0 && x < matrix.Length && y >= 0 && y < matrix[0].Length && matrix[x][y] > matrix[i][j])
            {
                max = Math.Max(max, 1 + DFS(matrix, x, y, cache));
            }
        }
        
        cache[i][j] = max;
        
        return max;
    }
}

                                            
/**
 * @param {number[][]} matrix
 * @return {number}
 */
const longestIncreasingPath = (matrix) => {
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
    const dfs = (i, j, matrix, dp) => {
        if (dp[i][j] !== 0) return dp[i][j];
        
        let max = 1;
        for (const [dx, dy] of dirs) {
            const x = i + dx;
            const y = j + dy;
            if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= matrix[i][j]) continue;

            const len = 1 + dfs(x, y, matrix, dp);
            max = Math.max(max, len);
        }
        
        dp[i][j] = max;
        return max;
    };
  
    if (!matrix || matrix.length === 0) return 0;
  
    const m = matrix.length;
    const n = matrix[0].length;
    let result = 1;
    const dp = Array.from({ length: m }, () => Array(n).fill(0));
  
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result = Math.max(result, dfs(i, j, matrix, dp));
        }
    }
  
    return result;
};

                                            
function longestIncreasingPath(matrix: number[][]): number {
    if (matrix.length === 0) return 0;
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    
    const memo: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));
    
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    
    const dfs = (row: number, col: number): number => {
        if (memo[row][col] !== 0) return memo[row][col];
        
        let max = 1;
        
        for (const [dx, dy] of directions) {
            const newRow = row + dx;
            const newCol = col + dy;
            
            if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || matrix[newRow][newCol] <= matrix[row][col]) {
                continue;
            }
            
            const len = 1 + dfs(newRow, newCol);
            max = Math.max(max, len);
        }
        
        memo[row][col] = max;
        return max;
    };
    
    let result = 0;
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            result = Math.max(result, dfs(i, j));
        }
    }
    
    return result;
};

                                            
class Solution {
    func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
        guard matrix.count > 0, matrix[0].count > 0 else {
            return 0
        }
        
        let m = matrix.count
        let n = matrix[0].count
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        var result = 0
        
        let dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        
        func dfs(_ i: Int, _ j: Int) -> Int {
            if dp[i][j] != 0 {
                return dp[i][j]
            }
            
            for dir in dirs {
                let x = i + dir[0]
                let y = j + dir[1]
                if x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j] {
                    dp[i][j] = max(dp[i][j], dfs(x, y))
                }
            }
            
            dp[i][j] += 1
            return dp[i][j]
        }
        
        for i in 0..<m {
            for j in 0..<n {
                result = max(result, dfs(i, j))
            }
        }
        
        return result
    }
}

                                            
class Solution {
    fun longestIncreasingPath(matrix: Array<IntArray>): Int {
        val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
        if (matrix.isEmpty() || matrix[0].isEmpty()) return 0
        
        val m = matrix.size
        val n = matrix[0].size
        val cache = Array(m) { IntArray(n) }
        
        fun dfs(x: Int, y: Int): Int {
            if (cache[x][y] != 0) {
                return cache[x][y]
            }
            
            var max = 1
            for (dir in dirs) {
                val nextX = x + dir[0]
                val nextY = y + dir[1]
                if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n || matrix[nextX][nextY] <= matrix[x][y]) {
                    continue
                }
                val len = 1 + dfs(nextX, nextY)
                max = maxOf(max, len)
            }
            
            cache[x][y] = max
            return max
        }
        
        var result = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                result = maxOf(result, dfs(i, j))
            }
        }
        
        return result
    }
}

                                            
class Solution {
  int longestIncreasingPath(List<List<int>> matrix) {
    if (matrix.isEmpty) return 0;

    int maxPath = 0;
    List<List<int>> memo = List.generate(matrix.length, (index) => List.filled(matrix[0].length, 0));

    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[0].length; j++) {
        maxPath = max(maxPath, dfs(matrix, i, j, memo));
      }
    }

    return maxPath;
  }

  int dfs(List<List<int>> matrix, int i, int j, List<List<int>> memo) {
    if (memo[i][j] != 0) return memo[i][j];

    int maxPath = 1;
    List<int> directionsX = [0, 0, -1, 1];
    List<int> directionsY = [-1, 1, 0, 0];

    for (int k = 0; k < 4; k++) {
      int x = i + directionsX[k];
      int y = j + directionsY[k];

      if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= matrix[i][j]) {
        continue;
      }

      maxPath = max(maxPath, 1 + dfs(matrix, x, y, memo));
    }

    memo[i][j] = maxPath;
    return maxPath;
  }

  int max(int a, int b) => a > b ? a : b;
}

                                            
func longestIncreasingPath(matrix [][]int) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    rows := len(matrix)
    cols := len(matrix[0])
    dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    dp := make([][]int, rows)
    for i := range dp {
        dp[i] = make([]int, cols)
    }

    var dfs func(int, int) int
    dfs = func(x, y int) int {
        if dp[x][y] != 0 {
            return dp[x][y]
        }

        dp[x][y]++
        for _, dir := range dirs {
            nx, ny := x+dir[0], y+dir[1]
            if 0 <= nx && nx < rows && 0 <= ny && ny < cols && matrix[nx][ny] > matrix[x][y] {
                dp[x][y] = max(dp[x][y], 1+dfs(nx, ny))
            }
        }
        return dp[x][y]
    }

    res := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            res = max(res, dfs(i, j))
        }
    }

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Integer[][]} matrix
# @return {Integer}
def longest_increasing_path(matrix)
    return 0 if matrix.empty? || matrix[0].empty?
    
    m = matrix.length
    n = matrix[0].length
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    dp = Array.new(m) { Array.new(n, 0) }
    
    def dfs(matrix, dp, i, j, m, n, directions)
        return dp[i][j] if dp[i][j] != 0
        
        max = 1
        directions.each do |dx, dy|
            x = i + dx
            y = j + dy
            
            if x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]
                max = [max, 1 + dfs(matrix, dp, x, y, m, n, directions)].max
            end
        end
        
        dp[i][j] = max
        return dp[i][j]
    end
    
    result = 1
    (0...m).each do |i|
        (0...n).each do |j|
            result = [result, dfs(matrix, dp, i, j, m, n, directions)].max
        end
    end
    
    return result
end

                                            
object Solution {
    def longestIncreasingPath(matrix: Array[Array[Int]]): Int = {
        val rows = matrix.length
        val cols = matrix(0).length
        val directions = List((0, 1), (0, -1), (1, 0), (-1, 0))

        def dfs(x: Int, y: Int, memo: Array[Array[Int]]): Int = {
            if (memo(x)(y) != 0) return memo(x)(y)
            var max = 1
            for ((dx, dy) <- directions) {
                val nextX = x + dx
                val nextY = y + dy
                if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && matrix(nextX)(nextY) > matrix(x)(y)) {
                    max = Math.max(max, 1 + dfs(nextX, nextY, memo))
                }
            }
            memo(x)(y) = max
            max
        }

        var result = 0
        val memo = Array.ofDim[Int](rows, cols)
        for (i <- 0 until rows; j <- 0 until cols) {
            result = Math.max(result, dfs(i, j, memo))
        }
        
        result
    }
}

                                            
impl Solution {
    pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
        let m = matrix.len();
        let n = matrix[0].len();
        
        let mut dp = vec![vec![0; n]; m];
        let directions = vec![(0, 1), (0, -1), (1, 0), (-1, 0)];
        
        fn dfs(matrix: &Vec<Vec<i32>>, dp: &mut Vec<Vec<i32>>, x: usize, y: usize, m: usize, n: usize) -> i32 {
            if dp[x][y] != 0 {
                return dp[x][y];
            }
            
            let mut max_path = 1;
            for dir in [(0, 1), (0, -1), (1, 0), (-1, 0)].iter() {
                let new_x = x as i32 + dir.0;
                let new_y = y as i32 + dir.1;
                
                if new_x >= 0 && new_x < m as i32 && new_y >= 0 && new_y < n as i32 && matrix[new_x as usize][new_y as usize] > matrix[x][y] {
                    let path_len = 1 + dfs(matrix, dp, new_x as usize, new_y as usize, m, n);
                    max_path = max_path.max(path_len);
                }
            }
            
            dp[x][y] = max_path;
            return max_path;
        }
        
        let mut result = 0;
        for i in 0..m {
            for j in 0..n {
                result = result.max(dfs(&matrix, &mut dp, i, j, m, n));
            }
        }
        
        result
    }
}

Explanation

To solve this coding challenge, we are asked to find the longest increasing path in a matrix, where we can move in four directions: up, down, left, and right. The given explanation highlights essential aspects of solving the challenge using a Depth-First Search (DFS) approach with memoization. Here’s a step-by-step explanation:

Grid Dimensions and Edge Cases:

First, check if the matrix or the first row of the matrix is empty. If it's empty, return 0 since there are no paths possible. Determine the dimensions of the matrix

M

(number of rows) and

N

(number of columns).

Memoization Array:

Create a 2D list

dp

of the same dimensions as the matrix to store the longest path found starting from each cell. Initialize all elements in

dp

to 0.

Depth-First Search with Memoization:

Define a helper function

dfs(i, j)

which will calculate the longest increasing path starting at cell

(i, j)

. This function uses memoization to store the result in

dp[i][j]

to avoid redundant calculations. If

dp[i][j]

has already been computed, return its value directly.

DFS Logic:

For cell

(i, j)

, initialize the longest path as 1 (since the cell itself counts as a path). Then consider moving in the four possible directions (up, down, left, right). For each direction, check that the move remains within the matrix boundaries and that the new cell's value is greater than the current cell's value (this ensures the path is increasing). Recursively call

dfs

for valid moves and update the longest path length.

Compute Longest Path for All Cells:

Iterate over each cell in the matrix and apply

dfs

to find the longest increasing path starting from that cell. The result is the maximum value found.

Detailed Steps in Pseudocode:

                                            
# Define the function to get the longest increasing path
function longestIncreasingPath(matrix):
# Check if the matrix or the first row is empty
if matrix is empty or matrix[0] is empty:
return 0

# Get the dimensions of the matrix
M = number of rows in matrix
N = number of columns in matrix

# Initialize the memoization array with zeros
dp = create a 2D list with dimensions M x N filled with 0

# Helper function for DFS with memoization
function dfs(i, j):
# If the result for this cell is already computed, return it
if dp[i][j] is not 0:
return dp[i][j]

# Value of the current cell
val = matrix[i][j]

# Initialize the maximum path length as 1 (the current cell itself)
max_path_length = 1

# Check the upward cell
if i > 0 and val > matrix[i - 1][j]:
max_path_length = max(max_path_length, 1 + dfs(i - 1, j))

# Check the downward cell
if i < M - 1 and val > matrix[i + 1][j]:
max_path_length = max(max_path_length, 1 + dfs(i + 1, j))

# Check the leftward cell
if j > 0 and val > matrix[i][j - 1]:
max_path_length = max(max_path_length, 1 + dfs(i, j - 1))

# Check the rightward cell
if j < N - 1 and val > matrix[i][j + 1]:
max_path_length = max(max_path_length, 1 + dfs(i, j + 1))

# Store the result in dp array for memoization
dp[i][j] = max_path_length
return max_path_length

# Compute the longest increasing path for each cell
longest_path = 0
for each row in range(M):
for each column in range(N):
# Update the longest path
longest_path = max(longest_path, dfs(row, column))

return longest_path

Detailed Steps in Pseudocode Explanation

Function and Matrix Check: Start by defining the primary function
longestIncreasingPath(matrix)

and check if the input matrix is empty. If it’s empty, early exit by returning 0.
Dimensions and Initialization: Retrieve the dimensions of the matrix
M

(rows) and
N

(columns). Then, initialize a memoization array
dp

with dimensions
M x N

to keep track of the longest path located at each cell.
DFS with Memoization Logic:

Define a helper function named
dfs(i, j)

which returns the length of the longest increasing path starting from cell
(i, j)

.
Check if the value for cell
(i, j)

is already computed in
dp

. If so, return it directly.
Initialize the current cell path length and value, then explore each direction: up, down, left, right. For each direction, check boundaries and value conditions, recursively call
dfs

if valid, and update the maximum path length.
Store the computed value in the
dp

array for future reference and return it.

Longest Path Calculation: Iterate through each cell in the matrix, applying the
dfs

function, and track the maximum value. Finally, return the maximum path length.