# Quirky In-Place Single-Swap Solution

• The idea is that we can push items around the perimeter of the matrix until they're in place, then descend into the next layer in the matrix and repeat.

Here's a derpy drawing I made to convey that idea.

This approach gets 3ms on the LeetCode tests.

The legibility of the implementation, I think, can be much improved.

``````public class Solution {
// The current n x n matrix
private int n;

/**
* Returns the [i] and [j] indices for the original matrix, given the
* rotational index i, and the depth d from the outside.
*
* @param i, the ith clockwise index of the perimeter of the current matrix
* @param d, the depth into the given matrix
* @return
*/
public int[] cycleIndex(int i, int d) {
i %= 4 * (n - 1);

int[] ij = new int[2];

// top
if (i < n) {
ij[0] = d;
ij[1] = i + d;
}

// right
else if (i < 2 * n - 1) {
ij[0] = 1 + i - n + d;
ij[1] = n - 1 + d;
}

// bottom
else if (i < 3 * n - 2) {
ij[0] = n - 1 + d;
ij[1] = n - 1 - (i - (2 * n - 2)) + d;
}

// left
else {
ij[0] = n - 1 - (i - (3 * n - 3)) + d;
ij[1] = d;
}
return ij;
}

public void rotate(int[][] matrix) {
n = matrix.length;

// Stores i, j indices
int[] tmp;

// Our queue structure
int back, front;

// Keep track of depth into matrix, from perimeter
for (int d = 0; n > 1; d++) {

// Will have (n-1) four-cycles
for (int j = 0; j < n - 1; j++) {

// Initialize our two-element queue
tmp = cycleIndex(j + 3 * (n - 1), d);
front = matrix[tmp[0]][tmp[1]];

// Complete a four-cycle
for (int i = j; i < 4 * (n - 1); i += (n - 1)) {
tmp = cycleIndex(i, d);
back = matrix[tmp[0]][tmp[1]];
matrix[tmp[0]][tmp[1]] = front;
front = back;
}
}
n -= 2;
}
}
}
``````

Given the following matrix:

``````{{1,2,3,2,1},
{2,3,4,3,2},
{3,4,5,4,3},
{4,5,6,5,4},
{5,6,7,6,5}}
``````

below are the completed four-cycles of this algorithm.

``````j = 0
{{5,2,3,2,1},
{2,3,4,3,2},
{3,4,5,4,3},
{4,5,6,5,4},
{5,6,7,6,1}}

j = 1
{{5,4,3,2,1},
{2,3,4,3,2},
{3,4,5,4,3},
{6,5,6,5,4},
{5,6,7,2,1}}

j = 2
{{5,4,3,2,1},
{2,3,4,3,2},
{7,4,5,4,3},
{6,5,6,5,4},
{5,6,3,2,1}}

j = 3
{{5,4,3,2,1},
{6,3,4,3,2},
{7,4,5,4,3},
{6,5,6,5,2},
{5,4,3,2,1}}

d = 1; j = 0
{{5,4,3,2,1},
{6,5,4,3,2},
{7,4,5,4,3},
{6,5,6,3,2},
{5,4,3,2,1}}

j = 1
{{5,4,3,2,1},
{6,5,4,3,2},
{7,6,5,4,3},
{6,5,4,3,2},
{5,4,3,2,1}}
``````

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