Skip to main content

Matrix

Cyclically Rotating a Grid Solution In C++/Python/java/JS

Cyclically Rotating a Grid Question Description

Problem Description

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:
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:
Return the matrix after applying k cyclic rotations to it.

Example

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

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
💡
Try Solving "Cyclically Rotating a Grid" Yourself First !!
Figuring out "Cyclically Rotating a Grid solution" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!

Optimal Approach

Intuition

So, we’re given a grid with even number of rows and columns, and we’re asked to perform k cyclic rotations on each layer of the grid. What’s our first instinct here?Let’s break it down. First of all, what’s a “layer” in a grid?

Like, is it the outer ring of the matrix?
Exactly! Think of an onion, the outermost skin is one layer, then there’s another one inside that, and so on. For example, if we have this 4x4 grid:

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

You see how the numbers around the edges form a border or ring? That’s our first layer. Got it. And then the numbers like 6, 7, 10, 11 form the second layer?Perfect! So let’s pick a simpler example, maybe a 4x2 grid — to keep things manageable:

1 2
3 4
5 6
7 8

Let’s say we’re told to rotate it once (k = 1). Now, before diving in, let’s ask what does "rotate" even mean here?

The question says we have to rotate each layer counter-clockwise. So for this example, how do we find the layer? Good question. In this 4x2 grid, the whole thing is one layer, since it's just two columns. If we go around it in a counter-clockwise order, the elements would appear in this sequence:

CopyEdit1 → 2 → 4 → 6 → 8 → 7 → 5 → 3

So, this is our layer, flattened out as a list:[1, 2, 4, 6, 8, 7, 5, 3]

If we rotate this list once to the left (because it’s counter-clockwise), we get:
[2, 4, 6, 8, 7, 5, 3, 1]
Now here’s where things get interesting. We want to take this list and "wrap" it back into the grid, using the same traversal path we used to flatten it.

So we're kind of treating the perimeter like a loop and shifting elements along it?Exactly! That’s the intuition. Instead of moving each value one by one in place which can get messy, we convert the perimeter into a 1D list, rotate it, then put it back.

That seems easier to manage than trying to rotate in place. Yes, it’s a cleaner approach and lets us avoid bugs. And actually, what we’re doing is intuitively known as a layered simulation approach. We flatten each layer, rotate, and write it back.

Let’s pause for a moment and ask: what if k is really large? Like 1 billion?
Then we’d just rotate a billion times?

That’s the trap! We don’t need to. If the layer has, say, 8 elements, then rotating it 8 times brings it back to the original state. So rotating 1 billion times is the same as rotating 1_000_000_000 % 8 times.

So we just do k % layerSize.

Spot on. Now for the actual implementation, we repeat this process for each layer - outer to inner. For a grid with m rows and n columns, how many such layers do we have?

Maybe min(m, n) / 2?
Because each layer eats up two rows and two columns — one on each side. So we loop over each layer, flatten it, rotate it, and put it back.

Yes! Now, let’s outline the steps of our Algorithm

Cyclically Rotating a Grid Algorithm

Main Method: rotateGrid(int[][] grid, int k)

  • Get the number of rows (rowCount) and columns (colCount) from the grid.
  • Save the input grid to an instance variable for internal use.
  • Loop through each layer of the matrix:
    • The total number of layers is min(rowCount, colCount) / 2.
    • For each layer, call rotateLayer(layer, k) to rotate it k times.

Helper Method: rotateLayer(int layer, int k)
Step 1: Extract Layer Elements

  • Create an empty list to store the elements of the current layer.
  • Traverse the perimeter of the layer in clockwise order:
    • Top row → left to right (excluding the last corner)
    • Right column → top to bottom (excluding the last corner)
    • Bottom row → right to left (excluding the last corner)
    • Left column → bottom to top (excluding the last corner)

