1260. Shift 2D Grid - Explanation

Problem Link

1. Simulation (Extra Space)

Intuition

Shifting a 2D grid is like rotating all elements forward by one position. Each element moves to the next column, and elements at the end of a row wrap around to the start of the next row. The last element of the grid wraps to position (0, 0).

By simulating this process k times, we can achieve the desired result. For each shift, we copy each element to its new position in a fresh grid.

Algorithm

1. For each shift iteration (k times):
   • Create a new grid cur filled with zeros.
   • Copy each element from column c to column c + 1 in the same row.
   • Handle the last column separately: element at (r, n-1) wraps to ((r + 1) % m, 0).
   • Replace the original grid with cur.
2. Return the final grid after all shifts.

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

        while k:
            cur = [[0] * n for _ in range(m)]

            for r in range(m):
                for c in range(n - 1):
                    cur[r][c + 1] = grid[r][c]

            for r in range(m):
                cur[(r + 1) % m][0] = grid[r][n - 1]

            grid = cur
            k -= 1

        return grid

Time & Space Complexity

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

Where $m$ is the number of rows in the grid, $n$ is the number of columns in the grid, and $k$ is the shift count.

---

2. Simulation

Intuition

Instead of creating a new grid each time, we can shift elements in place. The key insight is that shifting works like a rotation: each element takes the place of the previous one. By keeping track of the last element (which wraps to the first position), we can propagate values through the entire grid in a single pass.

Algorithm

1. For each shift iteration (k times):
   • Store the last element grid[m-1][n-1] as prev.
   • Traverse the grid row by row, column by column.
   • At each cell, swap the current element with prev.
   • This naturally propagates each element to the next position.
2. Return the grid after all shifts.

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

        while k:
            prev = grid[m - 1][n - 1]
            for r in range(m):
                for c in range(n):
                    grid[r][c], prev = prev, grid[r][c]
            k -= 1

        return grid

Time & Space Complexity

• Time complexity: $O(k * m * n)$
• Space complexity: $O(m * n)$ for the output matrix.

Where $m$ is the number of rows in the grid, $n$ is the number of columns in the grid, and $k$ is the shift count.

---

3. Convert to One Dimensional Array

Intuition

A 2D grid can be viewed as a 1D array if we flatten it row by row. Shifting in a 1D array is simply rotating elements to the right. The classic way to rotate an array by k positions is to use three reversals: reverse the entire array, then reverse the first k elements, then reverse the remaining elements.

Algorithm

1. Flatten the 2D grid into a 1D array arr where arr[r * n + c] = grid[r][c].
2. Reduce k by taking k % N (where N = m * n) to avoid unnecessary full rotations.
3. Reverse the entire array.
4. Reverse the first k elements.
5. Reverse the remaining elements from index k to N-1.
6. Map the 1D array back to the 2D grid.
7. Return the result.

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

        arr = [0] * N
        for r in range(m):
            for c in range(n):
                arr[r * n + c] = grid[r][c]

        def reverse(l, r):
            while l < r:
                arr[l], arr[r] = arr[r], arr[l]
                l += 1
                r -= 1

        reverse(0, N - 1)
        reverse(0, k - 1)
        reverse(k, N - 1)

        for r in range(m):
            for c in range(n):
                grid[r][c] = arr[r * n + c]

        return grid

Time & Space 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.

---

4. Iteration

Intuition

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.

Algorithm

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.

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

Time & Space 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.