Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1914. Cyclically Rotating a Grid - Leetcode Solution

Code Implementation

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        layers = min(m, n) // 2
        res = [row[:] for row in grid]
        
        for layer in range(layers):
            elements = []
            # Top row
            for j in range(layer, n-layer):
                elements.append(grid[layer][j])
            # Right column
            for i in range(layer+1, m-layer-1):
                elements.append(grid[i][n-layer-1])
            # Bottom row
            for j in range(n-layer-1, layer-1, -1):
                elements.append(grid[m-layer-1][j])
            # Left column
            for i in range(m-layer-2, layer, -1):
                elements.append(grid[i][layer])
            
            total = len(elements)
            k_mod = k % total
            rotated = elements[k_mod:] + elements[:k_mod]
            idx = 0
            
            # Place back rotated elements
            for j in range(layer, n-layer):
                res[layer][j] = rotated[idx]
                idx += 1
            for i in range(layer+1, m-layer-1):
                res[i][n-layer-1] = rotated[idx]
                idx += 1
            for j in range(n-layer-1, layer-1, -1):
                res[m-layer-1][j] = rotated[idx]
                idx += 1
            for i in range(m-layer-2, layer, -1):
                res[i][layer] = rotated[idx]
                idx += 1
        return res
      
class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int layers = min(m, n) / 2;
        vector<vector<int>> res = grid;
        
        for (int layer = 0; layer < layers; ++layer) {
            vector<int> elements;
            // Top row
            for (int j = layer; j < n-layer; ++j)
                elements.push_back(grid[layer][j]);
            // Right column
            for (int i = layer+1; i < m-layer-1; ++i)
                elements.push_back(grid[i][n-layer-1]);
            // Bottom row
            for (int j = n-layer-1; j >= layer; --j)
                elements.push_back(grid[m-layer-1][j]);
            // Left column
            for (int i = m-layer-2; i > layer; --i)
                elements.push_back(grid[i][layer]);
            
            int total = elements.size();
            int k_mod = k % total;
            vector<int> rotated(total);
            for (int i = 0; i < total; ++i)
                rotated[i] = elements[(i + k_mod) % total];
            int idx = 0;
            
            // Place back rotated elements
            for (int j = layer; j < n-layer; ++j)
                res[layer][j] = rotated[idx++];
            for (int i = layer+1; i < m-layer-1; ++i)
                res[i][n-layer-1] = rotated[idx++];
            for (int j = n-layer-1; j >= layer; --j)
                res[m-layer-1][j] = rotated[idx++];
            for (int i = m-layer-2; i > layer; --i)
                res[i][layer] = rotated[idx++];
        }
        return res;
    }
};
      
class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int layers = Math.min(m, n) / 2;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++)
            res[i] = grid[i].clone();
        
        for (int layer = 0; layer < layers; layer++) {
            List<Integer> elements = new ArrayList<>();
            // Top row
            for (int j = layer; j < n-layer; j++)
                elements.add(grid[layer][j]);
            // Right column
            for (int i = layer+1; i < m-layer-1; i++)
                elements.add(grid[i][n-layer-1]);
            // Bottom row
            for (int j = n-layer-1; j >= layer; j--)
                elements.add(grid[m-layer-1][j]);
            // Left column
            for (int i = m-layer-2; i > layer; i--)
                elements.add(grid[i][layer]);
            
            int total = elements.size();
            int k_mod = k % total;
            List<Integer> rotated = new ArrayList<>();
            for (int i = 0; i < total; i++)
                rotated.add(elements.get((i + k_mod) % total));
            int idx = 0;
            
            // Place back rotated elements
            for (int j = layer; j < n-layer; j++)
                res[layer][j] = rotated.get(idx++);
            for (int i = layer+1; i < m-layer-1; i++)
                res[i][n-layer-1] = rotated.get(idx++);
            for (int j = n-layer-1; j >= layer; j--)
                res[m-layer-1][j] = rotated.get(idx++);
            for (int i = m-layer-2; i > layer; i--)
                res[i][layer] = rotated.get(idx++);
        }
        return res;
    }
}
      
