Shift 2D Grid - Video Solutions

Problem Overview: You receive an m x n grid and an integer k. Each shift moves every element one step to the right, the last element of a row becomes the first of the next row, and the bottom‑right element wraps to the top‑left. After performing the shift operation k times, return the final grid configuration.

Approach 1: 1D Array Transformation (Time: O(mn), Space: O(mn))

The key observation is that the grid behaves like a single circular array of length m * n. Flatten the array/matrix indices into a 1D index using index = row * n + col. After k shifts, the element moves to (index + k) % (m * n). Convert that new index back to 2D coordinates using division and modulo.

This avoids performing the shift operation repeatedly. Instead, iterate through the grid once, compute the destination index, and place the element in the result grid. The approach is clean and deterministic: one pass to map positions and rebuild the grid. Time complexity stays O(mn) regardless of k, and space complexity is O(mn) for the new grid.

Approach 2: In-Place Simulation (Time: O(kmn), Space: O(1))

This method directly simulates the shift operation exactly as described. For each shift, traverse the grid from the bottom‑right corner while carrying the previous value that should move into the current cell. The value from the last cell wraps around to the first position.

Although you can reduce unnecessary work by computing k = k % (m * n), each shift still requires scanning the entire matrix. That results in O(kmn) time in the worst case. The advantage is constant extra memory because the transformation happens directly inside the grid. This technique mirrors the problem’s simulation behavior and is easy to reason about step by step.

Recommended for interviews: The 1D index transformation is the expected solution. It shows you recognize that a 2D grid can be treated as a circular linear structure and optimized using modular arithmetic. Interviewers often accept the simulation approach first because it demonstrates understanding of the shift rules, but the index‑mapping solution proves stronger algorithmic thinking with optimal O(mn) time.