Sharing my code , took 101 ms


  • 0
    S

    please suggest if any improvements can be made or any overhead can be decreased

    class Solution {
    public:
    
    
    int check(int i,int j,int rows,int cols){
    	if( i>=0 && j>=0 && i<rows && j<cols)
    		return 1;
    	else
    		return 0; 
    }
    void search(vector<vector<int> >& mark,vector<vector<int> >& matrix,int i,int j,int rows,int cols){
    	int arr[][2]={{-1,0},{1,0},{0,1},{0,-1}};
    	for(int k=0;k<4;k++){
    		
    		int x =arr[k][0];
    		int y = arr[k][1];
    		x += i;
    		y += j;
    		
    		if(check(x,y,rows,cols)){
    			if(matrix[i][j]<matrix[x][y]){
    				if(mark[x][y] == 0){
    					search(mark,matrix,x,y,rows,cols);
    				}
    					mark[i][j] = max(mark[x][y] + 1,mark[i][j]);
    			}
    		}
    	}
    	if(mark[i][j] == 0)
    		mark[i][j] = 1;
    }
    int longestIncreasingPath(vector<vector<int> >& matrix) {
    	int rows = matrix.size();
    	if(rows == 0) return 0;
    	int columns = matrix[0].size();
    	vector<vector<int> > mark(rows, vector<int>(columns,0));
        int maxPathSize = 0;
    	
    	for(int i=0;i<matrix.size();i++){
    		for(int j= 0;j<matrix[i].size();j++){
    			if(mark[i][j] == 1)
    				continue;
    			mark[i][j]=1;
    			search(mark,matrix,i,j,rows,columns);
    			maxPathSize = max(mark[i][j],maxPathSize);
    		}
    	}
    	return maxPathSize;
    }
    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.