Rotate each ring of matrix anticlockwise by K elements
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.
Examples:
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.
Below is C++ implementation of above steps.
CPP
// C++ program to rotate individual rings by k in // spiral order traversal. #include<bits/stdc++.h> #define MAX 100 using namespace std; // Fills temp array into mat[][] using spiral order // traversal. void fillSpiral( int mat[][MAX], int m, int n, int temp[]) { int i, k = 0, l = 0; 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++; } } } void spiralRotate( int mat[][MAX], int M, int N, int k) { // Create a temporary array to store the result int temp[M*N]; 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 reversal // algorithm for rotation reverse(start, start+k); reverse(start+k, end); reverse(start, end); // Reset start for next ring start = end; } } // Fill temp array in original matrix. fillSpiral(mat, M, N, temp); } // Driver program to run the case int main() { // Your C++ Code int M = 4, N = 4, k = 3; int mat[][MAX]= {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; spiralRotate(mat, M, N, k); // print modified matrix for ( int i=0; i<M; i++) { for ( int j=0; j<N; j++) cout << mat[i][j] << " " ; cout << endl; } return 0; } |
Java
import java.util.*; public class Main { static final int MAX = 100 ; // Fills temp array into mat[][] using spiral order // traversal. static void FillSpiral( int [][] mat, int m, int n, int [] temp) { int k = 0 , l = 0 ; 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++; } } } static void SpiralRotate( int [][] mat, int M, int N, int k) { // Create a temporary array to store the result int [] temp = new int [M * N]; int m = M, n = N, s = 0 , l = 0 ; // Initialize end position of current ring int tIdx = 0 ; int start = 0 ; while (s < m && l < n) { 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--; } 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 reversal // algorithm for rotation reverseArray(temp, start, start + k - 1 ); reverseArray(temp, start + k, end - 1 ); reverseArray(temp, start, end - 1 ); start = end; } } // Fill temp array in original matrix. FillSpiral(mat, M, N, temp); } // Reverse Array static void reverseArray( int [] arr, int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } // Driver code public static void main(String[] args) { int M = 4 , N = 4 , k = 3 ; int [][] mat = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 9 , 10 , 11 , 12 }, { 13 , 14 , 15 , 16 } }; SpiralRotate(mat, M, N, k); for ( int i = 0 ; i < M; i++) { for ( int j = 0 ; j < N; j++) { System.out.print(mat[i][j] + " " ); } System.out.println(); } } } |
Python3
# Python program to rotate individual rings by k in # spiral order traversal. MAX = 100 # Fills temp array into mat[][] using spiral order # traversal. def fillSpiral(mat, m, n, temp): i, k, l = 0 , 0 , 0 tIdx = 0 # Index in temp array while k < m and l < n: # first row from the remaining rows for i in range (l, n): mat[k][i] = temp[tIdx] tIdx + = 1 k + = 1 # last column from the remaining columns for i in range (k, m): mat[i][n - 1 ] = temp[tIdx] tIdx + = 1 n - = 1 # last row from the remaining rows if k < m: for i in range (n - 1 , l - 1 , - 1 ): mat[m - 1 ][i] = temp[tIdx] tIdx + = 1 m - = 1 # first column from the remaining columns if l < n: for i in range (m - 1 , k - 1 , - 1 ): mat[i][l] = temp[tIdx] tIdx + = 1 l + = 1 # Rotates the individual rings in spiral order def spiralRotate(mat, M, N, k): # Create a temporary array to store the result temp = [ 0 ] * (M * N) m, n, s, l = M, N, 0 , 0 start = 0 # Start position of current ring tIdx = 0 # Index in temp while s < m and l < n: # Initialize end position of current ring end = start # copy the first row from the remaining rows for i in range (l, n): temp[tIdx] = mat[s][i] tIdx + = 1 end + = 1 s + = 1 # copy the last column from the remaining columns for i in range (s, m): temp[tIdx] = mat[i][n - 1 ] tIdx + = 1 end + = 1 n - = 1 # copy the last row from the remaining rows if s < m: for i in range (n - 1 , l - 1 , - 1 ): temp[tIdx] = mat[m - 1 ][i] tIdx + = 1 end + = 1 m - = 1 # copy the first column from the remaining columns if l < n: for i in range (m - 1 , s - 1 , - 1 ): temp[tIdx] = mat[i][l] tIdx + = 1 end + = 1 l + = 1 # if elements in current ring greater than k then rotate elements of current ring if end - start > k: # Rotate current ring using reversal algorithm for rotation temp[start:start + k], temp[start + k:end] = reversed (temp[start:start + k]), reversed (temp[start + k:end]) temp[start:end] = reversed (temp[start:end]) # Reset start for next ring start = end # Fill temp array in original matrix. fillSpiral(mat, M, N, temp) # Driver program to run the case if __name__ = = "__main__" : M = 4 N = 4 k = 3 mat = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ], [ 13 , 14 , 15 , 16 ]] spiralRotate(mat, M, N, k) # print modified matrix for i in range (M): for j in range (N): print (mat[i][j], end = " " ) print () # This code is contributed by Prince Kumar |
C#
// C# program to rotate individual rings by k in // spiral order traversal. using System; class Program { const int MAX = 100; // Fills temp array into mat[][] using spiral order // traversal. static void FillSpiral( int [,] mat, int m, int n, int [] temp) { int k = 0, l = 0; 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++; } } } static void SpiralRotate( int [,] mat, int M, int N, int k) { // Create a temporary array to store the result int [] temp = new int [M * N]; int m = M, n = N, s = 0, l = 0; // Initialize end position of current ring int tIdx = 0; int start = 0; while (s < m && l < n) { 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--; } 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 reversal // algorithm for rotation Array.Reverse(temp, start, k); Array.Reverse(temp, start + k, end - start - k); Array.Reverse(temp, start, end - start); start = end; } } // Fill temp array in original matrix. FillSpiral(mat, M, N, temp); } // Driver program to run the case static void Main( string [] args) { // Your C++ Code int M = 4, N = 4, k = 3; int [,] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; SpiralRotate(mat, M, N, k); for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) { Console.Write(mat[i, j] + " " ); } Console.WriteLine(); } } } |
Javascript
// JavaScript program to rotate individual rings by k in // spiral order traversal. const MAX = 100; // Fills temp array into mat[][] using spiral order traversal. function fillSpiral(mat, m, n, temp) { let i = 0, k = 0, l = 0; let tIdx = 0; // Index in temp array while (k < m && l < n) { // first row from the remaining rows for (i = l; i < n; i++) { mat[k][i] = temp[tIdx]; tIdx++; } k++; // last column from the remaining columns for (i = k; i < m; i++) { mat[i][n - 1] = temp[tIdx]; tIdx++; } n--; // last row from the remaining rows if (k < m) { for (i = n - 1; i >= l; i--) { mat[m - 1][i] = temp[tIdx]; tIdx++; } m--; } // first column from the remaining columns if (l < n) { for (i = m - 1; i >= k; i--) { mat[i][l] = temp[tIdx]; tIdx++; } l++; } } } // Rotates the individual rings in spiral order function spiralRotate(mat, M, N, k) { // Create a temporary array to store the result const temp = new Array(M * N).fill(0); let m = M, n = N, s = 0, l = 0; let start = 0; // Start position of current ring let tIdx = 0; // Index in temp while (s < m && l < n) { // Initialize end position of current ring let end = start; // copy the first row from the remaining rows for (let i = l; i < n; i++) { temp[tIdx] = mat[s][i]; tIdx++; end++; } s++; // copy the last column from the remaining columns for (let i = s; i < m; i++) { temp[tIdx] = mat[i][n - 1]; tIdx++; end++; } n--; // copy the last row from the remaining rows if (s < m) { for (let i = n - 1; i >= l; i--) { temp[tIdx] = mat[m - 1][i]; tIdx++; end++; } m--; } // copy the first column from the remaining columns if (l < n) { for (let i = m - 1; i >= s; i--) { temp[tIdx] = mat[i][l]; tIdx++; end++; } l++; } // if elements in current ring greater than k then rotate elements of current ring if (end - start > k) { // Rotate current ring using reversal algorithm for rotation temp.splice(start, k, ...temp.slice(start, start + k).reverse()); temp.splice(start + k, end - start - k, ...temp.slice(start + k, end).reverse()); temp.splice(start, end - start, ...temp.slice(start, end).reverse()); start = end; } } fillSpiral(mat, M, N, temp); } const M = 4; const N = 4; const k = 3; const mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16], ]; spiralRotate(mat, M, N, k); // print modified matrix for (let i = 0; i < M; i++) { for (let j = 0; j < N; j++) { process.stdout.write(mat[i][j] + " " ); } console.log(); } // This code is generated by chetan bargal |
Output
4 8 12 16 3 10 6 15 2 11 7 14 1 5 9 13
Time Complexity : O(M*N) as we are using nested loops to traverse the matrix.
Auxiliary space : O(M*N) as we are using extra space for matrix.