Rotate each ring of matrix anticlockwise by K elements - GeeksforGeeks
Given a matrix of order M*N and a value K, the task is to rotate each ring of the matrix anticlockwise by K elements. If in any ring elements are less than and equal K then don't rotate it.
Read full article from Rotate each ring of matrix anticlockwise by K elements - GeeksforGeeks
Given a matrix of order M*N and a value K, the task is to rotate each ring of the matrix anticlockwise by K elements. If in any ring elements are less than and equal K then don't rotate it.
Input : k = 3
mat[4][4] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output: 4 8 12 16
3 10 6 15
2 11 7 14
1 5 9 13
Input : k = 2
mat[3][4] = {{1, 2, 3, 4},
{10, 11, 12, 5},
{9, 8, 7, 6}}
Output: 3 4 5 6
2 11 12 7
1 10 9 8
The idea is to traverse matrix in spiral form. Here is the algorithm to solve this problem :
- Make an auxiliary array temp[] of size M*N.
- Start traversing matrix in spiral form and store elements of current ring in temp[] array. While storing the elements in temp, keep track of starting and ending positions of current ring.
- For every ring that is being stored in temp[], rotate that subarray temp[]
- Repeat this process for each ring of matrix.
- In last traverse matrix again spirally and copy elements of temp[] array to matrix.
// Fills temp array into mat[][] using spiral order// traveral.void fillSpiral(int mat[][MAX], int m, int n, int temp[]){ int i, k = 0, l = 0; /* k - starting row index m - ending row index l - starting column index n - ending column index */ int tIdx = 0; // Index in temp array while (k < m && l < n) { /* first row from the remaining rows */ for (int i = l; i < n; ++i) mat[k][i] = temp[tIdx++]; k++; /* last column from the remaining columns */ for (int i = k; i < m; ++i) mat[i][n-1] = temp[tIdx++]; n--; /* last row from the remaining rows */ if (k < m) { for (int i = n-1; i >= l; --i) mat[m-1][i] = temp[tIdx++]; m--; } /* first column from the remaining columns */ if (l < n) { for (int i = m-1; i >= k; --i) mat[i][l] = temp[tIdx++]; l++; } }}// Function to spirally traverse matrix and// rotate each ring of matrix by K elements// mat[][] --> matrix of elements// M --> number of rows// N --> number of columnsvoid spiralRotate(int mat[][MAX], int M, int N, int k){ // Create a temporary array to store the result int temp[M*N]; /* s - starting row index m - ending row index l - starting column index n - ending column index; */ int m = M, n = N, s = 0, l = 0; int *start = temp; // Start position of current ring int tIdx = 0; // Index in temp while (s < m && l < n) { // Initialize end position of current ring int *end = start; // copy the first row from the remaining rows for (int i = l; i < n; ++i) { temp[tIdx++] = mat[s][i]; end++; } s++; // copy the last column from the remaining columns for (int i = s; i < m; ++i) { temp[tIdx++] = mat[i][n-1]; end++; } n--; // copy the last row from the remaining rows if (s < m) { for (int i = n-1; i >= l; --i) { temp[tIdx++] = mat[m-1][i]; end++; } m--; } /* copy the first column from the remaining columns */ if (l < n) { for (int i = m-1; i >= s; --i) { temp[tIdx++] = mat[i][l]; end++; } l++; } // if elements in current ring greater than // k then rotate elements of current ring if (end-start > k) { // Rotate current ring using revarsal // algorithm for rotation reverse(start, start+k); reverse(start+k, end); reverse(start, end); // Reset start for next ring start = end; } else // There are less than k elements in ring break; } // Fill tenp array in original matrix. fillSpiral(mat, M, N, temp);}