Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example 1
1.3.
Sample Example 2
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
Are linked lists FIFO or LIFO?
3.2.
What's the difference between LinkedList and ArrayList?
3.3.
What is the advantage of linked lists?
3.4.
Are linked lists sequential access structures?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Rotate Each Ring of Matrix Clockwise by K Elements

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

  1. Define the input matrix and the value of K.

     
  2. Do a spiral traversal of the input matrix. After the completion of each spiral traversal, do the following:

     
  3. If the length of the ring is less than K, break out of the loop.

     
  4. 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());
}
You can also try this code with Online C++ Compiler
Run Code

 

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).

Frequently Asked Questions

Are linked lists FIFO or LIFO?

A singly-linked list may be LIFO (last-in-first-out) or FIFO (first-in-first-out). If the list is using the LIFO method, the nodes will be added to and deleted from the same end. If it's using FIFO, nodes will be added to one end and deleted from the opposite end. Additionally, the linked list may be sorted.

What's the difference between LinkedList and ArrayList?

ArrayList internally uses a dynamic array to store its elements. LinkedList uses Doubly Linked List to store its elements. ArrayList is slow as array manipulation is slower. LinkedList is faster being node based as not much bit shifting is required.

What is the advantage of linked lists?

A linked list is a dynamic arrangement so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.

Are linked lists sequential access structures?

Sequential Access: Because a linked list is not contiguous, it does not support random access. In order to access a particular node within the linked list, the entire linked list must be traversed until the node is found.

Conclusion

In this blog, we saw in detail the coding problem which involved rotation of the rings of the given matrix. We implemented the approach in C++ and discussed the time and space complexity of the same.

You can find more blogs on Linked Lists and Rotations. Coding Ninjas has especially curated these blogs for readers like you - Most Asked Questions on LLLearn LLRotate Array, etc.

Moreover, if you find this article interesting, consider having a look at our articles from other domains. Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass