Skip to content

Instantly share code, notes, and snippets.

@vromero
Last active November 28, 2016 08:15
Show Gist options
  • Save vromero/e363d99bcf57d4725417dc7434f794e4 to your computer and use it in GitHub Desktop.
Save vromero/e363d99bcf57d4725417dc7434f794e4 to your computer and use it in GitHub Desktop.
Traverse matrix in spiral form. My personal approach.
package com.company;
public class Main {
/**
* This algorithm will divide the matrix into layers and portions. Layers are taken from the outside to the inside.
* i.e:
* <pre>
* 1 1 1 1 1
* 1 2 2 2 1
* 1 2 2 2 1
* 1 1 1 1 1
* </pre>
*
* Then the portions will be divided as follows:
* <pre>
* 1 1 1 1 2
* 4 1 1 2 2
* 4 4 3 3 2
* 4 3 3 3 3
* </pre>
*
* Each of the portions will have a different movement. The first to portions will have the exact inverse movement
* than the last two portions.
*/
void rotate(int[][] matrix) {
// Divide into layers, starting from the outside to the inside
for (int l = 0; l < Math.max(matrix.length, matrix[0].length) / 2; l++) {
// Divide each of the layers into portions
// A portion contains a series of cells that will require the same movement
int horizontalPortionWidth = matrix[0].length - 1 - (l * 2);
int verticalPortionHeight = matrix.length - 1 - (l * 2);
// The last cell count to visit, in base 1
int lastCell = horizontalPortionWidth * 2 + verticalPortionHeight * 2;
// The initial position of the layer
int positionX = l, positionY = l;
// Now visit each of the cells of the layer in spiral order
for (int c = 0; c < lastCell; c++) {
System.out.println(matrix[positionY][positionX]);
// Calculate the current portion
int currentPortion = ((c % (horizontalPortionWidth + verticalPortionHeight))
/ horizontalPortionWidth) + (2 * (c / (horizontalPortionWidth + verticalPortionHeight)));
// The last two portions, have the same movement than the first two but inverted 1 -> -1, -1 -> 1
int inverter = currentPortion > 1 ? -1 : 1;
// Calculate the movement given the current portion
int absoluteYDelta = (currentPortion % 2) * inverter;
int absoluteXDelta = (1 - currentPortion % 2) * inverter;
positionY += absoluteYDelta;
positionX += absoluteXDelta;
}
}
}
public static void main(String[] args) {
Main rotateMatrix = new Main();
int[][] matrix = {
{1, 2, 3, 4},
{10, 11, 12, 5},
{ 9, 8, 7, 6}};
rotateMatrix.rotate(matrix);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment