Skip to main content

Rotate matrix elements in given size

The problem at hand involves rotating the elements of a matrix in a clockwise direction by a given number of positions (k). The goal is to rotate each "ring" of the matrix (a layer of elements) by k positions while maintaining the overall structure of the matrix.

Problem Statement

Given a matrix of dimensions m x n and a positive integer k, the task is to rotate each "ring" of the matrix clockwise by k positions and display the modified matrix.

Example

Consider the following matrix:

1   2   3   4   5
6   7   8   9  10
11  12  13  14  15
16  17  18  19  20
21  22  23  24  25

If we rotate each "ring" of the matrix clockwise by 5 positions, the modified matrix becomes:

22  21  16  11   6
23  14  19  18   1
24   9  13  17   2
25   8   7  12   3
20  15  10   5   4

Idea to Solve

Rotate matrix elements

To solve this problem, divide the matrix into concentric "rings" and rotate each ring separately. Iterate through the rings, and for each ring, perform the rotation operation k times. The rotation can be implemented by swapping elements in each of the four edges of the ring.

Pseudocode

Here's the pseudocode for the algorithm:

function rotateRing(matrix, row, col, index):
    i = col - 1
    data = matrix[row][col]
    temp = 0
    // Rotate bottom right to left
    while i >= index:
        temp = matrix[row][i]
        matrix[row][i] = data
        data = temp
        i--
    // Rotate bottom to top
    i = row - 1
    while i >= index:
        temp = matrix[i][index]
        matrix[i][index] = data
        data = temp
        i--
    // Rotate left to right
    i = index + 1
    while i <= col:
        temp = matrix[index][i]
        matrix[index][i] = data
        data = temp
        i++
    // Rotate top to bottom
    i = index + 1
    while i <= row:
        temp = matrix[i][col]
        matrix[i][col] = data
        data = temp
        i++

function rotateByK(matrix, k):
    if k <= 0:
        return
    row = matrix.rows
    col = matrix.cols
    size = min(row, col)
    i = 0
    while i < size / 2:
        row--
        col--
        rotateRing(matrix, row, col, i)
        i++
    rotateByK(matrix, k-1)

Algorithm Explanation

  1. Define a function rotateRing that rotates the elements of a ring in a clockwise direction. It takes the matrix, current row and column index, and the index of the current ring as input.
  2. Implement the rotation in four cases: A (bottom right to left), B (bottom to top), C (left to right), and D (top to bottom). Use a data variable to temporarily store values during swapping.
  3. Define a function rotateByK that rotates the entire matrix by k positions. It takes the matrix and the value of k as input.
  4. If k is less than or equal to 0, return from the function (base case).
  5. Get the dimensions of the matrix (row and col) and determine the size of the smallest ring (size). Initialize the loop control variable i to 0.
  6. Iterate through each ring while decreasing the row and column indices by 1 (indicating moving to an inner ring). Call the rotateRing function for each ring.
  7. Recursively call rotateByK with a reduced value of k (k-1).

Code Solution

Time Complexity

The time complexity of this algorithm depends on the number of rings and the number of rotations. In each ring, the algorithm swaps each element four times, resulting in O(4 * n) operations for a ring with n elements. Since the algorithm recursively rotates the matrix k times, the total time complexity is O(k * 4 * n), which simplifies to O(k * n).





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment