Java - simple solution O(n) - with explanation


  • 0
    G

    Place 4 boundaries in matrix for row (i) and col (j), where il = row lower bound, ih = row upper bound, jl = col lower bound, jh = col upper bound, start i,j at 0,0. Rotate array by traversing each direction starting from east - south - west - north, and back to east. While still available space between boundaries, keep adding and switching direction in loop. Following algorithm in java:

    public class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            int dir = 0; // east
            List<Integer> r = new ArrayList<>();
            if (matrix == null || matrix.length == 0) 
                  return r;
            
            int i = 0;
            int j = 0;
            int il = 0;
            int ih = matrix.length;
            int jl = 0;
            int jh = matrix[0].length;
    
            while(il < ih && jl < jh) {
                // east
                if (dir == 0) {
                    int k = j;
                    while(k < jh) {
                        r.add(matrix[i][k]);
                        k++;
                    }
                    j = k-1;
                    il++;
                    i++;
                } 
                // south
                else if (dir == 1) {
                    int k = i;
                    while(k < ih) {
                        r.add(matrix[k][j]);
                        k++;
                    }
                    i = k - 1;
                    jh--;
                    j--;
                }    
                // west
                else if (dir == 2) {
                    int k = j;
                    while(k >= jl) {
                        r.add(matrix[i][k]);
                        k--;
                    }
                    j = k + 1;
                    ih--;
                    i--;
                }    
                // north
                else if (dir == 3) {
                    int k = i;
                    while(k >= il) {
                        r.add(matrix[k][j]);
                        k--;
                    }
                    i = k + 1;
                    jl++;
                    j++;
                }    
            
                dir++;
                dir = dir % 4;
            }
            return r;
        }
    }
    

Log in to reply
 

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