Posted on 2019-08-27.

The “Matrix Layer Rotation” problem on HackerRank defines a type of “rotation” operation that can be performed on a matrix, and asks you to write a function that will display the result of applying that operation a given number of times on a given matrix. Since the matrix can contain up to 300 * 300 = 90,000 elements, and up to 10⁹ = 1 billion rotations can be requested, moving every single element through each rotation could take 90,000 * 10⁹ = 90 trillion operations. An ideal solution would skip all the intermediate steps and go directly from the original matrix to the final matrix; this post explains how to do that.

My solution is written in the lovely Kotlin language. I’ll just show how to implement the matrixRotation function; for the main function, see the template that HackerRank provides.

Contents:

• Approach overview
• Program structure
• Implementation details
• Full code

Approach overview

As shown in the problem’s diagram, rotation occurs within “layers” of the matrix. The first layer consists of all the elements on the outer edge of the matrix. The next layer consists of all the elements that would be on the outer edge if you removed the first layer. And so on.

This means there are two different ways - two different coordinate systems - you can use to specify any element. One way is to specify the row and column of the element. Here’s a 6x6 matrix with each element labeled using (row, column) notation:

The other is to specify the layer number and the counterclockwise index within that layer. Here’s the same 6x6 matrix with each element labeled using (layer, index) notation:

As long as you know the size of the matrix, you can efficiently convert back and forth between these two coordinate systems.

Within the (layer, index) coordinate system, rotation is relatively simple. Each value will still be in the same layer after rotation that it was in prior to rotation; only its index changes. The new index is simply the old index plus the number of rotations, except that you need to “wrap around” back to 0 if you exceed the highest index in the layer.

For example, in the 6x6 matrix, if you rotate by 4, the value at (layer=1, index=2) will now be at (layer=1, index=6). The value at (layer=1, index=10) will now be at (layer=1, index=2). The “wrapping around” can be accomplished easily using the modulo operation (I’ve explained previously how modulo arithmetic is like working on a number wheel).

You could just as easily ask “what should be at (layer=1, index=6) in the result matrix?” To find the answer you just have to subtract 4 from the index and look up (layer=1, index=2) in the original matrix.

This suggests a way to solve the problem:

1. For each row y:
   1. For each column x:
      1. Convert the (row=y, column=x) coordinate to a (layer, index) coordinate.
      2. Subtract the number of rotations from the index, wrapping around if necessary.
      3. Convert that back to a (row, column) coordinate. This tells you which value from the original matrix should be copied to (row=y, column=x) in the result matrix.

This is an O(M x N) solution, where M is the number of rows and N is the number of columns. This is the best time complexity achievable for this problem - anything better would imply that your algorithm isn’t even looking at some elements of the input matrix.

Program structure

We’ll want a data type to hold (row, column) coordinates:

data class CartesianCoord(val row: Int, val col: Int)

We’ll also want a data type that can hold the dimensions of a matrix or layer:

data class Dimensions(val height: Int, val width: Int)

We could define a data type to hold (layer, index) coordinates, but they aren’t very useful on their own. You need the dimensions of the matrix, and a bunch of derived information, to really make sense of them. It seems more useful to define a Layer class. The functions for converting from (row, column) coordinates to (layer, index) coordinates, and vice versa, will be methods on this class, so that they can share some calculations about the layer. We’ll use those methods to build another method that performs rotation on a (row, column) coordinate, returning a (row, column) coordinate.

data class Layer(val mdim: Dimensions, val distFromEdge: Int) {
    fun index(cc: CartesianCoord): Int { ... }
    fun cartesian(index: Int): CartesianCoord { ... }
    fun rotate(cc: CartesianCoord, r: Int): CartesianCoord { ... }
}

We’re going to want to call rotate for every (row, column) coordinate of the matrix, which means we need a function that can figure out what layer a coordinate resides in:

fun layerFor(mdim: Dimensions, cc: CartesianCoord): Layer { ... }

