1"use strict";(self.webpackChunk_N_E=self.webpackChunk_N_E||[]).push([[10348],{2722:function(n,r,e){e.d(r,{LongestIncreasingPathRenderer:function(){return o}});var t=e(57437);e(2265);var i=e(63832),a=e(46387);let o=n=>{let{frame:r}=n,{matrix:e,memo:o,currentCell:s,path:c,longestPath:l,longestPathCells:m,message:x}=r.state,d=(n,r,e)=>{var t;let i=s&&s[0]===n&&s[1]===r,a=c.some(e=>{let[t,i]=e;return t===n&&i===r}),l=m.some(e=>{let[t,i]=e;return t===n&&i===r}),x=null===(t=o[n])||void 0===t?void 0:t[r],d="#18181b",f="#3f3f46";return i?(d="rgba(234, 179, 8, 0.35)",f="#eab308"):l&&!e?(d="rgba(34, 197, 94, 0.3)",f="#22c55e"):a&&!e?(d="rgba(59, 130, 246, 0.25)",f="#3b82f6"):e&&void 0!==x&&x>0&&(d="rgba(139, 92, 246, 0.2)",f="#8b5cf6"),{width:44,height:44,display:"flex",alignItems:"center",justifyContent:"center",backgroundColor:d,border:"2px solid ".concat(f),borderRadius:"6px",transition:"all 0.2s ease"}},f=(n,r,e)=>{var t;let i=s&&s[0]===n&&s[1]===r,a=m.some(e=>{let[t,i]=e;return t===n&&i===r}),c=null===(t=o[n])||void 0===t?void 0:t[r];return i?"#fbbf24":a&&!e?"#4ade80":e&&void 0!==c&&c>0?"#c4b5fd":"#a1a1aa"};return(0,t.jsxs)(i.Z,{sx:{display:"flex",flexDirection:"column",alignItems:"center",gap:3,p:3,width:"100%"},children:[(0,t.jsx)(i.Z,{sx:{px:3,py:1.5,bgcolor:"#1e1e1e",borderRadius:2,border:"1px solid #3f3f46"},children:(0,t.jsx)(a.Z,{sx:{color:"#a1a1aa",fontFamily:"monospace",fontSize:"14px"},children:x})}),(0,t.jsxs)(i.Z,{sx:{display:"flex",gap:4,flexWrap:"wrap",justifyContent:"center"},children:[(0,t.jsxs)(i.Z,{sx:{display:"flex",flexDirection:"column",alignItems:"center",gap:1},children:[(0,t.jsx)(a.Z,{sx:{color:"#71717a",fontSize:"12px"},children:"Input Matrix"}),(0,t.jsx)(i.Z,{sx:{display:"inline-block",borderRadius:"8px",overflow:"hidden",border:"2px solid #3f3f46"},children:e.map((n,r)=>(0,t.jsx)(i.Z,{sx:{display:"flex"},children:n.map((n,e)=>(0,t.jsx)(i.Z,{sx:d(r,e,!1),children:(0,t.jsx)(a.Z,{sx:{color:f(r,e,!1),fontFamily:"monospace",fontSize:"14px",fontWeight:600},children:n})},e))},r))})]}),(0,t.jsxs)(i.Z,{sx:{display:"flex",flexDirection:"column",alignItems:"center",gap:1},children:[(0,t.jsx)(a.Z,{sx:{color:"#71717a",fontSize:"12px"},children:"Memo (longest path from cell)"}),(0,t.jsx)(i.Z,{sx:{display:"inline-block",borderRadius:"8px",overflow:"hidden",border:"2px solid #3f3f46"},children:o.map((n,r)=>(0,t.jsx)(i.Z,{sx:{display:"flex"},children:n.map((n,e)=>(0,t.jsx)(i.Z,{sx:d(r,e,!0),children:(0,t.jsx)(a.Z,{sx:{color:f(r,e,!0),fontFamily:"monospace",fontSize:"14px",fontWeight:600},children:n>0?n:"-"})},e))},r))})]})]}),(0,t.jsx)(i.Z,{sx:{px:4,py:2,bgcolor:"#1f1f23",borderRadius:2,border:"1px solid #3f3f46"},children:(0,t.jsxs)(a.Z,{sx:{color:"#71717a",fontSize:"13px"},children:["Longest Increasing Path: ",(0,t.jsx)("span",{style:{color:"#4ade80",fontWeight:700,fontSize:"16px"},children:l})]})}),(0,t.jsxs)(i.Z,{sx:{display:"flex",gap:3,mt:1,flexWrap:"wrap",justifyContent:"center"},children:[(0,t.jsxs)(i.Z,{sx:{display:"flex",alignItems:"center",gap:1},children:[(0,t.jsx)(i.Z,{sx:{width:14,height:14,bgcolor:"rgba(234, 179, 8, 0.35)",borderRadius:"3px",border:"1px solid #eab308"}}),(0,t.jsx)(a.Z,{sx:{color:"#71717a",fontSize:"12px"},children:"Current"})]}),(0,t.jsxs)(i.Z,{sx:{display:"flex",alignItems:"center",gap:1},children:[(0,t.jsx)(i.Z,{sx:{width:14,height:14,bgcolor:"rgba(59, 130, 246, 0.25)",borderRadius:"3px",border:"1px solid #3b82f6"}}),(0,t.jsx)(a.Z,{sx:{color:"#71717a",fontSize:"12px"},children:"Exploring"})]}),(0,t.jsxs)(i.Z,{sx:{display:"flex",alignItems:"center",gap:1},children:[(0,t.jsx)(i.Z,{sx:{width:14,height:14,bgcolor:"rgba(34, 197, 94, 0.3)",borderRadius:"3px",border:"1px solid #22c55e"}}),(0,t.jsx)(a.Z,{sx:{color:"#71717a",fontSize:"12px"},children:"Longest Path"})]})]})]})}},10348:function(n,r,e){e.r(r),e.d(r,{LongestIncreasingPathInAMatrix:function(){return t}});let t={id:"longest-increasing-path-in-a-matrix",label:"Longest Increasing Path in a Matrix",description:"Given an m x n integers matrix, return the length of the longest increasing path in matrix. From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary.",constraints:["$m == \\text{matrix.length}$","$n == \\text{matrix}[i].\\text{length}$","$1 \\leq m, n \\leq 200$","$0 \\leq \\text{matrix}[i][j] \\leq 2^{31} - 1$"],topics:["array","dynamic-programming","depth-first-search","breadth-first-search","graph","topological-sort","memoization","matrix"],companies:["Amazon","Google","Microsoft","Bloomberg"],category:"Dynamic Programming",difficulty:"Hard",code:{python:"class Solution:\n def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n if not matrix:\n return 0\n\n m, n = len(matrix), len(matrix[0])\n memo = [[0] * n for _ in range(m)]\n\n def dfs(r, c):\n if memo[r][c]:\n return memo[r][c]\n\n directions = [(0,1),(0,-1),(1,0),(-1,0)]\n max_len = 1\n for dr, dc in directions:\n nr, nc = r + dr, c + dc\n if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:\n max_len = max(max_len, 1 + dfs(nr, nc))\n\n memo[r][c] = max_len\n return max_len\n\n return max(dfs(r, c) for r in range(m) for c in range(n))",javascript:"function longestIncreasingPath(matrix) {\n if (!matrix.length) return 0;\n\n const m = matrix.length, n = matrix[0].length;\n const memo = Array.from({length: m}, () => Array(n).fill(0));\n const directions = [[0,1],[0,-1],[1,0],[-1,0]];\n\n function dfs(r, c) {\n if (memo[r][c]) return memo[r][c];\n\n let maxLen = 1;\n for (const [dr, dc] of directions) {\n const nr = r + dr, nc = c + dc;\n if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c]) {\n maxLen = Math.max(maxLen, 1 + dfs(nr, nc));\n }\n }\n\n memo[r][c] = maxLen;\n return maxLen;\n }\n\n let result = 0;\n for (let r = 0; r < m; r++) {\n for (let c = 0; c < n; c++) {\n result = Math.max(result, dfs(r, c));\n }\n }\n return result;\n}",typescript:"function longestIncreasingPath(matrix: number[][]): number {\n if (!matrix.length) return 0;\n\n const m = matrix.length, n = matrix[0].length;\n const memo: number[][] = Array.from({length: m}, () => Array(n).fill(0));\n const directions = [[0,1],[0,-1],[1,0],[-1,0]];
1\n\n function dfs(r: number, c: number): number {\n if (memo[r][c]) return memo[r][c];\n\n let maxLen = 1;\n for (const [dr, dc] of directions) {\n const nr = r + dr, nc = c + dc;\n if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c]) {\n maxLen = Math.max(maxLen, 1 + dfs(nr, nc));\n }\n }\n\n memo[r][c] = maxLen;\n return maxLen;\n }\n\n let result = 0;\n for (let r = 0; r < m; r++) {\n for (let c = 0; c < n; c++) {\n result = Math.max(result, dfs(r, c));\n }\n }\n return result;\n}",java:"class Solution {\n int[][] memo;\n int[][] matrix;\n int m, n;\n int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};\n\n public int longestIncreasingPath(int[][] matrix) {\n if (matrix.length == 0) return 0;\n this.matrix = matrix;\n m = matrix.length;\n n = matrix[0].length;\n memo = new int[m][n];\n\n int result = 0;\n for (int r = 0; r < m; r++) {\n for (int c = 0; c < n; c++) {\n result = Math.max(result, dfs(r, c));\n }\n }\n return result;\n }\n\n private int dfs(int r, int c) {\n if (memo[r][c] != 0) return memo[r][c];\n\n int maxLen = 1;\n for (int[] d : directions) {\n int nr = r + d[0], nc = c + d[1];\n if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c]) {\n maxLen = Math.max(maxLen, 1 + dfs(nr, nc));\n }\n }\n\n memo[r][c] = maxLen;\n return maxLen;\n }\n}",cpp:"class Solution {\npublic:\n vector<vector<int>> memo;\n int m, n;\n vector<pair<int,int>> directions = {{0,1},{0,-1},{1,0},{-1,0}};\n\n int longestIncreasingPath(vector<vector<int>>& matrix) {\n if (matrix.empty()) return 0;\n m = matrix.size();\n n = matrix[0].size();\n memo.assign(m, vector<int>(n, 0));\n\n int result = 0;\n for (int r = 0; r < m; r++) {\n for (int c = 0; c < n; c++) {\n result = max(result, dfs(matrix, r, c));\n }\n }\n return result;\n }\n\n int dfs(vector<vector<int>>& matrix, int r, int c) {\n if (memo[r][c]) return memo[r][c];\n\n int maxLen = 1;\n for (auto [dr, dc] : directions) {\n int nr = r + dr, nc = c + dc;\n if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c]) {\n maxLen = max(maxLen, 1 + dfs(matrix, nr, nc));\n }\n }\n\n memo[r][c] = maxLen;\n return maxLen;\n }\n};",csharp:"public class Solution {\n int[,] memo;\n int[][] matrix;\n int m, n;\n int[][] directions = new int[][] {\n new[] {0,1}, new[] {0,-1}, new[] {1,0}, new[] {-1,0}\n };\n\n public int LongestIncreasingPath(int[][] matrix) {\n if (matrix.Length == 0) return 0;\n this.matrix = matrix;\n m = matrix.Length;\n n = matrix[0].Length;\n memo = new int[m, n];\n\n int result = 0;\n for (int r = 0; r < m; r++) {\n for (int c = 0; c < n; c++) {\n result = Math.Max(result, Dfs(r, c));\n }\n }\n return result;\n }\n\n private int Dfs(int r, int c) {\n if (memo[r, c] != 0) return memo[r, c];\n\n int maxLen = 1;\n foreach (var d in directions) {\n int nr = r + d[0], nc = c + d[1];\n if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c]) {\n maxLen = Math.Max(maxLen, 1 + Dfs(nr, nc));\n }\n }\n\n memo[r, c] = maxLen;\n return maxLen;\n }\n}",go:"func longestIncreasingPath(matrix [][]int) int {\n if len(matrix) == 0 {\n return 0\n }\n\n m, n := len(matrix), len(matrix[0])\n memo := make([][]int, m)\n for i := range memo {\n memo[i] = make([]int, n)\n }\n directions := [][]int{{0,1},{0,-1},{1,0},{-1,0}}\n\n var dfs func(r, c int) int\n dfs = func(r, c int) int {\n if memo[r][c] != 0 {\n return memo[r][c]\n }\n\n maxLen := 1\n for _, d := range directions {\n nr, nc := r+d[0], c+d[1]\n if nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c] {\n if l := 1 + dfs(nr, nc); l > maxLen {\n maxLen = l\n }\n }\n }\n\n memo[r][c] = maxLen\n return maxLen\n }\n\n result := 0\n for r := 0; r < m; r++ {\n for c := 0; c < n; c++ {\n if l := dfs(r, c); l > result {\n result = l\n }\n }\n }\n return result\n}"},lineMapping:{python:{init:6,dfs:9,explore:15,memo:19,done:22},javascript:{init:5,dfs:8,explore:13,memo:18,done:26},typescript:{init:5,dfs:8,explore:13,memo:18,done:26},java:{init:10,dfs:21,explore:26,memo:31,done:18},cpp:{init:10,dfs:20,explore:25,memo:30,done:17},csharp:{init:13,dfs:24,explore:29,memo:34,done:21},go:{init:11,dfs:15,explore:22,memo:28,done:35}},presets:[{label:"Example 1",data:[[9,9,4],[6,6,8],[2,1,1]],expected:"4"},{label:"Example 2",data:[[3,4,5],[3,2,6],[2,2,1]],expected:"4"},{label:"Single",data:[[1]],expected:"1"}],defaultInput:[[9,9,4],[6,6,8],[2,1,1]],defaultExpected:"4",Renderer:e(2722).LongestIncreasingPathRenderer,functionSignature:{name:"longestIncreasingPath",params:[{name:"matrix",type:"int[][]"}],returnType:"int"},starterCode:{python:"class Solution:\n def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n # Write your solution here\n return 0",javascript:"/**\n * @param {number[][]} matrix\n * @return {number}\n */\nvar longestIncreasingPath = function(matrix) {\n // Write your solution here\n return 0;\n};",typescript:"function longestIncreasingPath(matrix: number[][]): number {\n // Write your solution here\n return 0;\n}",java:"class Solution {\n public int longestIncreasingPath(int[][] matrix) {\n // Write your solution here\n return 0;\n }\n}",cpp:"class Solution {\npublic:\n int longestIncreasingPath(vector<vector<int>>
1& matrix) {\n // Write your solution here\n return 0;\n }\n};",csharp:"public class Solution {\n public int LongestIncreasingPath(int[][] matrix) {\n // Write your solution here\n return 0;\n }\n}",go:"func longestIncreasingPath(matrix [][]int) int {\n // Write your solution here\n return 0\n}"},generateFrames:n=>{let r=[];if(0===n.length)return r.push({stepId:"done",line:1,state:{matrix:[],memo:[],currentCell:null,path:[],longestPath:0,longestPathCells:[],message:"Empty matrix"}}),r;let e=n.length,t=n[0].length,i=Array.from({length:e},()=>Array(t).fill(0)),a=[[0,1],[0,-1],[1,0],[-1,0]],o=0,s=[],c=(r,e,t,a,o)=>({matrix:n,memo:i.map(n=>[...n]),currentCell:e,path:[...t],longestPath:a,longestPathCells:[...o],message:r});r.push({stepId:"init",line:1,state:c("Initialize DFS with memoization",null,[],0,[])});for(let l=0;l<e;l++)for(let m=0;m<t;m++){let x=function r(o,s){if(i[o][s])return i[o][s];let c=1;for(let[i,l]of a){let a=o+i,m=s+l;a>=0&&a<e&&m>=0&&m<t&&n[a][m]>n[o][s]&&(c=Math.max(c,1+r(a,m)))}return i[o][s]=c,c}(l,m);x>o&&(o=x,s=[[l,m]]),r.push({stepId:"dfs",line:2,state:c("DFS from (".concat(l,",").concat(m,"): longest path = ").concat(x),[l,m],[],o,s)})}return r.push({stepId:"done",line:3,state:c("Longest increasing path: ".concat(o),null,[],o,s)}),r}}}}]);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.