Matrix Rotation – HackerRank Solution

In this post, we will solve Matrix Rotation HackerRank Solution. This problem (Matrix Rotation) is a part of HackerRank Functional Programming series.

Task

You are given a 2D matrix, a, of dimension MxN and a positive integer R. You have to rotate the matrix R times and print the resultant matrix. Rotation should be in anti-clockwise direction.

Rotation of a 4×5 matrix is represented by the following figure. Note that in one rotation, you have to shift elements by one step only (refer sample tests for more clarity).

It is guaranteed that the minimum of M and N will be even.

Input

First line contains three space separated integers, M, N and R, where M is the number of rows, N is number of columns in matrix, and R is the number of times the matrix has to be rotated.
Then M lines follow, where each line contains N space separated positive integers. These M lines represent the matrix.

Output

Print the rotated matrix.

Constraints

• 2 <= M, N <= 300
• 1 <= R <= 10⁹
• min(M, N) % 2 == 0
• 1 <= a_ij <= 10⁸, where i ∈ [1..M] & j ∈ [1..N]

Sample Input #00

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #00

2 3 4 8
1 7 11 12
5 6 10 16
9 13 14 15

Sample Input #01

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #01

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

Sample Input #02

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

Sample Output #02

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

Sample Input #03

2 2 3
1 1
1 1

Sample Output #03

1 1
1 1

Explanation

Sample Case #00: Here is an illustration of what happens when the matrix is rotated once.

 1  2  3  4      2  3  4  8
 5  6  7  8      1  7 11 12
 9 10 11 12  ->  5  6 10 16
13 14 15 16      9 13 14 15

Sample Case #01: Here is what happens when to the matrix after two rotations.

 1  2  3  4      2  3  4  8      3  4  8 12
 5  6  7  8      1  7 11 12      2 11 10 16
 9 10 11 12  ->  5  6 10 16  ->  1  7  6 15
13 14 15 16      9 13 14 15      5  9 13 14

Sample Case #02: Following are the intermediate states.

1  2  3  4      2  3  4 10    3  4 10 16    4 10 16 22
7  8  9 10      1  9 15 16    2 15 21 22    3 21 20 28
13 14 15 16 ->  7  8 21 22 -> 1  9 20 28 -> 2 15 14 27 ->
19 20 21 22    13 14 20 28    7  8 14 27    1  9  8 26
25 26 27 28    19 25 26 27    13 19 25 26   7 13 19 25



10 16 22 28    16 22 28 27    22 28 27 26    28 27 26 25
 4 20 14 27    10 14  8 26    16  8  9 25    22  9 15 19
 3 21  8 26 ->  4 20  9 25 -> 10 14 15 19 -> 16  8 21 13
 2 15  9 25     3 21 15 19     4 20 21 13    10 14 20  7
 1  7 13 19     2  1  7 13     3  2  1  7     4  3  2  1

Sample Case #03: As all elements are same, any rotation will reflect the same matrix.

Solution – Matrix Rotation – HackerRank Solution

Scala

import java.util.Scanner

object Solution {

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val M = sc.nextInt
    val N = sc.nextInt
    val r = sc.nextInt
    val matrix = (0 until M).map(_ => (0 until N).map(_ => sc.nextInt))

    sc.close()

    println((0 until M).map(y => {
      (0 until N).map(x => {
        def normalize(v: Int, size: Int) = if (v < size / 2) v else size - 1 - v

        val normX = normalize(x, N)
        val normY = normalize(y, M)

        val LoopIndex = math.min(normX, normY)

        def sideSize(size: Int) = size - 2 * LoopIndex

        val loopN = sideSize(N)
        val loopM = sideSize(M)
        val loopLength = 2 * (loopN - 1 + loopM - 1)

        val offset = r % loopLength

        def singleShift(v: Int, lower: Int, upper: Int, dir: Int, offset: Int): (Int, Int) = {
          val nextV = v + offset * dir
          if (nextV < upper) {
            if (nextV >= lower) (nextV, 0)
            else (lower, offset - (v - lower))
          } else (upper - 1, offset - (upper - 1 - v))
        }

        @scala.annotation.tailrec
        def shift(x: Int, y: Int, offset: Int): (Int, Int) = {
          val (nextX, nextY, nextOffset) = (x, y) match {
            case _ if y == LoopIndex && x < N - LoopIndex - 1 =>
              val (nextX, nextOffset) = singleShift(x, LoopIndex, N - LoopIndex, 1, offset)
              (nextX, y, nextOffset)
            case _ if x == N - LoopIndex - 1 && y < M - LoopIndex - 1 =>
              val (nextY, nextOffset) = singleShift(y, LoopIndex, M - LoopIndex, 1, offset)
              (x, nextY, nextOffset)
            case _ if y == M - LoopIndex - 1 && x > LoopIndex =>
              val (nextX, nextOffset) = singleShift(x, LoopIndex, N - LoopIndex, -1, offset)
              (nextX, y, nextOffset)
            case _ if x == LoopIndex && y > LoopIndex =>
              val (nextY, nextOffset) = singleShift(y, LoopIndex, M - LoopIndex, -1, offset)
              (x, nextY, nextOffset)
          }

          if (nextOffset == 0) (nextX, nextY) else shift(nextX, nextY, nextOffset)
        }

        val (srcX, srcY) = shift(x, y, offset)
        matrix(srcY)(srcX)
      }).mkString(" ")
    }).mkString("\n"))
  }
}

Note: This problem (Matrix Rotation) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.