💬 Discord
Sign In
NeetCode #912LC-1260EasyMath & Geometry
← Back to All Problems

#912 · #1260 · Shift 2D Grid(二维网格迁移)

📌 Problem Statement & Constraints

Given an m x n grid and an integer k, shift the grid k times: each shift moves grid[i][j] to grid[i][j + 1], wraps the last element of each row to the first element of the next row, and wraps the bottom-right element to the top-left. Return the shifted grid. Constraints: 1 <= m, n <= 50, -1000 <= grid[i][j] <= 1000, 0 <= k <= 100.

💡 Core Algorithmic Approaches

  1. Flatten the grid into a row-major 1D array of length total = m * n.
  2. A single shift is a right rotation of that flat array by one, so k shifts are a right rotation by k % total.
  3. Map each flat index idx to its new flat index (idx + k) % total, then convert back to 2D coordinates (new // n, new % n).
  4. Reducing k modulo total keeps the work independent of k's magnitude.

💻 Benchmark Python3 Implementation

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
        flat = [grid[i][j] for i in range(m) for j in range(n)]
        res = [[0] * n for _ in range(m)]
        for idx in range(total):
            nxt = (idx + k) % total
            res[nxt // n][nxt % n] = flat[idx]
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): one pass to flatten and one pass to rebuild.
💾 Space Complexity
O(m * n): the flattened copy and the output grid.

⚠️ Interview Pitfalls & Follow-ups

  • Shifting each row independently: the carry must flow from the end of one row into the start of the next.
  • Skipping k %= total: for large k the rotation would be applied more times than necessary, and in general the modulo is required for correctness of the index mapping.
  • Using (idx - k) % total: the direction must match the problem's right shift.
  • Shifting in place with a naive loop: the carry would overwrite elements before they are read, so a copy or a fresh output is needed.