Shift 2D Grid

Problem Statement

You're given a two-dimensional array grid measuring m rows by n columns, and an integer k. The operation required involves shifting the entire grid k times. A single shift operation is defined as follows:

• The element at grid[i][j] moves to the position grid[i][j + 1].
• The element occupying the end of the row (grid[i][n - 1]) transitions to the start of the next row (grid[i + 1][0]).
• The element at the last position of the grid (grid[m - 1][n - 1]) wraps around to the very beginning (grid[0][0]).

The task is to return the modified 2D grid after performing the shift operation k times.

Examples

Example 1

Input:

`grid` = [[1,2,3],[4,5,6],[7,8,9]], k = 1

Output:

[[9,1,2],[3,4,5],[6,7,8]]

Example 2

Input:

`grid` = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4

Output:

[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3

Input:

`grid` = [[1,2,3],[4,5,6],[7,8,9]], k = 9

Output:

[[1,2,3],[4,5,6],[7,8,9]]

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m <= 50
• 1 <= n <= 50
• -1000 <= grid[i][j] <= 1000
• 0 <= k <= 100

Approach and Intuition

The operation described in the problem can be visualized as rotating the entire grid as if its elements are in a circular queue. Here’s a step-by-step approach on how we can achieve the desired transformation:

1. Visualize the grid as a single list or sequence of elements. This would involve concatenating all rows of the grid in order. This transformation simplifies the task by reducing the 2D rotation problem into a 1D rotation problem.

2. Calculate the effective number of rotations. Since performing a number of shifts that is a multiple of the total number of elements (m * n) brings the array back to its original state, the number of effective rotations is k % (m * n).

3. Rotate the transformed 1D list. This can be derived by:

   • Moving the last k elements of this list to the front, or
   • Shifting the first (m * n - k) % (m * n) elements to the end.

4. Reform the 1D list back into the original m x n grid format. This involves properly indexing and placing each element back into its 2D position.

By following the above steps, we effectively simulate the circular shift in two dimensions by leveraging simpler operations in one dimension.

Examples:

• Example 1: A simple 3x3 grid shifted by 1. Here, each element simply moves to its next right position, where the last elements of the rows move to the start of the next rows and the very last element moves to the beginning of the grid.
• Example 2: A more complex rotation where the grid is rotated 4 times, resulting in a complete cycle for a 4x4 grid, returning each row to their original positions.
• Example 3: The scenario where k is equal to the total number of elements in the grid. The grid remains unchanged because the number of shifts brings the grid full circle back to its original configuration.

By understanding the cyclic nature of this problem, we can manipulate indices and utilize modular arithmetic to efficiently rotate the grid as required.

Solutions

class Solution {
    public List<List<Integer>> rotateGrid(int[][] matrix, int shifts) {

        int cols = matrix[0].length;
        int rows = matrix.length;

        List<List<Integer>> shiftedGrid = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            List<Integer> currentRow = new ArrayList<>();
            shiftedGrid.add(currentRow);
            for (int j = 0; j < cols; j++) {
                currentRow.add(0);
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int targetCol = (j + shifts) % cols;
                int extraRows = (j + shifts) / cols;
                int targetRow = (i + extraRows) % rows;
                shiftedGrid.get(targetRow).set(targetCol, matrix[i][j]);
            }
        }

        return shiftedGrid;
    }
}