Finally, we need a function that uses all of the above to build a rotated copy of a given matrix. We also need a function to print the matrix.

fun rotateMatrix(rows: Array<Array<Int>>, r: Int): Array<Array<Int>> { ... }
fun printMatrix(rows: Array<Array<Int>>) { ... }

Those two methods are what we will use to implement the matrixRotation method requested by the problem statement:

fun matrixRotation(matrix: Array<Array<Int>>, r: Int) = printMatrix(rotateMatrix(matrix, r))

Implementation details

Jump to:

• printMatrix
• rotateMatrix
• layerFor
• Layer

printMatrix

This part is straightforward. The matrix is represented as an array of rows, and each row is represented by an array of column values. We need to print one line per row, with all of the column values for that row separated by spaces.

fun printMatrix(rows: Array<Array<Int>>) {
    for (row in rows) {
        println(row.joinToString(" "))
    }
}

rotateMatrix

This function builds a new matrix with the same dimensions as the original matrix. The code in the innermost block will execute once for each (row, column) coordinate in the new matrix, and should return the value that we want stored at that coordinate. As described above, we figure that out by rotating in reverse (using -r instead of r). We rely on the Layer.rotate method to convert to (layer, index) coordinates, do the rotation, and convert back to (row, column) coordinates.

fun rotateMatrix(rows: Array<Array<Int>>, r: Int): Array<Array<Int>> {
    val mdim = Dimensions(rows.size, rows[0].size)

    return Array(mdim.height) { row ->
        Array(mdim.width) { col ->
            val target = CartesianCoord(row, col)
            val source = layerFor(mdim, target).rotate(target, -r)
            rows[source.row][source.col]
        }
    }
}

layerFor

How do we determine which layer a given (row, column) coordinate resides within? Consider the following 6x6 matrix; the value in each cell is the layer number that cell is in.

Notice that the layer number is equal to the shortest perpendicular distance from the cell to any edge. For instance, at (row=2, col=0), the closest edge is the left edge of the matrix, since the cell is on that edge. It’s 0 cells away, so the cell is in layer 0. The cell at (row=2, col=1) is also closer to the left edge than any other edge, but it’s 1 cell away, so it’s in layer 1. The cell at (row=4, col=3) is closest to the bottom edge, which is 1 cell away, so it’s in layer 1. And so forth. We can use that reasoning to implement the layerFor method:

fun layerFor(mdim: Dimensions, cc: CartesianCoord) = Layer(
    mdim,
    minOf(cc.row, cc.col, minOf(mdim.height - cc.row - 1, mdim.width - cc.col - 1))
)

Layer

The gnarliest part of the program is the logic for converting between (row, column) and (layer, index) coordinates. First, let’s make some calculations about the geometry of the layer:

data class Layer(val mdim: Dimensions, val distFromEdge: Int) {
    val left = distFromEdge
    val top = distFromEdge
    val right = mdim.width - distFromEdge - 1
    val bottom = mdim.height - distFromEdge - 1
    val ldim = Dimensions(bottom - top + 1, right - left + 1)

    val length = ldim.width * 2 + ldim.height * 2 - 4 // the "- 4" is to avoid double-counting each corner
    val bottomLeftIndex = ldim.height - 1
    val bottomRightIndex = bottomLeftIndex + ldim.width - 1
    val topRightIndex = bottomRightIndex + ldim.height - 1

    ...
}

Here’s a diagram for layer 1 (so distFromEdge=1) of a 6x6 matrix showing what all those variables mean:

To find the index corresponding to a (row, column) coordinate, we just need to determine which of the four edges the coordinate lies on, and then determine how far it is past the corner.

For example, consider (row=4, col=3):

• It’s on the bottom edge, since row == bottom == 4.
• It’s 2 positions past the bottom left corner, since that corner is at col=1, the coordinate is at col=3, and 3-1=2.
• Since the bottom left corner’s index is 3, this coordinate’s index is 3+2=5.

Our code needs four cases, one for each edge:

