Shift 2D Grid — Solution in Python, Java & C++
Shift 2D Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and matrix.
Shift 2D Grid is an easy coding problem on arrays, matrix and simulation, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix, Simulation
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a 2-D grid of size m × n and an integer k, shift the grid k times.
One shift moves every element one column to the right; an element at the end of a row moves to the start of the next row, and the element at the bottom-right corner moves to the top-left. Return the grid after k shifts.
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 = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Explanation: A full cycle returns the grid unchanged.
Example 3
Input: grid = [[1,2],[3,4]], k = 2
Output: [[3,4],[1,2]]
Constraints
1 <= grid.length, grid[i].length <= 8-1000 <= grid[i][j] <= 10000 <= k <= 100
Hints for Shift 2D Grid
Hint 1
Reading the grid row by row makes it a flat list, and the shift is a rotation of that list.
Hint 2
Reduce
kmodulom × nfirst — anything more is a whole number of cycles.Hint 3
The element landing at flat position
icame from(i - k) mod (m·n).
How to solve Shift 2D Grid
Read the grid row-major as a flat list; a shift is a rotation of that list by k mod (m·n).
Approach
- Compute
shift = k % (m · n)and flatten the grid. - Fill the output so that flat position
iholdsflat[(i - shift) mod (m·n)].
Why it works
The shift rule (end of a row wraps to the next row, bottom-right wraps to top-left) is precisely a cyclic rotation of the row-major order.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Reduce
kfirst —kcan be much larger than the grid.
Reference solution
Python
def shiftGrid(grid, k: int):
m, n = len(grid), len(grid[0])
total = m * n
shift = k % total
flat = [v for row in grid for v in row]
return [[flat[(r * n + c - shift) % total] for c in range(n)] for r in range(m)]Java
public static int[][] shiftGrid(int[][] grid, int k) {
int m = grid.length, n = grid[0].length, total = m * n;
int shift = k % total;
int[] flat = new int[total];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) flat[r * n + c] = grid[r][c];
}
int[][] out = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
out[r][c] = flat[((r * n + c) - shift + total) % total];
}
}
return out;
}C++
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int m = (int) grid.size(), n = (int) grid[0].size(), total = m * n;
int shift = k % total;
vector<int> flat(total, 0);
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) flat[r * n + c] = grid[r][c];
}
vector<vector<int>> out(m, vector<int>(n, 0));
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
out[r][c] = flat[((r * n + c) - shift + total) % total];
}
}
return out;
}JavaScript
var shiftGrid = function(grid, k) {
const m = grid.length, n = grid[0].length, total = m * n;
const shift = k % total;
const flat = [];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) flat.push(grid[r][c]);
}
const out = [];
for (let r = 0; r < m; r++) {
const row = [];
for (let c = 0; c < n; c++) {
const idx = ((r * n + c) - shift + total) % total;
row.push(flat[idx]);
}
out.push(row);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal