Cyclically Rotating a Grid Leetcode Solution

Cyclically Rotating a Grid

You are given an m x n integer matrix grid​​​, where m and n are both even integers, and an integer k.

The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:

Cyclically Rotating a Grid Leetcode Solution

A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the counter-clockwise direction. An example rotation is shown below:

Cyclically Rotating a Grid Leetcode Solution

Return the matrix after applying k cyclic rotations to it.

Example 1:

Cyclically Rotating a Grid Leetcode Solution
Input: grid = [[40,10],[30,20]], k = 1
Output: [[10,20],[40,30]]
Explanation: The figures above represent the grid at every state.

Example 2:Cyclically Rotating a Grid Leetcode SolutionCyclically Rotating a Grid Leetcode SolutionCyclically Rotating a Grid Leetcode Solution

Input: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
Explanation: The figures above represent the grid at every state.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 50
  • Both m and n are even integers.
  • 1 <= grid[i][j] <=5000
  • 1 <= k <= 109

Approach:

  1. Convert a layer into a strip.
  2. Rotate the strip by k % length of strip.
  3. Set the rotated strip back to the grid.

Program:

class Solution {
public:

    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        
        int lefT = 0, rigT = n - 1;
        int h = 0;
        int lefB = m-1;
        while( (lefT < rigT) && (lefT<lefB) )
        {
            vector<int> temp;
			// Step 1: Converting a layer into strip
            for(int i=lefT; i<= rigT; i++)     //  top side ( left to right)
                temp.push_back(grid[h][i]);
            for(int i=lefT+1; i<=lefB;i++)    // right side ( top to bottom)
                temp.push_back(grid[i][rigT]);
            for(int i=rigT-1;i>=lefT;i--)       //  bottom side  ( right to left )
                temp.push_back(grid[lefB][i]);
            for(int i=lefB-1;i>lefT;i--)         // left side (bottom to top)
                temp.push_back(grid[i][lefT]);
            
			// Step2 : Rotating the strip
            int sz = temp.size(); 
            rotate(temp.begin(), temp.begin() + k%sz, temp.end());    
            
			// Step3: Setting the rotated strip back to the grid
            int it = 0;
            for(int i=lefT; i<= rigT; i++)     //  top side ( left to right)
                grid[h][i] = temp[it++];
            for(int i=lefT+1; i<=lefB;i++)    // right side ( top to bottom)
               grid[i][rigT] = temp[it++];
            for(int i=rigT-1;i>=lefT;i--)       //  bottom side  ( right to left )
                grid[lefB][i] = temp[it++];
            for(int i=lefB-1;i>lefT;i--)         // left side (bottom to top)
                grid[i][lefT] = temp[it++];

			// Shrinking the corner points
            h++;  lefT++;
            rigT--; lefB--;
        }
        return grid;
    }
};

Credit : Here

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment