LeetCode 1260: Shift 2D Grid (Linear Index Rotation)
LeetCode 1260MatrixIndex MappingToday we solve LeetCode 1260 - Shift 2D Grid.
Source: https://leetcode.com/problems/shift-2d-grid/
English
Problem Summary
Given an m x n grid and an integer k, shift the grid right by one cell repeatedly for k times. The last element of each row moves to the first position of the next row, and the last element of the whole grid moves to grid[0][0].
Key Insight
Treat the matrix as a circular 1D array of length m * n. A cell (r, c) maps to linear index idx = r * n + c. After shifting right by k, it moves to (idx + k) % (m * n). Convert back by division/modulo.
Algorithm
- Let rows = grid.length, cols = grid[0].length, total = rows * cols.
- Reduce shifts with k %= total.
- Create result matrix ans[rows][cols].
- For each original cell (r, c): compute from = r * cols + c, to = (from + k) % total, then place value into ans[to / cols][to % cols].
- Return ans.
Complexity Analysis
Time: O(mn).
Space: O(mn) for the output matrix.
Common Pitfalls
- Forgetting to reduce k by total, causing unnecessary work.
- Incorrect row/column recovery when converting from linear index.
- Trying to shift step-by-step (O(kmn)) instead of direct mapping.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int rows = grid.length;
int cols = grid[0].length;
int total = rows * cols;
k %= total;
int[][] shifted = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int from = r * cols + c;
int to = (from + k) % total;
shifted[to / cols][to % cols] = grid[r][c];
}
}
List<List<Integer>> ans = new ArrayList<>();
for (int r = 0; r < rows; r++) {
List<Integer> row = new ArrayList<>();
for (int c = 0; c < cols; c++) {
row.add(shifted[r][c]);
}
ans.add(row);
}
return ans;
}
}func shiftGrid(grid [][]int, k int) [][]int {
rows := len(grid)
cols := len(grid[0])
total := rows * cols
k %= total
shifted := make([][]int, rows)
for r := 0; r < rows; r++ {
shifted[r] = make([]int, cols)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
from := r*cols + c
to := (from + k) % total
shifted[to/cols][to%cols] = grid[r][c]
}
}
return shifted
}class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int rows = grid.size();
int cols = grid[0].size();
int total = rows * cols;
k %= total;
vector<vector<int>> shifted(rows, vector<int>(cols));
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
int from = r * cols + c;
int to = (from + k) % total;
shifted[to / cols][to % cols] = grid[r][c];
}
}
return shifted;
}
};class Solution:
def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
rows, cols = len(grid), len(grid[0])
total = rows * cols
k %= total
shifted = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
from_idx = r * cols + c
to_idx = (from_idx + k) % total
shifted[to_idx // cols][to_idx % cols] = grid[r][c]
return shiftedvar shiftGrid = function(grid, k) {
const rows = grid.length;
const cols = grid[0].length;
const total = rows * cols;
k %= total;
const shifted = Array.from({ length: rows }, () => Array(cols).fill(0));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
const from = r * cols + c;
const to = (from + k) % total;
shifted[Math.floor(to / cols)][to % cols] = grid[r][c];
}
}
return shifted;
};中文
题目概述
给定一个 m x n 的网格和整数 k，将网格向右移动 k 次。每次移动时：每行最后一个元素移到下一行开头，整个网格最后一个元素移到 grid[0][0]。
核心思路
把二维网格看成长度为 m * n 的环形一维数组。坐标 (r, c) 映射到线性下标 idx = r * n + c。右移 k 次后，新下标为 (idx + k) % (m * n)，再通过除法和取模还原回二维坐标即可。
算法步骤
- 设 rows、cols、total = rows * cols。
- 先做 k %= total。
- 新建结果矩阵 ans。
- 遍历原矩阵每个单元：from = r * cols + c，to = (from + k) % total，把值写入 ans[to / cols][to % cols]。
- 返回 ans。
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(mn)（输出矩阵）。
常见陷阱
- 没有先对 k 取模，导致多余计算。
- 一维下标转二维坐标时行列计算写错。
- 逐次模拟右移，复杂度退化到 O(kmn)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int rows = grid.length;
int cols = grid[0].length;
int total = rows * cols;
k %= total;
int[][] shifted = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int from = r * cols + c;
int to = (from + k) % total;
shifted[to / cols][to % cols] = grid[r][c];
}
}
List<List<Integer>> ans = new ArrayList<>();
for (int r = 0; r < rows; r++) {
List<Integer> row = new ArrayList<>();
for (int c = 0; c < cols; c++) {
row.add(shifted[r][c]);
}
ans.add(row);
}
return ans;
}
}func shiftGrid(grid [][]int, k int) [][]int {
rows := len(grid)
cols := len(grid[0])
total := rows * cols
k %= total
shifted := make([][]int, rows)
for r := 0; r < rows; r++ {
shifted[r] = make([]int, cols)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
from := r*cols + c
to := (from + k) % total
shifted[to/cols][to%cols] = grid[r][c]
}
}
return shifted
}class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int rows = grid.size();
int cols = grid[0].size();
int total = rows * cols;
k %= total;
vector<vector<int>> shifted(rows, vector<int>(cols));
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
int from = r * cols + c;
int to = (from + k) % total;
shifted[to / cols][to % cols] = grid[r][c];
}
}
return shifted;
}
};class Solution:
def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
rows, cols = len(grid), len(grid[0])
total = rows * cols
k %= total
shifted = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
from_idx = r * cols + c
to_idx = (from_idx + k) % total
shifted[to_idx // cols][to_idx % cols] = grid[r][c]
return shiftedvar shiftGrid = function(grid, k) {
const rows = grid.length;
const cols = grid[0].length;
const total = rows * cols;
k %= total;
const shifted = Array.from({ length: rows }, () => Array(cols).fill(0));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
const from = r * cols + c;
const to = (from + k) % total;
shifted[Math.floor(to / cols)][to % cols] = grid[r][c];
}
}
return shifted;
};
Comments