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.
1#include <vector>
2using namespace std;
3
4vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
5 int m = grid.size(), n = grid[0].size();
6 int total = m * n;
7 k = k % total;
8 vector<vector<int>> result(m, vector<int>(n));
9 for (int i = 0; i < total; i++) {
10 int srcX = i / n, srcY = i % n;
11 int destX = (i + k) / n % m, destY = (i + k) % n;
12 result[destX][destY] = grid[srcX][srcY];
13 }
14 return result;
15}In this C++ solution, we calculate the total number of movements into its equivalent position in the 1D array perspective, adjusting it within the bounds using modulo arithmetic.
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.
1
The C version for direct mapping ensures each element’s target location is computed directly, with careful attention to index wrap-around using modulus.