fun index(cc: CartesianCoord) = when {
    cc.col == left -> cc.row - top
    cc.row == bottom -> bottomLeftIndex + cc.col - left
    cc.row == top -> topRightIndex + right - cc.col
    else -> bottomRightIndex + bottom - cc.row
}

To go the other direction, from an index to a (row, column) coordinate, we need to determine which two corners the index lies between.

For example, consider index=5:

• It’s greater than bottomLeftIndex but less than bottomRightIndex, so it lies on the bottom edge, so its row will be 4.
• It’s 2 greater than bottomLeftIndex, so its column will be 2 greater than the column of bottomLeftIndex; 1+2=3.

Once again we need four cases, one for each corner/edge:

fun cartesian(index: Int) = when {
    index <= bottomLeftIndex -> CartesianCoord(top + index, left)
    index <= bottomRightIndex -> CartesianCoord(bottom, left + index - bottomLeftIndex)
    index <= topRightIndex -> CartesianCoord(bottom - (index - bottomRightIndex), right)
    else -> CartesianCoord(top, right - (index - topRightIndex))
}

Now we can write a method that converts from a (row, column) coordinate to an index, finds the index at which the element would reside after rotation of the matrix, and converts that index back to a (row, column) coordinate. We use Math.floorMod to ensure that if we increment the index higher than length or less than 0, it wraps back around. (Using the % operator rather than Math.floorMod would not behave as desired when the result is less than 0.)

fun rotate(cc: CartesianCoord, r: Int) = cartesian(Math.floorMod(index(cc) + r, length))

Full code

data class CartesianCoord(val row: Int, val col: Int)
data class Dimensions(val height: Int, val width: Int)

data class Layer(val mdim: Dimensions, val distFromEdge: Int) {
    val left = distFromEdge
    val top = distFromEdge
    val right = mdim.width - distFromEdge - 1
    val bottom = mdim.height - distFromEdge - 1
    val ldim = Dimensions(bottom - top + 1, right - left + 1)

    val length = ldim.width * 2 + ldim.height * 2 - 4
    val bottomLeftIndex = ldim.height - 1
    val bottomRightIndex = bottomLeftIndex + ldim.width - 1
    val topRightIndex = bottomRightIndex + ldim.height - 1

    fun index(cc: CartesianCoord) = when {
        cc.col == left -> cc.row - top
        cc.row == bottom -> bottomLeftIndex + cc.col - left
        cc.row == top -> topRightIndex + right - cc.col
        else -> bottomRightIndex + bottom - cc.row
    }

    fun cartesian(index: Int) = when {
        index <= bottomLeftIndex -> CartesianCoord(top + index, left)
        index <= bottomRightIndex -> CartesianCoord(bottom, left + index - bottomLeftIndex)
        index <= topRightIndex -> CartesianCoord(bottom - (index - bottomRightIndex), right)
        else -> CartesianCoord(top, right - (index - topRightIndex))
    }

    fun rotate(cc: CartesianCoord, r: Int) = cartesian(Math.floorMod(index(cc) + r, length))
}

fun layerFor(mdim: Dimensions, cc: CartesianCoord) = Layer(
    mdim,
    minOf(cc.row, cc.col, minOf(mdim.height - cc.row - 1, mdim.width - cc.col - 1))
)

fun rotateMatrix(rows: Array<Array<Int>>, r: Int): Array<Array<Int>> {
    val mdim = Dimensions(rows.size, rows[0].size)

    return Array(mdim.height) { row ->
        Array(mdim.width) { col ->
            val target = CartesianCoord(row, col)
            val source = layerFor(mdim, target).rotate(target, -r)
            rows[source.row][source.col]
        }
    }
}

fun printMatrix(rows: Array<Array<Int>>) {
    for (row in rows) {
        println(row.joinToString(" "))
    }
}

fun matrixRotation(matrix: Array<Array<Int>>, r: Int) = printMatrix(rotateMatrix(matrix, r))