Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.
In one shift operation:
grid[i][j] moves to grid[i][j + 1].grid[i][n - 1] moves to grid[i + 1][0].grid[m - 1][n - 1] moves to grid[0][0].Return the 2D grid after applying shift operation k times.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Example 2:
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]]
Example 3:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Constraints:
m == grid.lengthn == grid[i].length1 <= m <= 501 <= n <= 50-1000 <= grid[i][j] <= 10000 <= k <= 100Transform the 2D grid into a 1D list: The problem of shifting all elements in a 2D grid can be simplified by flattening the grid into a 1D array. This enables easier shifting and indexing.
Shift the 1D Array: Determine the actual number of shifts needed by computing k % (m * n) to avoid redundant full rotations. Then partition and concatenate the 1D array accordingly to achieve the desired shift.
Transform back to 2D Grid: Finally, map the shifted 1D list back to the original 2D grid layout.
This C solution first calculates the equivalent shift for the 1D representation of the grid. The nested loop traverses each element in the current 2D grid and calculates its new position in the shifted grid using the offset calculated with the modulo operation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) since we access each grid element once.
Space Complexity: O(m * n) needed for the result grid storage.
Calculate Direct Position Mapping: Instead of flattening, calculate the direct position mapping for shifted elements. This avoids the extra space used by intermediate lists.
Perform Element-wise Placement: Iterate through elements and directly place them in their new calculated positions.
The C version for direct mapping ensures each element’s target location is computed directly, with careful attention to index wrap-around using modulus.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n).
Space Complexity: O(m * n) for the shifted result.
| Approach | Complexity |
|---|---|
| Approach 1: 1D Array Transformation | Time Complexity: O(m * n) since we access each grid element once. |
| Approach 2: In-Place Simulation | Time Complexity: O(m * n). |
Shift 2D Grid - Leetcode 1260 - Python • NeetCode • 21,910 views views
Watch 9 more video solutions →Practice Shift 2D Grid with our built-in code editor and test cases.
Practice on FleetCode