## Monday, November 21, 2016

### Rotate each ring of matrix anticlockwise by K elements - GeeksforGeeks

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 columns`
`void` `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);`
`}`