Shift 2D Grid

Difficulty: Easy | Acceptance: 68.00% | Paid: No Topics: Array, Matrix, Simulation

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift, move each element grid[i][j] to grid[i][j + 1]. If grid[i][j + 1] does not exist (i.e., j == n - 1), then move the element to grid[i + 1][0]. If grid[i + 1][0] does not exist (i.e., i == m - 1), then move the element to grid[0][0].

Return the 2D grid after applying shift to k.

• Examples
• Constraints
• Flatten and Shift
• Direct Index Mapping

Examples

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Explanation:
The diagram above shows the elements moving from their original positions to their new positions after shifting the grid once.

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]]
Explanation:
The diagram above shows the elements moving from their original positions to their new positions after shifting the grid 4 times.

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Explanation:
Since the grid has 9 elements, shifting it 9 times results in the original grid.

Constraints

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

Flatten and Shift

Intuition Treat the 2D grid as a single 1D array. Shifting a 1D array is a standard problem (rotate array). After shifting, map the 1D array back to 2D.

Steps

• Flatten the 2D grid into a 1D list.
• Normalize k by taking k modulo the total number of elements.
• Slice the 1D list to perform the rotation: the last k elements become the first part, and the rest follow.
• Reconstruct the 2D grid from the rotated 1D list.

class Solution:
    def shiftGrid(self, grid: list[list[int]], k: int) -> list[list[int]]:
        m, n = len(grid), len(grid[0])
        flat = [num for row in grid for num in row]
        k %= len(flat)
        flat = flat[-k:] + flat[:-k]
        
        res = [[0] * n for _ in range(m)]
        idx = 0
        for i in range(m):
            for j in range(n):
                res[i][j] = flat[idx]
                idx += 1
        return res

Complexity

• Time: O(m * n)
• Space: O(m * n)
• Notes: We use extra space for the flattened array and the result grid.

Direct Index Mapping

Intuition Instead of creating a separate flat list, calculate the target index for each cell (i, j) directly using modulo arithmetic to determine its new position in the result grid.

Steps

• Calculate the total number of elements and normalize k.
• Create a result grid of the same dimensions.
• Iterate through every cell (i, j) in the original grid.
• Calculate the 1D index of the current cell: idx = i * n + j.
• Calculate the new 1D index after shifting: new_idx = (idx + k) % total.
• Convert new_idx back to 2D coordinates: new_i = new_idx // n, new_j = new_idx % n.
• Assign the value to the new position in the result grid.

class Solution:
    def shiftGrid(self, grid: list[list[int]], k: int) -> list[list[int]]:
        m, n = len(grid), len(grid[0])
        total = m * n
        k %= total
        res = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                idx = (i * n + j + k) % total
                res[idx // n][idx % n] = grid[i][j]
        return res

Complexity

• Time: O(m * n)
• Space: O(m * n)
• Notes: This approach avoids the overhead of creating an intermediate flattened list, though the space complexity remains dominated by the output grid.