Skip to content

1260. Shift 2D Grid

SourceWeekly Contest 163 Q1DifficultyEasyRating1337

Description

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:

  • Element at grid[i][j] moves to grid[i][j + 1].
  • Element at grid[i][n - 1] moves to grid[i + 1][0].
  • Element at 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.length
  • n == grid[i].length
  • 1 <= m <= 50
  • 1 <= n <= 50
  • -1000 <= grid[i][j] <= 1000
  • 0 <= k <= 100

Solutions

Solution 1: Flattening the 2D Array

Thinking

Each move takes the last cell to the front and shifts the rest, i.e. a right rotation of the row-major flattening by \(k\). \(m,n \le 50\), so we compute each element's final index instead of rotating \(k\) times.

The flat index \(i\cdot n+j\) plus \(k\) modulo \(mn\) converts back to a row and column in a new matrix. One pass finishes the map.

According to the problem description, if we flatten the 2D array into a 1D array, then each shift operation is to move the elements in the array one position to the right, with the last element moving to the first position of the array.

Therefore, we can flatten the 2D array into a 1D array, then calculate the final position \(idx = (x, y)\) of each element, and update the answer array ans[x][y] = grid[i][j].

The time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns in the grid array, respectively. We need to traverse the grid array once to calculate the final position of each element. Ignoring the space consumption of the answer array, the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        ans = [[0] * n for _ in range(m)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                x, y = divmod((i * n + j + k) % (m * n), n)
                ans[x][y] = v
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; ++j) {
                row.add(0);
            }
            ans.add(row);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int idx = (i * n + j + k) % (m * n);
                int x = idx / n, y = idx % n;
                ans.get(x).set(y, grid[i][j]);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int idx = (i * n + j + k) % (m * n);
                int x = idx / n, y = idx % n;
                ans[x][y] = grid[i][j];
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func shiftGrid(grid [][]int, k int) [][]int {
    m, n := len(grid), len(grid[0])
    ans := make([][]int, m)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            idx := (i*n + j + k) % (m * n)
            x, y := idx/n, idx%n
            ans[x][y] = grid[i][j]
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function shiftGrid(grid: number[][], k: number): number[][] {
    const [m, n] = [grid.length, grid[0].length];
    const ans: number[][] = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            const idx = (i * n + j + k) % (m * n);
            const [x, y] = [Math.floor(idx / n), idx % n];
            ans[x][y] = grid[i][j];
        }
    }
    return ans;
}

Comments