Step 2: Rotate the List

  • Compute rotations % totalElements to avoid redundant full cycles.
  • If rotations == 0, return early.
  • Otherwise, treat the list as circular and rotate the elements by updating the grid with the rotated order:
    • Top row ← first segment of rotated list
    • Right column ← next segment
    • Bottom row ← next segment (reversed)
    • Left column ← remaining segment (reversed) 

Fine !! Let's now see how to code the approach !!

Let's Visualize the Dry-Run with a Video

0:00
/1:26

Dry-Run

Input: grid =[[1,2,3,8],[5,6,7,4], [9,10,11,15],[12,14,13,16]]
k=2
Output:- [[3,8,4,15],[2,11,10,16],[1,7,6,13],[5,9,12,14]]

Layer-wise Rotation

Layer 0 (Outer boundary)

  • Collect elements clockwise:
    • Top row → 1 2 3
    • Right column → 8 4 15
    • Bottom row (reversed) → 16 13 14
    • Left column (bottom to top) → 12 9 5
    • Elements: [1, 2, 3, 8, 4, 15, 16, 13, 14, 12, 9, 5]
  • Rotate by k = 2 positions left:
    • Result: [3, 8, 4, 15, 16, 13, 14, 12, 9, 5, 1, 2]
  • Place back into Layer 0:
    • Top row → 3 8 4
    • Right column → 15 16 13
    • Bottom row (right to left) → 14 12 9
    • Left column (bottom to top) → 5 1 2
  • Matrix after Layer 0:

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

Layer 1 (Inner 2×2 square)

  • Collect elements clockwise:
    • Top row → 6 7
    • Right column → 11
    • Bottom row → 10
    • Elements: [6, 7, 11, 10]
  • Rotate by k = 2 positions left:
    • Result: [11, 10, 6, 7]
  • Place back into Layer 1:
    • Top row → 11 10
    • Right column → 6
    • Bottom row → 7
  • Final Rotated Matrix:

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

Cyclically Rotating a Grid Solution

Now lets checkout the "Cyclically Rotating a Grid code in C++ , Java, Python and JavaScript.

"Cyclically Rotating a Grid" Code in all Languages.
1. Cyclically Rotating a Grid solution in C++ Try on Compiler 
#include <iostream>
#include <vector>
using namespace std;

class Solution {
private:
    int rowCount;
    int colCount;
    vector<vector<int>> grid;

public:
    // Method to rotate the grid layers k times
    vector<vector<int>> rotateGrid(vector<vector<int>>& inputGrid, int k) {
        // Set row and column count
        rowCount = inputGrid.size();
        colCount = inputGrid[0].size();
        grid = inputGrid;

        // Rotate each layer of the grid
        for (int layer = 0; layer < min(rowCount, colCount) / 2; ++layer) {
            rotateLayer(layer, k);
        }

        // Return the modified grid
        return grid;
    }

private:
    // Helper to rotate a single layer of the grid
    void rotateLayer(int layer, int k) {
        vector<int> elements;

        // Top row
        for (int col = layer; col < colCount - layer - 1; ++col) {
            elements.push_back(grid[layer][col]);
        }

        // Right column
        for (int row = layer; row < rowCount - layer - 1; ++row) {
            elements.push_back(grid[row][colCount - layer - 1]);
        }

        // Bottom row
        for (int col = colCount - layer - 1; col > layer; --col) {
            elements.push_back(grid[rowCount - layer - 1][col]);
        }

        // Left column
        for (int row = rowCount - layer - 1; row > layer; --row) {
            elements.push_back(grid[row][layer]);
        }

        int total = elements.size();
        k %= total;

        // Apply rotation
        int idx = 0;
        for (int col = layer; col < colCount - layer - 1; ++col)
            grid[layer][col] = elements[(k + idx++) % total];
        for (int row = layer; row < rowCount - layer - 1; ++row)
            grid[row][colCount - layer - 1] = elements[(k + idx++) % total];
        for (int col = colCount - layer - 1; col > layer; --col)
            grid[rowCount - layer - 1][col] = elements[(k + idx++) % total];
        for (int row = rowCount - layer - 1; row > layer; --row)
            grid[row][layer] = elements[(k + idx++) % total];
    }
};

