We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cyclically Rotating a Grid

Difficulty: Medium

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. A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix in the counter-clockwise direction. Return the matrix after applying k cyclic rotations to it.

Key Insights

  • The matrix can be visualized as a series of concentric layers.
  • Each layer can be represented as a list of elements that can be rotated independently.
  • The effective number of rotations can be reduced using modulo operation with the length of the layer.
  • The overall problem can be solved by extracting each layer, rotating it, and placing it back into its original position.

Space and Time Complexity

Time Complexity: O(m * n) - since we need to process each element in the grid. Space Complexity: O(m + n) - for storing the layers temporarily.

Solution

To solve this problem, we can follow these steps:

  1. Identify the number of layers in the grid. Each layer can be represented by a list of its elements.
  2. For each layer, extract its elements into a list.
  3. Rotate the list of elements by k positions in a counter-clockwise direction. This can be achieved using slicing.
  4. Place the rotated list back into the corresponding positions in the grid.
  5. Return the modified grid.

We will use arrays to represent the layers and apply the rotation using simple list operations.

Code Solutions

def rotateGrid(grid, k):
    m, n = len(grid), len(grid[0])
    
    def get_layer(r1, r2, c1, c2):
        layer = []
        for j in range(c1, c2):
            layer.append(grid[r1][j])  # Top row
        for i in range(r1 + 1, r2):
            layer.append(grid[i][c2 - 1])  # Right column
        for j in range(c2 - 1, c1 - 1, -1):
            layer.append(grid[r2 - 1][j])  # Bottom row
        for i in range(r2 - 2, r1, -1):
            layer.append(grid[i][c1])  # Left column
        return layer

    def set_layer(r1, r2, c1, c2, layer):
        idx = 0
        for j in range(c1, c2):
            grid[r1][j] = layer[idx]  # Top row
            idx += 1
        for i in range(r1 + 1, r2):
            grid[i][c2 - 1] = layer[idx]  # Right column
            idx += 1
        for j in range(c2 - 1, c1 - 1, -1):
            grid[r2 - 1][j] = layer[idx]  # Bottom row
            idx += 1
        for i in range(r2 - 2, r1, -1):
            grid[i][c1] = layer[idx]  # Left column
            idx += 1

    layers = min(m, n) // 2
    for layer in range(layers):
        r1, r2 = layer, m - layer
        c1, c2 = layer, n - layer
        current_layer = get_layer(r1, r2, c1, c2)
        length = len(current_layer)
        k = k % length  # Effective rotations
        rotated_layer = current_layer[k:] + current_layer[:k]  # Rotate
        set_layer(r1, r2, c1, c2, rotated_layer)
    
    return grid
← Back to All Questions