O(m+n) solution java easy understand


  • 0
    G
    class pair{
        int a1;
        int a2;
        pair(int a1, int a2){
            this.a1 = a1;
            this.a2 = a2;
        }
    }
    
    public class Solution {
        int h;
        int w;
        
        public int[] findDiagonalOrder(int[][] matrix) {
            h = matrix.length;
            if(h==0){
                return new int[0];
            }
            
            w = matrix[0].length;
            int newlen = h*w;
            int [] res = new int[newlen];
            int sumlimit = h+w-2;
            boolean flag = true;
            //int index=0;
            
            List<pair> as = new ArrayList<>();
            
            for(int i=0;i<=sumlimit;i++){
                List<pair> temp = get(i);
                if(flag){
                    Collections.reverse(temp);
                    as.addAll(temp);
                    flag = false;
                }
                else{
                    as.addAll(temp);
                    flag = true;
                }
            }
           
            for(int i=0;i<as.size();i++){
                res[i] = matrix[as.get(i).a1][as.get(i).a2];
            }
    
            return res;
        }
        
        public List<pair> get(int n){
            List<pair> as = new ArrayList<>();
            for(int i =0;i<=n;i++){
                if(i<h && n-i<w){
                    as.add(new pair(i,n-i));
                }
            }
            return as;
        }
    }

Log in to reply
 

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