My simple solution using a map with both O(n) space and time complexity


  • 0
    S
    public class Solution {
        public int[] findDiagonalOrder(int[][] matrix) {
            if(matrix == null || matrix.length == 0) {
                return new int[0];
            }
            int[] result = new int[matrix.length*matrix[0].length];
            
            Map<Integer, List<Integer>> map = new LinkedHashMap<>();
            
            int row = 0;
            for(int i=0; i<matrix[0].length; i++) {
                map.put(row+i, new ArrayList<Integer>());
            }
            
            int col = matrix[0].length-1;
            for(int i=1; i<matrix.length; i++) {
                map.put(col+i, new ArrayList<Integer>());
            }
            
            for(int i=0; i<matrix.length; i++) {
                for(int j=0; j<matrix[0].length; j++) {
                    List<Integer> list = map.get(i+j);
                    list.add(0, matrix[i][j]);
                }
            }
            
            
            
            
            boolean up = true;
            int index = 0;
            for(List<Integer> value: map.values()) {
                if(up) {
                    for(int i=0; i<value.size(); i++) {
                        result[index] = value.get(i);
                        index++;
                    }
                    up = false;
                } else {
                    for(int i=value.size()-1; i>=0; i--) {
                        result[index] = value.get(i);
                        index++;
                    }
                    up = true;
                }
            }
            
            return result;
            
            
        }
    }

Log in to reply
 

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