Shift 2D Grid solution and explanation
9 more videos on this problem
Shift 2D Grid - Leetcode 1260 - PythonNeetCode · 10:18 · 24K views
Rotate Array | Shift 2D Grid | Smart Approach | Leetcode 189 | Leetcode 1260 | codestorywithMIKcodestorywithMIK · 20:18 · 5K views
LeetCode 1260: Shift 2D Grid - Interview Prep Ep 12Fisher Coder · 27:51 · 2K views
Daily Leetcode #741: Apr 11, 2022 - 1260. Shift 2D GridProgramming Live with Larry · 5:11 · 2K views
Shift 2D Grid | Leetcode 1260 | Array | MatrixNitesh Nanda · 10:50 · 1K views
Leetcode 1260: Shift 2D GridAlgorithms Casts · 22:55 · 695 views
LeetCode 1260 Solution | Shift 2D Grid | Easy 1D Array Flattening Trick | PythonStatLearn Tech · 12:33 · 433 views
Leetcode 1260: Shift 2D GridAlgorithms Casts · 17:34 · 401 views
Shift 2D Grid | LeetCode 1260 - Pythonimpoldev · 3:50 · 334 views
Daily Leetcode #2302: Jul 20, 2026 - 1260. Shift 2D GridProgramming Live with Larry · 5:54 · 316 views
The problem
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 togrid[i][j + 1]. - Element at
grid[i][n - 1]moves togrid[i + 1][0]. - Element at
grid[m - 1][n - 1]moves togrid[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.lengthn == grid[i].length1 <= m <= 501 <= n <= 50-1000 <= grid[i][j] <= 10000 <= k <= 100
Approach overview
Problem Overview: You receive an m x n grid and an integer k. Each shift moves every element one step to the right, the last element of a row becomes the first of the next row, and the bottom‑right element wraps to the top‑left. After performing the shift operation k times, return the final grid configuration.
Approach 1: 1D Array Transformation (Time: O(mn), Space: O(mn))
The key observation is that the grid behaves like a single circular array of length m * n. Flatten the array/matrix indices into a 1D index using index = row * n + col. After k shifts, the element moves to (index + k) % (m * n). Convert that new index back to 2D coordinates using division and modulo.
This avoids performing the shift operation repeatedly. Instead, iterate through the grid once, compute the destination index, and place the element in the result grid. The approach is clean and deterministic: one pass to map positions and rebuild the grid. Time complexity stays O(mn) regardless of k, and space complexity is O(mn) for the new grid.
Approach 2: In-Place Simulation (Time: O(kmn), Space: O(1))
This method directly simulates the shift operation exactly as described. For each shift, traverse the grid from the bottom‑right corner while carrying the previous value that should move into the current cell. The value from the last cell wraps around to the first position.
Although you can reduce unnecessary work by computing k = k % (m * n), each shift still requires scanning the entire matrix. That results in O(kmn) time in the worst case. The advantage is constant extra memory because the transformation happens directly inside the grid. This technique mirrors the problem’s simulation behavior and is easy to reason about step by step.
Recommended for interviews: The 1D index transformation is the expected solution. It shows you recognize that a 2D grid can be treated as a circular linear structure and optimized using modular arithmetic. Interviewers often accept the simulation approach first because it demonstrates understanding of the shift rules, but the index‑mapping solution proves stronger algorithmic thinking with optimal O(mn) time.
Approach 1: Approach 1: 1D Array Transformation
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.
def shiftGrid(grid, k):
m, n = len(grid), len(grid[0])
total = m * n
k = k % total
flat_list = [grid[i][j] for i in range(m) for j in range(n)]
shifted_list = flat_list[-k:] + flat_list[:-k]
return [[shifted_list[i * n + j] for j in range(n)] for i in range(m)]import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int total = m * n;
k = k % total;
List<List<Integer>> result = new ArrayList<>();
for(int i = 0; i < m; i++) {
result.add(new ArrayList<Integer>());
for(int j = 0; j < n; j++) {
int index1D = ((i * n + j) - k + total) % total;
int destRow = index1D / n;
int destCol = index1D % n;
result.get(destRow).add(grid[i][j]);
}
}
return result;
}
}#include <vector>
using namespace std;
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
int total = m * n;
k = k % total;
vector<vector<int>> result(m, vector<int>(n));
for (int i = 0; i < total; i++) {
int srcX = i / n, srcY = i % n;
int destX = (i + k) / n % m, destY = (i + k) % n;
result[destX][destY] = grid[srcX][srcY];
}
return result;
}var shiftGrid = function(grid, k) {
const m = grid.length, n = grid[0].length;
const total = m * n;
k = k % total;
const flatGrid = grid.flat();
const shiftedGrid = [...flatGrid.slice(-k), ...flatGrid.slice(0, -k)];
const result = [];
for (let row = 0; row < m; row++) {
result.push(shiftedGrid.slice(row * n, row * n + n));
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int** shiftGrid(int** grid, int gridSize, int* gridColSize, int k, int* returnSize, int** returnColumnSizes) {
int m = gridSize, n = *gridColSize;
int total = m * n;
*returnSize = m;
int** result = malloc(m * sizeof(int*));
*returnColumnSizes = malloc(m * sizeof(int));
for (int i = 0; i < m; i++) {
result[i] = malloc(n * sizeof(int));
(*returnColumnSizes)[i] = n;
}
k = k % total;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int index1D = ((i * n + j) + total - k) % total;
int destRow = index1D / n;
int destCol = index1D % n;
result[destRow][destCol] = grid[i][j];
}
}
return result;
}public class Solution {
public IList<IList<int>> ShiftGrid(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int total = m * n;
k = k % total;
int[] flatGrid = new int[total];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
flatGrid[i * n + j] = grid[i][j];
}
}
int[] shiftedGrid = new int[total];
Array.Copy(flatGrid, total - k, shiftedGrid, 0, k);
Array.Copy(flatGrid, 0, shiftedGrid, k, total - k);
IList<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < m; i++) {
List<int> row = new List<int>();
for (int j = 0; j < n; j++) {
row.Add(shiftedGrid[i * n + j]);
}
result.Add(row);
}
return result;
}
}This Python solution leverages list slicing to rotate the 1D representation of the grid elements efficiently, then reformats them back to a 2D list.
Time Complexity: O(m * n).
Space Complexity: O(m * n).
Approach 2: Approach 2: In-Place Simulation
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.
def shiftGrid(grid, k):
m, n = len(grid), len(grid[0])
total = m * n
result = [[0] * n for _ in range(m)]
k = k % total
for i in range(m):
for j in range(n):
newIdx = (i * n + j + k) % total
newRow, newCol = newIdx // n, newIdx % n
result[newRow][newCol] = grid[i][j]
return resultimport java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int total = m * n;
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < m; i++) { result.add(new ArrayList<>(Arrays.asList(new Integer[n]))); }
k = k % total;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int newIdx = ((i * n + j) + k) % total;
int newRow = newIdx / n;
int newCol = newIdx % n;
result.get(newRow).set(newCol, grid[i][j]);
}
}
return result;
}
}#include <vector>
using namespace std;
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
int total = m * n;
vector<vector<int>> result(m, vector<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;
}var shiftGrid = function(grid, k) {
const m = grid.length, n = grid[0].length;
const total = m * n;
const result = Array.from({ length: m }, () => new Array(n).fill(0));
k = k % total;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let newIdx = (i * n + j + k) % total;
let newRow = Math.floor(newIdx / n);
let newCol = newIdx % n;
result[newRow][newCol] = grid[i][j];
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int** shiftGrid(int** grid, int gridSize, int* gridColSize, int k, int* returnSize, int** returnColumnSizes) {
int m = gridSize, n = *gridColSize;
int total = m * n;
*returnSize = m;
int** result = malloc(m * sizeof(int*));
*returnColumnSizes = malloc(m * sizeof(int));
for (int i = 0; i < m; i++) {
result[i] = malloc(n * sizeof(int));
(*returnColumnSizes)[i] = n;
}
k = k % total;
for (int r = 0; r < total; r++) {
int oldPos = (r - k + total) % total;
int srcR = oldPos / n, srcC = oldPos % n;
int destR = r / n, destC = r % n;
result[destR][destC] = grid[srcR][srcC];
}
return result;
}using System;
using 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;
}
}Python’s solution uses nested loops and directly places shifted values according to the calculated linear indices back into their new two-dimensional spots.
Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the new 2D array.
Approach 3: Flattening the 2D Array
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).
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: 1D Array Transformation | Time Complexity: O(m * n). |
| Approach 2: In-Place Simulation | Time Complexity: O(m * n). |
| Flattening the 2D Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| 1D Array Transformation | O(mn) | O(mn) | Best general solution. Converts the grid to a circular 1D index and computes final positions directly. |
| In-Place Simulation | O(kmn) | O(1) | Useful when minimizing extra memory or when demonstrating the shift mechanics step by step. |
Frequently asked questions
Is Shift 2D Grid easy or hard?
Shift 2D Grid is classified as an Easy problem on LeetCode with an acceptance rate around 68%. The main challenge is recognizing that the matrix can be treated as a circular array to avoid repeated simulation.
How to solve Shift 2D Grid in O(n)?
Flatten the m x n grid into a conceptual 1D array of length m*n. For each element, compute its new index after k shifts using modular arithmetic: (index + k) % (m*n). Convert the resulting index back to row and column positions to rebuild the grid in O(mn) time.
What is the best approach for Shift 2D Grid?
The most efficient approach treats the grid as a circular 1D array. Convert each cell (row, col) into a linear index, shift it using (index + k) % (m * n), and map it back to 2D coordinates. This completes the transformation in O(mn) time with O(mn) extra space and avoids repeatedly simulating shifts.
What data structure is used in Shift 2D Grid?
The problem primarily uses arrays and matrices. The optimal solution relies on index arithmetic to treat the matrix as a circular array, while the simulation approach updates elements directly inside the matrix.
What is the time complexity of Shift 2D Grid?
The optimal solution runs in O(mn) time where m and n are the grid dimensions. Each element is processed once to compute its final position after k shifts. A direct simulation approach takes O(kmn) time because the entire grid is shifted k times.
Shift 2D Grid Python or Java solution approach?
Both Python and Java implementations typically use the index‑mapping technique. Iterate through the grid, compute the flattened index, shift it using modulo arithmetic, and place the value in the computed row and column of the result grid.
Is Shift 2D Grid asked at Google, Amazon, or Meta?
Shift 2D Grid is a common entry‑level matrix manipulation problem used in coding interviews and practice sets. Variations of grid rotation, circular array shifts, and matrix index mapping appear in interviews at companies like Amazon and Google.