# Intuition\nwe find the longest increasing paths starting from each value in the matrix. By keeping track of the longest paths for rows and columns, we determine the maximum number of cells we can visit. The final result is the maximum path length among all rows and columns.\n\n# Algo\n1-: We have a grid of numbers, and we want to find the most cells we can visit by starting from any cell and moving only to cells with higher numbers.\n\n2-: We go through the grid and remember where each number is located, and also keep track of the unique numbers in reverse order.\n\n3 -: Starting from the highest number, we calculate the longest paths by moving only to cells with higher numbers. We keep track of the longest path for each row and column.\n\nAfter going through all the numbers, we update the longest paths for each row and column based on the calculated paths.\n\nFinally, we find the longest path among all the rows and columns, which represents the maximum number of cells we can visit.\nComplexity\nTime complexity:\nO(m * n * log(m * n))\n\nSpace complexity:\nO(m * n)\n# Code\n```\nclass Solution {\npublic:\n int maxIncreasingCells(vector>& matrix) {\n const int rows = matrix.size();\n const int cols = matrix[0].size();\n\n vector rowPaths(rows);\n vector colPaths(cols);\n unordered_map>> valuePositions;\n vector> temp(rows, vector(cols));\n set uniqueValues;\n\n // Populate valuePositions and uniqueValues\n for (int i = 0; i < rows; ++i) {\n for (int j = 0; j < cols; ++j) {\n int value = matrix[i][j];\n valuePositions[-value].push_back({i, j});\n uniqueValues.insert(-value);\n }\n }\n\n // Calculate longest paths\n for (int value : uniqueValues) {\n for (const auto& position : valuePositions[value]) {\n int row = position[0];\n int col = position[1];\n temp[row][col] = max(rowPaths[row], colPaths[col]) + 1;\n }\n\n for (const auto& position : valuePositions[value]) {\n int row = position[0];\n int col = position[1];\n rowPaths[row] = max(rowPaths[row], temp[row][col]);\n colPaths[col] = max(colPaths[col], temp[row][col]);\n }\n }\n\n // Return the maximum path length\n return max(*max_element(rowPaths.begin(), rowPaths.end()), *max_element(colPaths.begin(), colPaths.end()));\n }\n};\n```\n# Method 2-> Recursion ( Dfs )\nBut it passed only 557 cases and give tle at 558\nSuggest me how to reduce complexity of recursion\nMy logic\n1. Fisrt make array and mark -1 at each point \n2. make a call in same row and same column for given point \n3. Returm maximum of both calls \n```\n class Solution {\npublic:\n vector>vis;\n int m,n;\n int dfs(int x,int y,vector>&mat)\n {\n if(vis[x][y]!=-1)return vis[x][y];\n // for col\n int ans=1;\n for(int col=0;col>& mat)\n { \n m=mat.size(),n=mat[0].size();\n vis.resize(m+1,vector(n+1,-1));\n int ans=1;\n for(int i=0 ;i< m ;i++)\n for(int j=0 ;j Binary Search along with dfs\n But its also give tle at case 558\n```\nclass Solution {\npublic:\n vector>vis;\n vector>>scol,srow;\n int m,n;\n int bs(vector>&sorted,int target)\n {\n int low=0,high=sorted.size()-1,ans=-1;\n vectorgreater;\n while(high>=low)\n {\n int mid=(low+high)/2;\n if(sorted[mid].first>target)\n {\n ans=mid;\n high=mid-1;\n }\n else low=mid+1;\n }\n return ans ;\n }\n int dfs(int x,int y,vector>&mat)\n {\n \n int ans=1;\n int c=bs(scol[x],mat[x][y]);\n int r=bs(srow[y],mat[x][y]);\n if(vis[x][y]!=-1)return vis[x][y];\n //-1 means no element left in that row or column\n while(c!=-1 and c>& mat)\n { \n m=mat.size(),n=mat[0].size();\n scol.resize(m),srow.resize(n);\n // create sorted col\n for(int i=0 ;i(n+1,-1));\n int ans=1;\n for(int i=0 ;i< m ;i++)\n for(int j=0 ;j< n ;j++)\n {\n ans=max(ans,dfs(i,j,mat));\n }\n return ans;\n\n }\n};\n```\n# 4 Dfs using map and binary Search 100% accepted\n```\n\nclass Solution {\nprivate:\n int dfs(vector> &arr,int i,int j,map> row[],map> col[],vector> &dp){\n \n if(dp[i][j]!=-1)return dp[i][j];\n int ans=1;\n //move in row\n auto c=row[i].lower_bound(arr[i][j]+1);\n if(c!=row[i].end()){\n vector x=(*c).second;\n for(auto ele:x)\n ans=max(ans,1+dfs(arr,i,ele,row,col,dp));\n }\n //move in col\n auto r=col[j].lower_bound(arr[i][j]+1);\n if(r!=col[j].end()){\n vector x=(*r).second;\n for(auto ele:x)\n ans=max(ans,1+dfs(arr,ele,j,row,col,dp));\n }\n return dp[i][j]=ans;\n }\npublic:\n int maxIncreasingCells(vector>& arr) {\n \n int m=arr.size(),n=arr[0].size(),i,j;\n map> row[m];\n map> col[n];\n \n for(i=0;i> dp(m,vector(n,-1));\n int ans=0;\n \n for(i=0;i

Maximum Strictly Increasing Cells in a Matrix

Problem Description

Problem Description

Answer Panel