int main() {
    // Read grid dimensions and number of rotations
    int m, n, k;
    cin >> m >> n >> k;

    // Read the grid
    vector<vector<int>> grid(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> grid[i][j];

    // Call the solution
    Solution sol;
    vector<vector<int>> rotated = sol.rotateGrid(grid, k);

    // Print the rotated grid
    for (auto& row : rotated) {
        for (int val : row) cout << val << " ";
        cout << "\n";
    }

    return 0;
}

2. Cyclically Rotating a Grid Solution in Java Try on Compiler 
import java.util.*;

class Solution {
    private int rowCount; // The number of rows in the grid
    private int colCount; // The number of columns in the grid
    private int[][] grid; // The grid to be rotated

    // Method to rotate the grid layer by layer
    public int[][] rotateGrid(int[][] grid, int k) {

        // Initialize the number of rows
        rowCount = grid.length;

        // Initialize the number of columns
        colCount = grid[0].length;

        // Set the instance grid variable to the input grid
        this.grid = grid;

        // Iterate over the layers of the grid
        for (int layer = 0; layer < Math.min(rowCount, colCount) / 2; ++layer) {

            // Rotate each layer k times
            rotateLayer(layer, k);
        }

        // Return the rotated grid
        return grid;
    }

    // Helper method to rotate one layer
    private void rotateLayer(int layer, int rotations) {

        // Store the elements of the current layer
        List<Integer> elements = new ArrayList<>();

        // Top row, left to right
        for (int col = layer; col < colCount - layer - 1; ++col) {
            elements.add(grid[layer][col]);
        }

        // Right column, top to bottom
        for (int row = layer; row < rowCount - layer - 1; ++row) {
            elements.add(grid[row][colCount - layer - 1]);
        }

        // Bottom row, right to left
        for (int col = colCount - layer - 1; col > layer; --col) {
            elements.add(grid[rowCount - layer - 1][col]);
        }

        // Left column, bottom to top
        for (int row = rowCount - layer - 1; row > layer; --row) {
            elements.add(grid[row][layer]);
        }

        // Total number of elements in the current layer
        int totalElements = elements.size();

        // Normalize rotations to the range of 0 to totalElements - 1
        rotations %= totalElements;

        // Return early if no rotation is needed
        if (rotations == 0) {
            return;
        }

        // Apply the rotation to the layer
        for (int col = layer; col < colCount - layer - 1; ++col) {
            grid[layer][col] = elements.get((rotations++) % totalElements);
        }
        for (int row = layer; row < rowCount - layer - 1; ++row) {
            grid[row][colCount - layer - 1] = elements.get((rotations++) % totalElements);
        }
        for (int col = colCount - layer - 1; col > layer; --col) {
            grid[rowCount - layer - 1][col] = elements.get((rotations++) % totalElements);
        }
        for (int row = rowCount - layer - 1; row > layer; --row) {
            grid[row][layer] = elements.get((rotations++) % totalElements);
        }
    }

    // Main method to read input and display output
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read number of rows and columns
        int rowCount = scanner.nextInt();
        int colCount = scanner.nextInt();

        // Initialize the grid
        int[][] grid = new int[rowCount][colCount];

        // Read grid elements
        for (int i = 0; i < rowCount; ++i) {
            for (int j = 0; j < colCount; ++j) {
                grid[i][j] = scanner.nextInt();
            }
        }

        // Read number of rotations
        int k = scanner.nextInt();

        // Create a solution instance
        Solution solution = new Solution();

        // Get the rotated grid
        int[][] result = solution.rotateGrid(grid, k);

        // Print the rotated grid
        for (int[] row : result) {
            for (int value : row) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }
}

3. Cyclically Rotating a Grid Solution in Python Try on Compiler 
class Solution:
    def __init__(self):
        self.grid = []
        self.row_count = 0
        self.col_count = 0

    # Method to rotate each layer of the grid k times
    def rotateGrid(self, grid, k):
        # Initialize grid dimensions
        self.grid = grid
        self.row_count = len(grid)
        self.col_count = len(grid[0])

        # Rotate each layer individually
        for layer in range(min(self.row_count, self.col_count) // 2):
            self.rotateLayer(layer, k)

        # Return the rotated grid
        return self.grid

    # Helper method to rotate one layer
    def rotateLayer(self, layer, k):
        elements = []

        # Top row (left to right)
        for col in range(layer, self.col_count - layer - 1):
            elements.append(self.grid[layer][col])

        # Right column (top to bottom)
        for row in range(layer, self.row_count - layer - 1):
            elements.append(self.grid[row][self.col_count - layer - 1])

        # Bottom row (right to left)
        for col in range(self.col_count - layer - 1, layer, -1):
            elements.append(self.grid[self.row_count - layer - 1][col])

        # Left column (bottom to top)
        for row in range(self.row_count - layer - 1, layer, -1):
            elements.append(self.grid[row][layer])

        total = len(elements)
        k %= total  # Normalize rotations

        # Rotate and write back to grid
        idx = 0
        for col in range(layer, self.col_count - layer - 1):
            self.grid[layer][col] = elements[(k + idx) % total]
            idx += 1
        for row in range(layer, self.row_count - layer - 1):
            self.grid[row][self.col_count - layer - 1] = elements[(k + idx) % total]
            idx += 1
        for col in range(self.col_count - layer - 1, layer, -1):
            self.grid[self.row_count - layer - 1][col] = elements[(k + idx) % total]
            idx += 1
        for row in range(self.row_count - layer - 1, layer, -1):
            self.grid[row][layer] = elements[(k + idx) % total]
            idx += 1

# Main code to read input
if __name__ == "__main__":
    # Read dimensions and k
    m, n, k = map(int, input().split())

    # Read grid values
    grid = [list(map(int, input().split())) for _ in range(m)]

    # Solve and print result
    sol = Solution()
    result = sol.rotateGrid(grid, k)
    for row in result:
        print(" ".join(map(str, row)))

4. Cyclically Rotating a Grid solution in JavaScript Try on Compiler 
function solve(stdin) {
    // Split input into lines
    const lines = stdin.trim().split('\n');

    // Parse grid dimensions and rotations
    const [m, n, k] = lines[0].trim().split(' ').map(Number);

    // Parse grid
    const grid = [];
    for (let i = 1; i <= m; i++) {
        grid.push(lines[i].trim().split(' ').map(Number));
    }

    class Solution {
        constructor() {
            this.grid = [];
            this.rowCount = 0;
            this.colCount = 0;
        }

        // Main method to rotate grid
        rotateGrid(grid, k) {
            this.grid = grid;
            this.rowCount = grid.length;
            this.colCount = grid[0].length;

            for (let layer = 0; layer < Math.min(this.rowCount, this.colCount) / 2; layer++) {
                this.rotateLayer(layer, k);
            }

            return this.grid;
        }

        // Rotate a single layer
        rotateLayer(layer, k) {
            const elements = [];

            // Top row
            for (let col = layer; col < this.colCount - layer - 1; col++) {
                elements.push(this.grid[layer][col]);
            }

            // Right column
            for (let row = layer; row < this.rowCount - layer - 1; row++) {
                elements.push(this.grid[row][this.colCount - layer - 1]);
            }

            // Bottom row
            for (let col = this.colCount - layer - 1; col > layer; col--) {
                elements.push(this.grid[this.rowCount - layer - 1][col]);
            }

            // Left column
            for (let row = this.rowCount - layer - 1; row > layer; row--) {
                elements.push(this.grid[row][layer]);
            }

            const total = elements.length;
            k %= total;

            let idx = 0;

            // Fill top row
            for (let col = layer; col < this.colCount - layer - 1; col++) {
                this.grid[layer][col] = elements[(k + idx++) % total];
            }

            // Fill right column
            for (let row = layer; row < this.rowCount - layer - 1; row++) {
                this.grid[row][this.colCount - layer - 1] = elements[(k + idx++) % total];
            }

            // Fill bottom row
            for (let col = this.colCount - layer - 1; col > layer; col--) {
                this.grid[this.rowCount - layer - 1][col] = elements[(k + idx++) % total];
            }

            // Fill left column
            for (let row = this.rowCount - layer - 1; row > layer; row--) {
                this.grid[row][layer] = elements[(k + idx++) % total];
            }
        }
    }

    // Solve
    const solution = new Solution();
    const result = solution.rotateGrid(grid, k);

    // Output result
    for (const row of result) {
        console.log(row.join(' '));
    }
}

// Handle input via readline
;(() => {
    process.stdin.resume();
    process.stdin.setEncoding('utf-8');

    let input = '';
    process.stdin.on('data', chunk => input += chunk);
    process.stdin.on('end', () => solve(input));
})();

Minimum Operations to Write the Letter Y on a Grid Complexity Analysis

Time Complexity: O(m x n)

Let m = rowCount and n = colCount

Number of Layers:
The number of layers is min(m, n) / 2
→ Let's call this L (i.e. L = min(m, n) / 2)

For Each Layer:
Let’s analyze the cost per layer:
A single layer has O(P) elements where
P = 2 × (rows in layer + cols in layer) - 4 = 2 × ((m - 2×layer) + (n - 2×layer)) - 4
So every layer is O(m + n) in the worst case.

For each layer
Extract elements → O(P)
Write back elements → O(P)
Total for one layer: O(P)

Across All Layers
Across all L layers: the total work is
O(total number of elements in the grid)

Because each cell belongs to exactly one layer, the sum of elements over all layers is exactly m × n

So the total time complexity is:
Final Time Complexity: O(m × n)

About k (number of rotations):

  • You're rotating using modulo: rotations %= totalElements
  • No shifting of the list is done — just indexing with a rotated offset during the copy-back step.
  • So rotation cost is O(1) per element — no extra time per rotation.

Therefore, k does not impact time complexity.

Space Complexity: O(m + n)

Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm, excluding input and output.

Key usage: For each layer, you store the layer’s boundary elements in a list:
List<Integer> elements = new ArrayList<>();

Let’s analyze how big this list can grow. For Each Layer:

The number of elements in each layer is:
P = 2 × ((m - 2×layer) + (n - 2×layer)) - 4

At most, the outermost layer (layer 0) has:P = 2 × (m + n) - 4 ≈ O(m + n)

You repeat this for each layer, but only one layer is processed at a time, so:

Only one List<Integer> is active at a time.
So the Auxiliary Space Complexity is: O(m + n) — to hold one layer at a time.

Total Space Complexity

Total space includes:

  • Input: int[][] grid → O(m × n)
  • Output: modifies the same grid in-place → no extra output space
  • Auxiliary: as calculated above → O(m + n)

So the Total Space Complexity is: O(m × n) (for the grid itself)
+ O(m + n) (temporary list)

But typically, we omit input space in total space complexity analysis unless you're creating a new grid.

So depending on whether the grid is considered part of the space cost:

  • If including input: O(m × n)
  • If excluding input: O(m + n)

Similar Problems

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Rat in a Maze Problem - I

Consider a rat placed at position (0, 0) in an n x n square matrix mat. The rat's goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions: 'U'(up), 'D'(down), 'L' (left), 'R' (right).

The matrix contains only two possible values:

  • 0: A blocked cell through which the rat cannot travel.
  • 1: A free cell that the rat can pass through.