Shift 2D Grid Solution in C++/Java/Python/JS
Shift 2D Grid Problem 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 k shift operations.
Examples:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Explanation: Last element 9 moves to front; everything else shifts right.
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Explanation: 9 shifts is a full cycle; grid returns to original.
Constraints:
m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
Brute Force Approach
Imagine you have a 2D grid — kind of like a spreadsheet or a table. Each row has some numbers, and all the rows stack on top of each other to form a rectangle. You’re told to shift this grid k times, and the shifting follows a very specific pattern.
Now you might be asking, “What do you mean by shift?”
Well, here’s how the shift works:
- Each element moves one place to the right.
- But if something is at the end of a row, it wraps around and goes to the beginning of the next row.
- And if it’s the last element in the whole grid — bottom-right corner — it wraps back to the top-left corner.
Sounds a bit like rotating things, right? But instead of rotating rows or columns, we’re pushing elements forward, one step at a time, like a conveyor belt that wraps around.
Let’s say we start with this grid:
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Now, what happens if we shift this grid once?
Let’s follow the rules:
- The number 9, which is at the end, wraps around and moves to the front.
- Everything else moves one step to the right.
So we get:
[[9, 1, 2],
[3, 4, 5],
[6, 7, 8]]
Cool, right? We just “pushed” every element forward and looped the last one back to the start.
When you first read the problem, a very natural idea comes to mind:
“Why don’t we just do this process k times, shifting the grid one step at a time?”
That’s the essence of the brute force approach — no shortcuts, no optimization, just repeat the operation exactly as described until we’ve done it k times.
Yes, it might be slow for large values of k, but it’s super easy to understand and works perfectly fine for small values — which is often where you start when learning.
Let’s think about what’s happening during one shift:
- For every element at position (i, j), we need to figure out where it goes.
- Normally, it just goes to (i, j + 1) — one column to the right.
- But what if it’s already at the last column?
- Then it moves to the start of the next row: (i + 1, 0)
- And if it’s the last row too? We wrap it all the way back to the top: (0, 0)
So we’re moving rightward — and wrapping across rows and then to the top — over and over again.
This is why for each shift, we can go through every element, figure out its new position (based on those rules), and place it there in a temporary grid. After we’ve done this for one complete pass, we update the original grid and repeat this process k times.
This method is very visual, very direct, and very beginner-friendly. You’re not jumping into anything complex like index math or modulo tricks — you’re just simulating what the problem asks, literally:
"Take everything, push it one space forward, wrap when needed, and repeat."
It's almost like you’re animating the movement of numbers in your mind — “This one moves here, that one moves there…”
It’s clean, intuitive, and helps you internalize how the grid transforms over time.
Let’s say we start with:
[[1, 2],
[3, 4]]
After one shift →
[[4, 1],
[2, 3]]
After another shift →
[[3, 4],
[1, 2]]
After another →
[[2, 3],
[4, 1]]
And we can keep going like that.
You can literally imagine the values moving like a snake around the grid — sliding from one cell to the next, always wrapping around.
Let's understand with an example:
Shift 2D Grid Example:
Input:
grid = [[1,2,3],
[4,5,6],
[7,8,9]],
k = 2
Shift 1:
Step-by-step movement:
- Shift every element one position to the right.
- Wrap around last elements to the next row or top-left if needed.
Result after 1 shift:
[[9, 1, 2],
[3, 4, 5],
[6, 7, 8]]
Shift 2:
Now we shift the above result again by 1.
Result after 2 shifts:
[[8, 9, 1],
[2, 3, 4],
[5, 6, 7]]
Final Output after k = 2 shifts:
[[8, 9, 1],
[2, 3, 4],
[5, 6, 7]]
Steps to Implement the Solution:
- Get Grid Dimensions
- Let m = number of rows
- Let n = number of columns
- Repeat the Shift Operation k Times:
- Loop from 0 to k - 1
- Inside Each Shift:
- Create a new temporary grid of same size m x n
- For every element at position (i, j) in the original grid:
- Move it to position:
- (i, j + 1) normally
- If j + 1 == n, wrap to (i + 1, 0)
- If also at last row, wrap to (0, 0)
- After Each Shift:
- Replace original grid with updated temporary grid
- After All k Shifts:
- Return the updated grid
Shift 2D Grid Solution
Code Implementation / Shift 2D Grid leetcode Solution
1. Shift 2D Grid solution in C++ Try on Compiler
class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
// Number of rows
int m = grid.size();
// Number of columns
int n = grid[0].size();
// Repeat the shift operation k times
for (int shift = 0; shift < k; ++shift) {
// Create a new grid to store the result after one shift
vector<vector<int>> temp(m, vector<int>(n));
// Traverse each cell to shift its value
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// Calculate new position after one shift
int new_i = i;
int new_j = j + 1;
// If it goes past the last column, move to next row
if (new_j == n) {
new_j = 0;
// Wrap around to 0 if at last row
new_i = (i + 1) % m;
}
// Place the current value into its new position
temp[new_i][new_j] = grid[i][j];
}
}
// Update the original grid with the shifted result
grid = temp;
}
return grid;
}
};2. Shift 2D Grid solution in Java Try on Compiler
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
// Number of rows
int m = grid.length;
// Number of columns
int n = grid[0].length;
for (int shift = 0; shift < k; shift++) {
// Temporary grid for storing the result after one shift
int[][] temp = new int[m][n];
// Traverse each cell to shift its value
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Calculate new position
int new_i = i;
int new_j = j + 1;
// If column goes out of bounds, wrap to next row
if (new_j == n) {
new_j = 0;
// Wrap around to first row if needed
new_i = (i + 1) % m;
}
temp[new_i][new_j] = grid[i][j];
}
}
// Update the original grid with shifted version
grid = temp;
}
// Convert 2D array to List<List<Integer>> for return type
List<List<Integer>> result = new ArrayList<>();
for (int[] row : grid) {
List<Integer> list = new ArrayList<>();
for (int val : row) {
list.add(val);
}
result.add(list);
}
return result;
}
}
3. Shift 2D Grid solution in Python Try on Compiler
class Solution:
def shiftGrid(self, grid, k):
# Number of rows
m = len(grid)
# Number of columns
n = len(grid[0])
for shift in range(k):
# Temporary grid for one shift
temp = [[0] * n for _ in range(m)]
# Traverse each cell and shift it
for i in range(m):
for j in range(n):
# Compute new position
new_i = i
new_j = j + 1
# If column goes out of bounds
if new_j == n:
new_j = 0
new_i = (i + 1) % m # Wrap to first row if needed
temp[new_i][new_j] = grid[i][j]
# Update original grid
grid = temp
return grid
4. Shift 2D Grid solution in Javascript Try on Compiler
var shiftGrid = function(grid, k) {
const m = grid.length; // Number of rows
const n = grid[0].length; // Number of columns
for (let shift = 0; shift < k; shift++) {
// Temporary grid for one shift
const temp = Array.from({ length: m }, () => new Array(n));
// Traverse each cell to shift it
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// Compute new position
let new_i = i;
let new_j = j + 1;
// If column overflows
if (new_j === n) {
new_j = 0;
new_i = (i + 1) % m; // Wrap to first row if at last
}
temp[new_i][new_j] = grid[i][j];
}
}
// Update grid with shifted version
grid = temp;
}
return grid;
};
Shift 2D Grid Complexity Analysis
Time Complexity: O(k × m × n)
Let:
- m = number of rows
- n = number of columns
- k = number of shifts
The outer loop runs k times.
Inside that, we do a full traversal of the entire grid (nested for loops over m and n). Each shift operation involves visiting every element in the grid once.
There are m × n elements in the grid. So, for each shift, we do m × n operations.
And we're doing this k times. Repeating this k times gives k × m × n total operations.
So the total time complexity is: O(k × m × n)
Space Complexity: O(m × n)
- Auxiliary Space Complexity: O(1)
The extra space used in the algorithm — like: loop counters i, j, shift, new_i, new_j
— are all primitive integer variables.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(m × n)
We are working with a 2D input grid of size m × n, which is provided to us. However, during each shift, we also create a temporary grid temp of the same size to hold the intermediate result of one shift.So while we don’t use extra space that grows beyond m × n, we do use an additional grid of the same size.
Therefore, the total space used in the process is:
- One for the input grid → O(m × n)
- One temporary grid temp → O(m × n)
But since we're not stacking these up, it's still considered linear in terms of the number of elements.
So, the total space complexity is O(m × n) due to the input grid.
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(m × n × k), where:
- m is the number of rows in the grid
- n is the number of columns
- k is the number of times we perform the shift operation
Given the constraints:
- 1 ≤ m ≤ 50
- 1 ≤ n ≤ 50
- 0 ≤ k ≤ 100
In the worst-case scenario, this algorithm would perform up to:
O(50 × 50 × 100) = 250,000 operations
Even though this is a brute-force approach, the absolute number of operations — around a quarter million — is still well within the acceptable limits for most online judges, including LeetCode, which generally allows up to 10⁶ (1 million) operations per test case.
So, although this solution isn’t the most optimized in terms of time complexity, it performs efficiently in practice for the given constraints and is simple and easy to understand, making it a solid starting point.
How to optimize it?
So earlier, we solved this problem using a brute-force approach. What did we do there?
We performed the shift operation one step at a time, and we repeated it k times. In each shift, we would take every element in the grid and move it one position forward — rightward in the same row, and if it reached the end, we wrapped it to the beginning of the next row. If it was at the last element of the last row, we wrapped it all the way back to the top-left of the grid.
This approach was straightforward and easy to understand. But, as you probably noticed, it had a small drawback — we had to repeat the entire grid traversal k times, which means the time complexity became O(m × n × k). While that's fine for small values of k, it's not the most efficient way to handle this problem, especially when k gets larger.
So now let’s step into an optimized way of thinking.
Shift 2D Grid Algorithm
Instead of shifting the entire grid one step at a time, why not jump directly to the final position of each element after k total shifts?
Let’s try to see what happens when you shift an element forward — it moves to the next position in row-major order. And if you shift it k times, it will move k steps forward in this flattened, one-dimensional view of the grid.
Imagine flattening the grid into a 1D array. For example, let’s take:
grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
If we flatten this, we get:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Now if we want to shift this by k = 1, the array becomes:
[9, 1, 2, 3, 4, 5, 6, 7, 8]
And for k = 2, it becomes:
[8, 9, 1, 2, 3, 4, 5, 6, 7]
You see how we’re just rotating this array to the right k times?
But here’s the trick — we don’t actually need to flatten the grid into a 1D array, do the rotation, and then convert it back. We can just map the 2D position directly.
Every cell grid[i][j] has a unique 1D index in the flattened array:
index = i × m + j (where m = number of columns)
And after shifting k times, its new 1D position will be:
newIndex = (index + k) % (m × n)
Once we get this new index, we can convert it back to 2D coordinates:
- new_i = newIndex / m (row)
- new_j = newIndex % m (column)
But instead of literally computing the 1D index and converting back, the code cleverly does this in-place using math inside the nested loops:
- For every grid[i][j], it calculates the new column as:
newJ = (j + k) % m - But wait — just adding k to the column may cross over to the next row. So we figure out how many times we cross a row using:
(j + k) / m - We then add that number to the row i to get the new row:
newI = (i + (j + k)/m) % n
That’s it! It’s like shifting elements along a 1D tape, but storing them back into the 2D format directly. No need to manually rotate or simulate every single shift.
Let’s say:
grid = [[1, 2, 3], [4, 5, 6]] and k = 2
This grid is 2 rows × 3 columns.
If we flatten this:
[1, 2, 3, 4, 5, 6]
After shifting 2 times:
[5, 6, 1, 2, 3, 4]
Back to 2D:
[[5, 6, 1], [2, 3, 4]]
And the optimized code directly maps each element to its new location using modular arithmetic — super efficient and elegant!
So this approach teaches an important lesson: thinking in terms of 1D mapping can often simplify problems on 2D grids. Instead of physically rotating the grid step by step, you’re using math to jump directly to the destination.
Let us understand this with a video,
Shift 2D Grid-Optimal-Approach-Animation
Let's understand with an example:
Shift 2D Grid Example:
Input:
grid = [[3,8,1,9], [19,7,2,5], [4,6,11,10], [12,0,21,13]]
k = 4
There are 4 rows (n = 4) and 4 columns (m = 4) → total 16 elements
Flattened grid:
[3, 8, 1, 9, 19, 7, 2, 5, 4, 6, 11, 10, 12, 0, 21, 13]
After shifting 4 positions to the right, the array becomes:
[12, 0, 21, 13, 3, 8, 1, 9, 19, 7, 2, 5, 4, 6, 11, 10]
Chunk into rows of 4:
[[12, 0, 21, 13],
[3, 8, 1, 9],
[19, 7, 2, 5],
[4, 6, 11, 10]]
Final Output:
[[12, 0, 21, 13], [3, 8, 1, 9], [19, 7, 2, 5], [4, 6, 11, 10]]
This is the grid after shifting everything 4 steps forward, with wraparound.
How to code it up:
Get grid dimensions:
- Let n be the number of rows.
- Let m be the number of columns.
- Create a result grid (ans) of size n × m initialized with 0.
Loop over each cell (i, j) in the original grid.
- Compute the new column index:
- newJ = (j + k) % m
→ this shifts the element rightward within its row.
- newJ = (j + k) % m
- Compute the new row index:
- newI = (i + (j + k) / m) % n
→ this moves the element to the correct row if it overflows the column.
- newI = (i + (j + k) / m) % n
Assign the value:
- Place grid[i][j] in ans[newI][newJ].
- Return the ans grid.
Shift 2D Grid Solution
Code Implementation / Shift 2D Grid leetcode Solution
1. Shift 2D Grid solution in C++ Try on Compiler
class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
// Get the number of rows
int n = grid.size();
// Get the number of columns
int m = grid[0].size();
// Create a new grid to store the result after shifting
vector<vector<int>> ans(n, vector<int>(m));
// Traverse each element of the original grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Calculate the new column index after k shifts
int newJ = (j + k) % m;
// Calculate how many rows down the element shifts
int newI = (i + (j + k) / m) % n;
// Place the current element at its new position in the result grid
ans[newI][newJ] = grid[i][j];
}
}
// Return the shifted grid
return ans;
}
};
2. Shift 2D Grid solution in Java Try on Compiler
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
// Get the number of rows
int n = grid.length;
// Get the number of columns
int m = grid[0].length;
// Create a result list of lists
List<List<Integer>> ans = new ArrayList<>();
// Initialize an empty 2D array for temporary result
int[][] temp = new int[n][m];
// Traverse each element of the original grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Calculate the new column index after k shifts
int newJ = (j + k) % m;
// Calculate how many rows down the element shifts
int newI = (i + (j + k) / m) % n;
// Place the current element at its new position
temp[newI][newJ] = grid[i][j];
}
}
// Convert the 2D array into a List of Lists
for (int[] row : temp) {
List<Integer> newRow = new ArrayList<>();
for (int val : row) {
newRow.add(val);
}
ans.add(newRow);
}
// Return the shifted grid
return ans;
}
}
3. Shift 2D Grid solution in Python Try on Compiler
class Solution:
def shiftGrid(self, grid, k):
# Get the number of rows
n = len(grid)
# Get the number of columns
m = len(grid[0])
# Create a result grid of same size with 0s
ans = [[0 for _ in range(m)] for _ in range(n)]
# Traverse each cell in the original grid
for i in range(n):
for j in range(m):
# Calculate the new column index after shift
new_j = (j + k) % m
# Calculate the new row index after overflow
new_i = (i + (j + k) // m) % n
# Place the value in its new position
ans[new_i][new_j] = grid[i][j]
# Return the shifted grid
return ans
4. Shift 2D Grid solution in Javascript Try on Compiler
var shiftGrid = function(grid, k) {
// Get the number of rows
let n = grid.length;
// Get the number of columns
let m = grid[0].length;
// Create a new grid filled with 0s
let ans = Array.from({ length: n }, () => Array(m).fill(0));
// Traverse each element in the grid
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// Calculate the new column index after shift
let newJ = (j + k) % m;
// Calculate the new row index after column overflow
let newI = (i + Math.floor((j + k) / m)) % n;
// Place the value in the new position
ans[newI][newJ] = grid[i][j];
}
}
// Return the shifted grid
return ans;
};
Shift 2D Grid Complexity Analysis
Time Complexity: O(n × m)
- We loop over every element in the 2D grid once using two nested loops:
- The outer loop runs for n rows.
- The inner loop runs for m columns.
- For each of these n × m elements, we compute the new position in constant time (just some arithmetic).
- So, the total operations = n × m.
So, the overall time complexity is O(n × m).
Space Complexity: O(n × m)
- Auxiliary Space Complexity: O(n × m)
We create a new 2D result grid (ans) of the same size as the input to store the final shifted values.
This result grid takes O(n × m) space. - Total Space Complexity: O(n × m)
The total space complexity is O(n × m) because we construct a new grid of the same size as the input to hold the shifted values. No additional space beyond that is used significantly.
Therefore, the total space complexity is O(n × m).
Similar Problems
In programming, manipulating an array is a fundamental task that often requires performing various operations, such as shifting or rotating elements. This is especially common when working with matrices, which are essentially 2D arrays. Matrix manipulation can simulate real-world scenarios where data needs to be transformed or adjusted repeatedly. These simulations help solve complex problems efficiently, whether it's through simple operations or more advanced techniques that optimize performance.
Now that we have successfully tackled this problem, let's try similar problems.
Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.
A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.
The following proccess happens k times:
Even-indexed rows (0, 2, 4, ...) are cyclically shifted to the left.
Odd-indexed rows (1, 3, 5, ...) are cyclically shifted to the right.
Return true if the final modified matrix after k steps is identical to the original matrix, and false otherwise.