Created
March 8, 2018 06:51
-
-
Save jianminchen/3851b49be78a9d2f206099225725ed18 to your computer and use it in GitHub Desktop.
Spiral matrix print - March 7 2018 - I am the interviewer and the peer solved the problem. The code should be improved.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Spiral Matrix print - mock interview, it took the peer over 45 minutes to come out the correct solution. | |
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: | |
[ | |
[ 1, 2, 3 ], | |
[ 4, 5, 6 ], | |
[ 7, 8, 9 ] | |
] | |
You should return [1,2,3,6,9,8,7,4,5]. | |
*/ | |
class Solution { | |
public int[] spiralOrder(int[][] matrix) { | |
int rows, cols; | |
if((rows = matrix.length) == 0 || (cols = matrix[0].length) == 0) { | |
return new int[0]; | |
} | |
boolean[][] flags = new boolean[rows][cols]; | |
int[] result = new int[rows * cols]; | |
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // right, down, left, up | |
int index = 0; | |
int r = 0; // current row | |
int c = 0; // current col | |
while(index < result.length) { | |
for(int i = 0; i < directions.length; i++) { // no break statement inside ! | |
int[] delta = directions[i]; | |
while(r >= 0 && r < rows && c >= 0 && c < cols && !flags[r][c]) { | |
result[index++] = matrix[r][c]; | |
flags[r][c] = true; | |
int nr = r + delta[0]; | |
int nc = c + delta[1]; | |
if(nr >= 0 && nr < rows && nc >= 0 && nc < cols && !flags[nr][nc]) { | |
r = nr; | |
c = nc; | |
} | |
} | |
int[] nextDir = directions[(i+1) % directions.length]; | |
r += nextDir[0]; | |
c += nextDir[1]; | |
} | |
} | |
return result; | |
} | |
public void printArray(int[] arr) { | |
for(int i : arr) { | |
System.out.print(" " + i); | |
} | |
System.out.println(); | |
} | |
public static void main(String[] args) { | |
Solution inst = new Solution(); | |
int[][] matrix = {{1, 2, 3, 10}, {4, 5, 6, 11}, {7, 8, 9, 12}}; | |
int[] res = inst.spiralOrder(matrix); | |
inst.printArray(res); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment