Problem

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 shift operation k times.

Examples

Example 1:

$$ grid = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \Longrightarrow \\ \begin{bmatrix} 9 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix} $$

1
2

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:

$$ grid = \begin{bmatrix} 3 & 8 & 1 & 9 \\ 19 & 7 & 2 & 5 \\ 4 & 6 & 11 & 10 \\ 12 & 0 & 21 & 13 \end{bmatrix} \\ \Longrightarrow \\ \begin{bmatrix} 13 & 3 & 8 & 1 \\ 9 & 19 & 7 & 2 \\ 5 & 4 & 6 & 11 \\ 10 & 12 & 0 & 21 \end{bmatrix} \\ \Longrightarrow \\ \begin{bmatrix} 21 & 13 & 3 & 8 \\ 1 & 9 & 19 & 7 \\ 2 & 5 & 4 & 6 \\ 11 & 10 & 12 & 0 \end{bmatrix} \\ $$

$$ \Longrightarrow \\ \begin{bmatrix} 0 & 21 & 13 & 3 \\ 8 & 1 & 9 & 19 \\ 7 & 2 & 5 & 4 \\ 6 & 11 & 10 & 12 \end{bmatrix} \\ \Longrightarrow \\ \begin{bmatrix} 12 & 0 & 21 & 13 \\ 3 & 8 & 1 & 9 \\ 19 & 7 & 2 & 5 \\ 4 & 6 & 11 & 10 \end{bmatrix} $$

1
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:

1
2

Input: grid =[[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Solution

Method 1 - Treat Matrix as 1D Array

We can easily convert this 2D matrix to 1D Array. Lets take example 1. Element 1 in [0,0] will be at [0] in 1D array. Likewise, element 5 at [1,1] is at index [4] in 1D array. So, any element in 2D array will be numRows * rowIndex + column

1

1dIndex = rowIndex * rowSize + colIndex

We should also do k%size of 2D array.

Once we have the size, we need to convert back the 1D array to 2D Array:

1
2

rowIdx = 1dIndex / C
colIdx = 1dIndex % C

Method 2 - Using Arraylist Instead of Array Indexes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public List<List> shiftGrid(int[][] grid, int k) {
	List<List<Integer>> ans = new ArrayList<>();
	List<Integer> temp = new ArrayList<>();

	int m = grid.length;
	int n = grid[0].length;
	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			temp.add(grid[i][j]);
		}
	}
	Collections.rotate(temp, k);

	for (int i = 0; i < m * n; i += n) {
		List<Integer> my = new ArrayList<>();
		for (int j = i; j<i + n; j++) {
			my.add(temp.get(j));
		}
		ans.add(my);

	}

	return ans;
}