1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/**
 * DFS with Memoization
 * Time Complexity: O(m * n) - We visit each cell exactly once and perform constant work for each cell
 * Space Complexity: O(m * n) - We use a memo table of size m * n to store the longest path starting from each cell
 * 
 * @param {number[][]} matrix - The input matrix
 * @return {number} - The length of the longest increasing path
 */
function longestIncreasingPath(matrix) {
  if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
    return 0;
  }
  
  const m = matrix.length;
  const n = matrix[0].length;
  const memo = Array(m).fill().map(() => Array(n).fill(0));
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right
  
  function dfs(i, j) {
    // If we've already computed the result for this cell, return it
    if (memo[i][j] !== 0) {
      return memo[i][j];
    }
    
    // Initialize the longest path from this cell as 1 (counting the current cell)
    let longest = 1;
    
    // Explore all four adjacent cells
    for (const [di, dj] of directions) {
      const ni = i + di;
      const nj = j + dj;
      
      // Check if the adjacent cell is within bounds and has a higher value
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
        // Update the longest path if a longer path is found
        longest = Math.max(longest, 1 + dfs(ni, nj));
      }
    }
    
    // Memoize the result and return it
    memo[i][j] = longest;
    return longest;
  }
  
  // Find the longest path starting from each cell
  let result = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      result = Math.max(result, dfs(i, j));
    }
  }
  
  return result;
}
 
/**
 * Topological Sort (Kahn's Algorithm)
 * Time Complexity: O(m * n) - We process each cell exactly once and perform constant work for each cell
 * Space Complexity: O(m * n) - We use additional space for the graph, in-degree array, queue, and distances array
 * 
 * @param {number[][]} matrix - The input matrix
 * @return {number} - The length of the longest increasing path
 */
function longestIncreasingPathTopological(matrix) {
  if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
    return 0;
  }
  
  const m = matrix.length;
  const n = matrix[0].length;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right
  
  // Calculate in-degree of each cell
  const inDegree = Array(m).fill().map(() => Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      for (const [di, dj] of directions) {
        const ni = i + di;
        const nj = j + dj;
        
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
          inDegree[i][j]++;
        }
      }
    }
  }
  
  // Initialize queue with cells that have in-degree 0
  const queue = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (inDegree[i][j] === 0) {
        queue.push([i, j]);
      }
    }
  }
  
  // Initialize distances array
  const distances = Array(m).fill().map(() => Array(n).fill(1));
  
  // Process cells in topological order
  while (queue.length > 0) {
    const [i, j] = queue.shift();
    
    for (const [di, dj] of directions) {
      const ni = i + di;
      const nj = j + dj;
      
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] < matrix[i][j]) {
        distances[ni][nj] = Math.max(distances[ni][nj], distances[i][j] + 1);
        inDegree[ni][nj]--;
        
        if (inDegree[ni][nj] === 0) {
          queue.push([ni, nj]);
        }
      }
    }
  }
  
  // Find the maximum distance
  let result = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      result = Math.max(result, distances[i][j]);
    }
  }
  
  return result;
}
 
// Test cases
const matrix1 = [
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
];
console.log(longestIncreasingPath(matrix1)); // 4
 
const matrix2 = [
  [3, 4, 5],
  [3, 2, 6],
  [2, 2, 1]
];
console.log(longestIncreasingPath(matrix2)); // 4
 
const matrix3 = [[1]];
console.log(longestIncreasingPath(matrix3)); // 1