View post on GitHub ⇤ Back

Rotate a Square Matrix

Posted on 21 August 2017

(Referring to this leetcode problem.)

Pictorally, my approach consists of:

Given a NxN (N=6 here) matrix, number its four corners:

1 . . . . 2
. . . . . .
. . . . . .
. . . . . .
. . . . . .
4 . . . . 3

Rotate elements at positions 1, 2, 3, 4 clockwise:

4 . . . . 1
. . . . . .
. . . . . .
. . . . . .
. . . . . .
3 . . . . 2

Next, number their clockwise-immediate elements:

# 1 . . . #
. . . . . 2
. . . . . .
. . . . . .
4 . . . . .
# . . . 3 #

(Already dealt with elements are marked with #.)

Repeat the previous steps N-1 times (in total):

# # 1 . . #        # # # 1 . #
. . . . . #        . . . . . #
. . . . . 2  --->  4 . . . . #
4 . . . . .  --->  # . . . . 2
# . . . . .        # . . . . .
# . . 3 # #        # . 3 # # #
                //
              //
             LL
# # # # 1 #        # # # # # #
4 . . . . #        # . . . . #
# . . . . #  --->  # . . . . #
# . . . . #  --->  # . . . . #
# . . . . 2        # . . . . #
# 3 # # # #        # # # # # #

Notice how we moved through the ‘outer layer’ of the matrix in a ‘spiral’ shape, and its elements were rotated thusly.

By applying the same procedure to the inner layers, we arrive at a fully rotated matrix.

The code follows:

struct Pos { int i, j; };

void rotate(vector<vector<int>>& m) {
  // for every k-th layer:
  for (int k = 0; k < m.size() / 2; ++k) {
    // it has n*n size:
    int n = m.size() - k * 2;
    // apply our 'spiral' rotating procedure n-1 times:
    for (int s = 0; s < n - 1; ++s) {
      rotateLayer(m, k, n, s);
    }
  }
}

void rotateLayer(vector<vector<int>> &m, int layer, int size, int step) {
  int k = layer;
  int n = size;
  int s = step;

  // top-left corner,  moving right   (j += s)
  Pos p1 { k,             k + s };
  // top-right corner, moving down    (i += s)
  Pos p2 { k + s,         k + n - 1 };
  // bottom-right corner, moving left (j -= s)
  Pos p3 { k + n - 1,     k + n - 1 - s };
  // bottom-left corner,  moving up   (i -= s)
  Pos p4 { k + n - 1 - s, k };

  // swap clockwise
  tie(at(m, p1), at(m, p2), at(m, p3), at(m, p4))
    = make_tuple(at(m, p4), at(m, p1), at(m, p2), at(m, p3));
}

int& at(vector<vector<int>>& m, Pos p) {
  return m[p.i][p.j];
}

Note that this algorithm is not exactly cache-friendly (:

Related Posts