LeetCode Solutions Blog

Cyclically Rotating a Grid

Number: 2043

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an m x n matrix (with both m and n being even) and an integer k, the grid is divided into layers (or rings). A cyclic rotation means that every element in each layer moves one position in the counter-clockwise direction. After applying k such rotations to each layer, return the resulting matrix.

Key Insights

Identify each layer of the grid as a separate ring defined by its boundaries.
Extract the elements of each ring into a one-dimensional list by traversing the perimeter in a consistent order.
Use modulo arithmetic to reduce the number of rotations (k mod length of ring) if k is very large.
Rotate the list accordingly and then map the rotated elements back into the grid in the same order.
Ensure proper handling of indices while extracting and placing back elements.

Space and Time Complexity

Time Complexity: O(mn) because every element in the grid is processed. Space Complexity: O(mn) in the worst-case due to storing elements of layers separately (though it is possible to do in-place with careful bookkeeping).

Solution

The approach iterates over each layer (or ring) of the grid. For a given layer, the boundary indices (top, bottom, left, and right) are determined. Then, the elements along the perimeter of the layer are extracted in a clockwise order (which means that a left shift of the list corresponds to one counter-clockwise rotation). The effective number of rotations is determined by k modulo the number of elements in that layer. After rotating the list, the elements are placed back into the grid following the same order. This process repeats for all layers, yielding the final rotated grid.

Code Solutions

# Define the function to rotate the grid
def rotateGrid(grid, k):
    m, n = len(grid), len(grid[0])
    # Number of layers is min(m,n)//2
    layers = min(m, n) // 2
    
    # Process each layer individually
    for layer in range(layers):
        top, left = layer, layer
        bottom, right = m - layer - 1, n - layer - 1
        
        # Extract the elements of the current ring in clockwise order
        elements = []
        # Top row: left to right
        for j in range(left, right + 1):
            elements.append(grid[top][j])
        # Right column: top+1 to bottom-1
        for i in range(top + 1, bottom):
            elements.append(grid[i][right])
        # Bottom row: right to left
        for j in range(right, left - 1, -1):
            elements.append(grid[bottom][j])
        # Left column: bottom-1 to top+1
        for i in range(bottom - 1, top, -1):
            elements.append(grid[i][left])
        
        # Compute effective rotations
        rotation = k % len(elements)
        # Rotate counter-clockwise by shifting left
        rotated = elements[rotation:] + elements[:rotation]
        
        # Place the rotated elements back into the grid
        index = 0
        # Top row: left to right
        for j in range(left, right + 1):
            grid[top][j] = rotated[index]
            index += 1
        # Right column: top+1 to bottom-1
        for i in range(top + 1, bottom):
            grid[i][right] = rotated[index]
            index += 1
        # Bottom row: right to left
        for j in range(right, left - 1, -1):
            grid[bottom][j] = rotated[index]
            index += 1
        # Left column: bottom-1 to top+1
        for i in range(bottom - 1, top, -1):
            grid[i][left] = rotated[index]
            index += 1

    return grid

# Example usage:
if __name__ == "__main__":
    grid = [[40, 10], [30, 20]]
    k = 1
    # Expected output: [[10,20],[40,30]]
    print(rotateGrid(grid, k))