var rotateGrid = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const layers = Math.floor(Math.min(m, n) / 2);
    const res = grid.map(row => row.slice());
    
    for (let layer = 0; layer < layers; layer++) {
        let elements = [];
        // Top row
        for (let j = layer; j < n-layer; j++)
            elements.push(grid[layer][j]);
        // Right column
        for (let i = layer+1; i < m-layer-1; i++)
            elements.push(grid[i][n-layer-1]);
        // Bottom row
        for (let j = n-layer-1; j >= layer; j--)
            elements.push(grid[m-layer-1][j]);
        // Left column
        for (let i = m-layer-2; i > layer; i--)
            elements.push(grid[i][layer]);
        
        const total = elements.length;
        const k_mod = k % total;
        const rotated = elements.slice(k_mod).concat(elements.slice(0, k_mod));
        let idx = 0;
        
        // Place back rotated elements
        for (let j = layer; j < n-layer; j++)
            res[layer][j] = rotated[idx++];
        for (let i = layer+1; i < m-layer-1; i++)
            res[i][n-layer-1] = rotated[idx++];
        for (let j = n-layer-1; j >= layer; j--)
            res[m-layer-1][j] = rotated[idx++];
        for (let i = m-layer-2; i > layer; i--)
            res[i][layer] = rotated[idx++];
    }
    return res;
};

Problem Description

You are given a 2D integer grid called grid and an integer k. The task is to cyclically rotate each "layer" of the grid in a clockwise direction, k times. A layer is defined as a set of elements that form a border around the grid or its subgrids (like the outermost border, then the next inner border, etc.).

For each rotation, every element in a layer moves one position forward along the border of the layer. After rotating all layers k times, you must return the modified grid.

Constraints:

  • Each element must be used exactly once; do not reuse or skip any elements.
  • There is only one valid solution for each input.
  • The grid is at least 2x2 in size.

Thought Process

To solve this problem, first, we need to understand what a "layer" is. Imagine peeling an onion: the outermost layer is the border, and as you move inward, you encounter more layers. For each layer, we need to collect its elements, rotate them, and then put them back in their respective places.

A brute-force approach would be to rotate the entire grid k times, moving each element one by one, but this is inefficient, especially for large k. Instead, we can optimize by:

  • Extracting the elements of each layer into a list.
  • Rotating the list efficiently using modular arithmetic.
  • Placing the rotated elements back into their correct positions in the grid.
This reduces unnecessary moves and avoids redundant computations.

Solution Approach

The solution involves processing each layer independently. Here is a step-by-step breakdown:

  1. Identify the Number of Layers: The number of layers is min(m, n) // 2, where m and n are the grid's dimensions.
  2. Extract Layer Elements:
    • Traverse the top row of the layer from left to right.
    • Traverse the right column from top to bottom (excluding corners already covered).
    • Traverse the bottom row from right to left.
    • Traverse the left column from bottom to top.
    This gives all elements in the current layer in order.
  3. Rotate the Layer:
    • Calculate k % len(layer) to avoid unnecessary full cycles.
    • Rotate the list by slicing: the new start is at index k % len(layer).
  4. Place Elements Back:
    • Follow the same traversal as extraction, but now assign the rotated values back to the grid.
  5. Repeat for All Layers: Continue the process for each layer, moving inward.

This approach ensures each element is moved exactly once per rotation, and the use of lists and modular arithmetic makes the process efficient.

Example Walkthrough

Suppose grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]] and k = 2.

Layer 0 (outermost):

  • Extract: [1,2,3,4,8,12,16,15,14,13,9,5]
  • Rotate by 2: [3,4,8,12,16,15,14,13,9,5,1,2]
  • Place back in the same order, starting at the same position.

Layer 1 (inner):

  • Extract: [6,7,11,10]
  • Rotate by 2: [11,10,6,7]
  • Place back in the same order.

Resulting grid:

  • First row: [3,4,8,12]
  • Second row: [5,11,10,16]
  • Third row: [1,6,7,15]
  • Fourth row: [2,9,13,14]

This step-by-step process demonstrates how each layer is rotated independently and efficiently.

Time and Space Complexity

Brute-force Approach:

  • Time: O(k * m * n) – Each rotation moves every element individually, repeated k times.
  • Space: O(1) – In-place, but inefficient.
Optimized Approach:
  • Time: O(m * n) – Each element is visited a constant number of times (once for extraction, once for placement).
  • Space: O(m * n) – For the result grid, plus O(min(m, n)) for layer lists.

The optimized approach is much faster for large k values, as it avoids unnecessary rotations by using modular arithmetic.

Summary

The key to solving the cyclically rotating grid problem efficiently is to process each layer independently, extract its elements, rotate them using modular arithmetic, and place them back. This avoids redundant moves and leverages the structure of the grid, resulting in a clean and efficient solution that scales well for large grids and large k. The approach is both intuitive and optimal, making it a great example of algorithmic thinking.