Introduction
In this blog, we will take up a coding problem involving spiral traversal of a matrix. Matrix problems are increasingly asked in programming contests and technical interviews. Therefore, it is a must for aspiring programmers to have a solid grounding in this concept. This blog aims to solve a difficult problem using multiple concepts like spiral traversal, array rotation, etc. We will also discuss the time and space complexity of our approach. So let’s get started.
Must Read, Array Implementation of Queue and Rabin Karp Algorithm
Problem Statement
Ninja has given you a matrix and a number K. It has asked you to rotate each ring of the matrix by K in clockwise direction and for those rings whose size is less than K, leave them unchanged. Print the final matrix after making these changes.
Note: Ring means a single spiral traversal of a matrix.
Sample Example 1
Input
K = 2
Output
Explanation
We have rotated each ring of the matrix by 2 positions in a clockwise direction.
Sample Example 2
Input
K = 4
Output
Explanation
Rotated the outermost ring by 4 positions in a clockwise direction. Notice that the second ring consisting of 11 10 and 3 is not rotated.
Approach
We will be following a straightforward approach. The straightforward approach is the most optimized approach as well. We will do a spiral traversal of the input matrix and store the elements of each ring in a vector after the traversal. Now, if the size of the vector is less than K, then break out of the process according to the provided question definition. The rings afterward will be smaller as well.
Now, if the size of the vector is larger than K, we will rotate the array by K positions in the clockwise direction and then store the elements in the matrix again by repeating the previous spiral traversal.
Algorithm
-
Define the input matrix and the value of K.
-
Do a spiral traversal of the input matrix. After the completion of each spiral traversal, do the following:
-
If the length of the ring is less than K, break out of the loop.
- If not, rotate the vector and store the elements in the matrix again by repeating the previous spiral traversal.
Implementation
#include<bits/stdc++.h>
using namespace std;
// Function to rotate the rings.
void rotateRings(vector<vector<int>>& mat, int k, int n, int m)
{
// Spiral rotation parameters.
int top=0, bottom=n-1,left=0,right=m-1;
// Rotate while the ring exists.
while(top<=bottom){
// To hold the ring elements.
vector<int> elems;
// Do the spiral traversal and store the ring elements.
for(int i=left;i<=right;i++){
elems.push_back(mat[top][i]);
}
for(int i=top+1;i<=bottom;i++){
elems.push_back(mat[i][right]);
}
for(int i=right-1;i>=left;i--){
elems.push_back(mat[bottom][i]);
}
for(int i=bottom-1;i>top;i--){
elems.push_back(mat[i][left]);
}
// Check if the ring size is less than or equal to k
// If true, break as the rings after will also be smaller than k.
if(elems.size()<=k){
break;
}
// Rotation starts.
// ind represents the index of the
// position that should be at the start of the ring.
int sz=elems.size();
int ind=sz-k;
// Store the rotated ring.
for(int i=left;i<=right;i++){
mat[top][i]=elems[ind];
ind++; ind%=sz;
}
for(int i=top+1;i<=bottom;i++){
mat[i][right]=elems[ind];
ind++; ind%=sz;
}
for(int i=right-1;i>=left;i--){
mat[bottom][i]=elems[ind];
ind++; ind%=sz;
}
for(int i=bottom-1;i>top;i--){
mat[i][left]=elems[ind];
ind++; ind%=sz;
}
// Update the rotation parameters.
top++; bottom--;
left++; right--;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
}
int main(){
// Define the input.
vector<vector<int>> mat = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
int k = 2;
// Run the algorithm.
rotateRings(mat, k, mat.size(), mat[0].size());
}
Output:
9 5 1 2
13 11 10 3
14 7 6 4
15 16 12 8
Time Complexity
The time complexity of the above approach is O(N * M), where N and M are the dimensions of the input matrix. It is because we are looping through the matrix once.
Space Complexity
The Space Complexity of the above approach is O(N + M), where N and M are the dimensions of the input matrix. It is because we are creating a vector to store the elements of the rings and the maximum possible size of a ring < 2 * (N + M).