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 the shift operation k times.
Key Insights
- The grid can be flattened into a 1D array for easier manipulation.
- The effective number of shifts can be reduced by taking
k % (m * n), since shifting the grid a full cycle (m * n shifts) results in the same grid. - After calculating the new positions for each element based on the effective shifts, we can reconstruct the 2D grid.
Space and Time Complexity
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Solution
The solution involves flattening the 2D grid into a 1D array to facilitate easier shifting of elements. We then compute the effective number of shifts required and place each element in its new position in a new 1D array. Finally, we convert this array back into a 2D grid.