Problem statement
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.length
.n == grid[i].length
.1 <= m <= 50
.1 <= n <= 50
.-1000 <= grid[i][j] <= 1000
.0 <= k <= 100
.
Solution: Convert a 2D array into an 1D one
Convert the 2D grid
into 1D vector v
to perform the shifting easier. The first element of the result now starts from v[v.size() - k]
.
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 = 1
the shiftedgrid
now 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;
for (auto& r : grid) {
v.insert(v.end(), r.begin(), r.end());
}
const int m = grid.size();
const int n = grid[0].size();
int p = v.size() - (k % v.size());
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (p == v.size()) {
p = 0;
}
grid[i][j] = v[p++];
}
}
return grid;
}
void printResult(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{{1,2,3},{4,5,6},{7,8,9}};
auto result = shiftGrid(grid, 1);
printResult(result);
grid = {{3,8,1,9},{19,7,2,5},{4,6,11,10},{12,0,21,13}};
result = shiftGrid(grid, 4);
printResult(result);
grid = {{1,2,3},{4,5,6},{7,8,9}};
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,]]
Complexity
Runtime:
O(mn)
, wherem = grid.length
,n = grid[i].length
.Extra space:
O(mn)
.
References
Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.
Did you find this article valuable?
Support LeetSolve by becoming a sponsor. Any amount is appreciated!