Shift 2D Grid

How it works

Instead of actually shifting elements, we can compute where each element should go after k shifts. The position of an element in a flattened grid is r * n + c. After k shifts, this becomes (r * n + c + k) % (m * n). We can then convert this back to 2D coordinates.

This approach processes each element exactly once, computing its final position directly.

Steps

1. Create a result grid of the same dimensions.
2. For each cell (r, c):
   • Compute the new flattened position: newVal = (r * n + c + k) % (m * n).
   • Convert back to 2D: newR = newVal / n, newC = newVal % n.
   • Place the original value at the new position: res[newR][newC] = grid[r][c].
3. Return the result grid.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(m * n)

Where m is the number of rows in the grid and n is the number of columns in the grid.

Things to watch for

Not Reducing k Modulo Total Elements

When k is larger than the total number of elements (m * n), performing k shifts is redundant since the grid returns to its original state after every m * n shifts. Failing to reduce k with modulo leads to unnecessary iterations and potential timeout errors.

Incorrect 2D to 1D Index Conversion

When flattening the grid or computing new positions, using incorrect formulas for converting between 2D coordinates (r, c) and 1D index causes elements to be placed in wrong positions. The correct formulas are: index = r * n + c and r = index / n, c = index % n.

from typing import List

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        M, N = len(grid), len(grid[0])

        def posToVal(r, c):
            return r * N + c

        def valToPos(v):
            return [v // N, v % N]

        res = [[0] * N for _ in range(M)]
        for r in range(M):
            for c in range(N):
                newVal = (posToVal(r, c) + k) % (M * N)
                newR, newC = valToPos(newVal)
                res[newR][newC] = grid[r][c]

        return res

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int M = grid.size(), N = grid[0].size();
        vector<vector<int>> res(M, vector<int>(N));

        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                int newVal = (r * N + c + k) % (M * N);
                int newR = newVal / N, newC = newVal % N;
                res[newR][newC] = grid[r][c];
            }
        }

        return res;
    }
};