Leetcode 1260. How To Shift Elements of a Matrix
Perform k shift operations on a 2D grid to return the updated grid.
Problem statement
You are given a 2D grid with dimension mxn and an integer k. Your task is to perform k shift operations on the grid.
In each shift operation:
- The element at
grid[i][j]moves togrid[i][j+1]. - The element at
grid[i][n-1]moves togrid[i+1][0]. - The element at
grid[m-1][n-1]moves togrid[0][0].
After performing k shift operations, return the updated 2D grid.
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
1 <= grid.length <= 50.1 <= grid[i].length <= 50.-1000 <= grid[i][j] <= 1000.0 <= k <= 100.
Solution: Convert a 2D array into a 1D one
You can convert the 2D grid into a 1D vector v to perform the shifting easier. One way of doing this is concatenating the rows of the matrix.
- If you shift the grid
k = i*Ntimes whereN = v.size()andiis any non-negative integer, you go back to the original grid; i.e. you did not shift it. - If you shift the grid
ktimes with0 < k < N, the first element of the result starts fromv[N-k]. - In general, the first element of the result starts from
v[N - k%N].
Example 1
For grid = [[1,2,3],[4,5,6],[7,8,9]]:
- It can be converted into a 1D vector
v = [1,2,3,4,5,6,7,8,9]of sizem*n = 9. - With
k = 1the shiftedgridnow starts fromv[9-1] = 9. - The final result is
grid = [[9,1,2][3,4,5][6,7,8]].
Code
#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
vector<int> v;
// store the 2D grid values into a 1D vector v
for (auto& r : grid) {
v.insert(v.end(), r.begin(), r.end());
}
const int N = v.size();
// perform the shifting
int p = N - k % N;
// number of rows
const int m = grid.size();
// number of columns
const int n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (p == N) {
p = 0;
}
// reconstruct the grid
grid[i][j] = v[p++];
}
}
return grid;
}
void printResult(const vector<vector<int>>& grid) {
cout << "[";
for (auto& r : grid) {
cout << "[";
for (int a: r) {
cout << a << ",";
}
cout << "]";
}
cout << "]\n";
}
int main() {
vector<vector<int>> grid</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">3</span><span class="p">},{</span><span class="mi">4</span><span class="p">,</span><span class="mi">5</span><span class="p">,</span><span class="mi">6</span><span class="p">},{</span><span class="mi">7</span><span class="p">,</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">;
auto result = shiftGrid(grid, 1);
printResult(result);
grid = </span><span class="mi">3</span><span class="p">,</span><span class="mi">8</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">9</span><span class="p">},{</span><span class="mi">19</span><span class="p">,</span><span class="mi">7</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">5</span><span class="p">},{</span><span class="mi">4</span><span class="p">,</span><span class="mi">6</span><span class="p">,</span><span class="mi">11</span><span class="p">,</span><span class="mi">10</span><span class="p">},{</span><span class="mi">12</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">21</span><span class="p">,</span><span class="mi">13</span><span class="p">;
result = shiftGrid(grid, 4);
printResult(result);
grid = </span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">3</span><span class="p">},{</span><span class="mi">4</span><span class="p">,</span><span class="mi">5</span><span class="p">,</span><span class="mi">6</span><span class="p">},{</span><span class="mi">7</span><span class="p">,</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">;
result = shiftGrid(grid, 9);
printResult(result);
}
Output:
[[9,1,2,][3,4,5,][6,7,8,]]
[[12,0,21,13,][3,8,1,9,][19,7,2,5,][4,6,11,10,]]
[[1,2,3,][4,5,6,][7,8,9,]]
This solution flattens the 2D grid into a 1D vector v, representing the grid's elements in a linear sequence. Then, by calculating the new position for each element after the shift operation, it reconstructs the grid by placing the elements back into their respective positions based on the calculated indices. This approach avoids unnecessary copying or shifting of elements within the grid, optimizing both memory and time complexity.
Complexity
- Runtime:
O(m*n)(the nestedforloops), wherem = grid.lengthandn = grid[i].length. - Extra space:
O(m*n)(the vectorv).
Key takeaway
-
To convert a 2D matrix into a 1D vector, you can use the
std::vector's functioninsert(). -
The modulo operator
%is usually used to ensure the index is inbound.
Thanks for reading!
I hope you enjoyed this content. Don't keep it to yourself! Share it with your network and help each other improve your coding skills and advance your career!
Nhut Nguyen, the author of The Problem Solver's Guide To Coding.