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

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
- 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. - 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. - Define a function
rotateByK
that rotates the entire matrix by k positions. It takes the matrix and the value of k as input. - If k is less than or equal to 0, return from the function (base case).
- 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. - 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. - Recursively call
rotateByK
with a reduced value of k (k-1).
Code Solution
-
1) Rotate each ring of matrix by k elements in java
2) Rotate each ring of matrix by k elements in c++
3) Rotate each ring of matrix by k elements in c
4) Rotate each ring of matrix by k elements in c#
5) Rotate each ring of matrix by k elements in php
6) Rotate each ring of matrix by k elements in node js
7) Rotate each ring of matrix by k elements in typescript
8) Rotate each ring of matrix by k elements in python
9) Rotate each ring of matrix by k elements in ruby
10) Rotate each ring of matrix by k elements in scala
11) Rotate each ring of matrix by k elements in swift
12) Rotate each ring of matrix by k elements in kotlin
13) Rotate each ring of matrix by k elements in golang
14) Rotate each ring of matrix by k elements in vb.net
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).
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