Finding time complexity and how to improve


  • 0
    S
    public class Solution {
        public int longestLine(int[][] M) {
            int max=0;
            for(int i=0;i<M.length;i++){
                for(int j=0;j<M[i].length;j++){
                    int straight = Math.max(checkH(M,i,j),checkV(M,i,j));
                    int diagonal = Math.max(checkD(M,i,j),checkAD(M,i,j));
                    int longestLine = Math.max(straight,diagonal);
                    max= Math.max(max,longestLine);
                }
            }
            return max;
        }
        
        public int checkH(int[][] M,int i, int j ){
            int count=0;
            if(j-1 >= 0 && M[i][j-1]==1){
                return 0;
            }
            while(i < M.length && j<M[i].length && M[i][j]==1){
                j++;
                count++;
            }
            return count;
        }
        
        public int checkV(int[][] M,int i, int j ){
            int count=0;
            if(i-1 >= 0 && M[i-1][j]==1){
                return 0;
            }
            while(i < M.length && j<M[i].length && M[i][j]==1){
                i++;
                count++;
            }
            return count;
        }
        
        public int checkD(int[][] M,int i, int j ){
            int count=0;
            if(i-1 >= 0 && j-1 >= 0 && M[i-1][j-1]==1){
                return 0;
            }
            while(i < M.length && j<M[i].length && M[i][j]==1){
                j++;
                i++;
                count++;
            }
            return count;
        }
        
        public int checkAD(int[][] M,int i, int j ){
            int count=0;
            if(i-1 >= 0 && j+1 <M[i].length && M[i-1][j+1]==1){
                return 0;
            }
            while(i < M.length && j>=0 && M[i][j]==1){
                j--;
                i++;
                count++;
            }
            return count;
        }
    
    }
    

    I am not using any kind of DP. I am only checking the previous element before start checking longest sequence.
    Is the time Complexity O(mn) ?
    How can I improve the code in terms of time complexity. ?


Log in to reply
 

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