Cyclically Rotating A Grid - Leetcode Solution

Problem Statement:

Given a 2d grid of integers, a top-left coordinate (row1, col1), and a bottom-right coordinate (row2, col2), you need to cyclically rotate the sub-grid enclosed by those coordinates by 1 step clockwise.

In particular, content located on the boundary of the sub-grid should be moved such that each element is shifted right once, and the rightmost element of each row moves to the leftmost column of that row. Similarly, the bottom element of each column moves to the topmost row of that column.

The following example shows what happens to the grid Z shown on the left after rotating its sub-grid enclosed by (row1 = 1, col1 = 2) and (row2 = 4, col2 = 5) clockwise by 1 step.

Example:

Input: grid = [[1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20], [21,22,23,24,25]] row1 = 1, col1 = 2, row2 = 4, col2 = 5 Output: [[1, 2, 3, 4, 5], [6, 20, 21, 22, 10], [11, 18, 19, 15, 14], [16, 17, 13, 9, 8], [21, 22, 23, 24, 25]]

Solution:

The solution of this problem can be divided into three parts.

1. Creating 1D array of the sub-grid: We need to create a 1D array of the sub-grid enclosed by (row1, col1) and (row2, col2). We can do so by iterating from row1 to row2 and for each row, iterating from col1 to col2 and adding the element to the 1D array. At the end of this process, we will have a 1D array containing the elements of the sub-grid.

2. Rotating the 1D array: We need to rotate the 1D array by one step clockwise. We can do so by moving the last element of the array to the first position and shifting all other elements to the right. We can use a temporary variable to hold the last element while shifting elements to the right.

3. Filling the sub-grid with rotated elements: We need to fill the sub-grid enclosed by (row1, col1) and (row2, col2) with elements from the rotated 1D array. We can use two pointers, one pointing to the start of the 1D array, and the other pointing to the start of the sub-grid. We can fill the sub-grid row by row and column by column and increment both pointers accordingly, while also wrapping around to the start of the 1D array when we reach its end.

Code:

class Solution: def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]: m, n = len(grid), len(grid[0]) row1, col1, row2, col2 = 0, 0, m-1, n-1

    while row1 < row2 and col1 < col2:
        # Creating 1D array of the sub-grid
        sub_grid = []
        for j in range(col1, col2+1):
            sub_grid.append(grid[row1][j])
        for i in range(row1+1, row2+1):
            sub_grid.append(grid[i][col2])
        for j in range(col2-1, col1-1, -1):
            sub_grid.append(grid[row2][j])
        for i in range(row2-1, row1, -1):
            sub_grid.append(grid[i][col1])
        
        # Rotating the 1D array
        k %= len(sub_grid)
        sub_grid = sub_grid[-k:] + sub_grid[:-k]
        
        # Filling the sub-grid with rotated elements
        p = 0
        for j in range(col1, col2+1):
            grid[row1][j] = sub_grid[p]
            p += 1
        for i in range(row1+1, row2+1):
            grid[i][col2] = sub_grid[p]
            p += 1
        for j in range(col2-1, col1-1, -1):
            grid[row2][j] = sub_grid[p]
            p += 1
        for i in range(row2-1, row1, -1):
            grid[i][col1] = sub_grid[p]
            p += 1
        
        # Updating the sub-grid boundary
        row1 += 1
        col1 += 1
        row2 -= 1
        col2 -= 1
    
    return grid

1