How To Shift Elements of a Matrix

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 to grid[i][j+1].
• The element at grid[i][n-1] moves to grid[i+1][0].
• The element at grid[m-1][n-1] moves to grid[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*N times where N = v.size() and i is any non-negative integer, you go back to the original grid; i.e. you did not shift it.
• If you shift the grid k times with 0 < k < N, the first element of the result starts from v[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 size m*n = 9.
• With k = 1 the shifted grid now starts from v[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,]]

Code explanation

1. The code declares a 1D vector v which will be used to flatten the 2D grid into a 1D vector so that shifting the elements becomes easier.

2. The first loop iterates over each row r in the input 2D grid grid. It uses the std::vector's insert function to add all the elements in the row r to the end of the 1D vector v. This effectively flattens the 2D grid into a 1D vector.

3. Two constant variables m and n are used to store the number of rows and columns in the input grid, respectively.

4. Then the code calculates the starting index p of the flattened 1D vector v after shifting by k positions. The % operator is used to ensure that the value of k wraps around if it exceeds the length of v.

5. The nested loops iterates over each row and each column of the original grid.

6. A condition checks if p has reached the end of the flattened 1D vector v. If it has, it wraps p back to the beginning of the vector.

7. Then it assigns the value at index p in the flattened vector v to the current cell of the 2D grid grid[i][j], and then increments p to move to the next element in v.

8. Finally, the modified grid is returned as the result of the function.

In summary, this code flattens a 2D grid into a 1D vector, shifts the elements of the vector to the right by k positions while wrapping around, and then reshapes the 1D vector back into the original 2D grid. The result is a grid that has been shifted to the right by k positions.

Complexity

• Runtime: O(m*n) (the nested for loops), where m = grid.length and n = grid[i].length.
• Extra space: O(m*n) (the vector v).

Key takeaway

1. To convert a 2D matrix into a 1D vector, you can use the std::vector's function insert().

2. The modulo operator % is usually used to ensure the index is inbound.

Thanks for reading! We would love to hear what you think about our content. Just drop a comment below. If you have feedback about how we can improve the content, please share it here. Thank you very much!