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.
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public List<List<Integer>> shiftGrid(int[][] grid, int k) {
6 int m = grid.length, n = grid[0].length;
7 int total = m * n;
8 k = k % total;
9 List<List<Integer>> result = new ArrayList<>();
10 for(int i = 0; i < m; i++) {
11 result.add(new ArrayList<Integer>());
12 for(int j = 0; j < n; j++) {
13 int index1D = ((i * n + j) - k + total) % total;
14 int destRow = index1D / n;
15 int destCol = index1D % n;
16 result.get(destRow).add(grid[i][j]);
17 }
18 }
19 return result;
20 }
21}The Java solution utilizes nested ArrayLists to reconstruct the shifted grid. It performs the same position calculation as the other languages but uses list operations native to Java.
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.
1Python’s solution uses nested loops and directly places shifted values according to the calculated linear indices back into their new two-dimensional spots.