My Java Solution with O(N) space.


  • 0
    Y

    Using O(N) memory to store temporary results and hence editing input, not creating a new matrix.

    class Solution {
        int[][] list = new int[][]{{0,0},{0,1},{0,-1},{1,0},{1,1},{1,-1},{-1,0},{-1,1},{-1,-1}};
        public int smoothenIt(int[][] M, int i, int j){
            if(M==null) return 0;
            int nR = M.length;
            int nC = M[0].length;
            int sum = 0;
            int count = 0;
            for(int[] tmp: list){
                if(i+tmp[0]<nR && i+tmp[0]>=0 && j+tmp[1]>=0 && j+tmp[1]<nC){
                   sum+= M[i+tmp[0]][j+tmp[1]];
                    count++;
                }
            }
            if (count == 0) return 0;
            return (sum/count);
        }
        public int[][] imageSmoother(int[][] M) {
                // rc ij 
            if(M == null) return null;
            int nR = M.length;
            int nC = M[0].length;
            //int[] temp = M[0];
            int[][] temp = new int[2][];
            int[] Mnew= new int[nC];
            int i=0;
            for(i=0; i<nR ;i++){
                for(int j=0;j<nC;j++){
                    Mnew[j] = smoothenIt(M,i,j);
                }
               if(temp[0]==null){
                   temp[0]=Arrays.copyOf(Mnew,Mnew.length);
               } else 
                   if(i-2>=0){
                       M[i-2] = Arrays.copyOf(temp[0],temp[0].length);
                       temp[0]= Arrays.copyOf(temp[1],temp[1].length);
                   }  
                   
                   temp[1]=Arrays.copyOf(Mnew,Mnew.length);
            }    
        
            if( i-2 >= 0){
                M[i-2]=temp[0];
            } else if(i-1>=0){
                M[i-1]=temp[0];
            }
            if(i-1>=0 && temp[1]!=null){
                M[i-1]=temp[1];
            }
            
            return M;
                 
        }
    }
    

Log in to reply
 

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