Sponsored
Sponsored
Transform 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.
Time Complexity: O(m * n) since we access each grid element once.
Space Complexity: O(m * n) needed for the result grid storage.
1def shiftGrid(grid, k):
2 m, n = len(grid), len(grid[0])
3 total = m * n
4 k = k % total
5 flat_list = [grid[i][j] for i in range(m) for j in range(n)]
6 shifted_list = flat_list[-k:] + flat_list[:-k]
7 return [[shifted_list[i * n + j] for j in range(n)] for i in range(m)]This Python solution leverages list slicing to rotate the 1D representation of the grid elements efficiently, then reformats them back to a 2D list.
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.
Time Complexity: O(m * n).
Space Complexity: O(m * n) for the shifted result.
1using System.Collections.Generic;
public class Solution {
public IList<IList<int>> ShiftGrid(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int total = m * n;
var result = new List<IList<int>>(m);
for (int i = 0; i < m; i++) {
result.Add(new List<int>(new int[n]));
}
k = k % total;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int oldIdx = (i * n + j);
int newIdx = (oldIdx + k) % total;
result[newIdx / n][newIdx % n] = grid[i][j];
}
}
return result;
}
}C# handles index calculation and uses List for result storage, ensuring placement via direct index mapping in the output matrix.