Tutorialspoint.dev

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.

// 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
// 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);
}
  
// 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;
}

Output:

4 8  12 16
3 10  6 15
2 11  7 14
1  5  9 13

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter