Shift 2d Grid - Leetcode Solution

The Shift 2D Grid problem on leetcode requires us to implement a function that takes in a 2D grid and the number of shifts that we need to perform on the grid. The function should then shift the elements of the grid based on the number of shifts and return the resulting shifted grid.

Before we discuss the solution, let's first understand the problem in detail.

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] becomes at grid[i][j + 1].
• Element at grid[i][n - 1] becomes at grid[i + 1][0].
• Element at grid[m - 1][n - 1] becomes at grid[0][0].
• Element at grid[i][0] becomes at grid[i - 1][n - 1].

Return the 2D grid which is shifted k times.

Example:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[9,1,2],[3,4,5],[6,7,8]] Explanation: The shift is shown in the above diagram. Grid after one shift is: [[9,1,2], [3,4,5], [6,7,8]]

Solution:

The first thing that we need to do is to determine the number of rows and columns in the grid. We can do this by using the len() function in Python. Once we know the number of rows and columns, we can calculate the total number of elements in the grid (m * n). We also need to determine the number of shifts required (k).

Next, we need to create an auxiliary array of size equal to the total number of elements in the grid. We will use this array to store the shifted grid.

We will then copy the elements of the original grid into the auxiliary array based on the shift operation mentioned in the problem statement. We will start from the last element of the grid and move towards the first element, copying each element to its new position based on the shift operation.

Once we have copied all the elements to their new positions in the auxiliary array, we will create a new 2D grid of the same dimensions as the original grid and copy the elements from the auxiliary array into the new 2D grid.

Finally, we will return the new 2D grid, which will be the shifted grid.

Here is the step-by-step algorithm for the solution:

1. Initialize the number of rows (m) and columns (n) in the grid.
2. Calculate the total number of elements in the grid (m * n) and the number of shifts required (k).
3. Create an auxiliary array of size equal to the total number of elements in the grid.
4. Initialize a variable (counter) to keep track of the number of elements copied to the auxiliary array.
5. Starting from the last element of the grid, copy each element to its new position in the auxiliary array based on the shift operation mentioned in the problem statement. Increment the counter after each copy operation.
6. Once all the elements have been copied to their new positions in the auxiliary array, create a new 2D grid of the same dimensions as the original grid.
7. Copy the elements from the auxiliary array into the new 2D grid based on their position in the grid.
8. Return the new 2D grid.

Here is the Python code for the solution:

def shiftGrid(grid, k): m, n = len(grid), len(grid[0]) total_elements = m * n k %= total_elements aux_array = [0] * total_elements counter = 0

for i in range(m):
    for j in range(n):
        new_index = (counter + k) % total_elements
        aux_array[new_index] = grid[i][j]
        counter += 1

new_grid = [[0] * n for _ in range(m)]
for i in range(m):
    for j in range(n):
        index = i * n + j
        new_i = index // n
        new_j = index % n
        new_grid[new_i][new_j] = aux_array[index]

return new_grid

The time complexity of this solution is O(m * n), where m and n are the number of rows and columns in the grid, respectively. The space complexity of this solution is also O(m * n), since we are using an auxiliary array to store the shifted grid.

I hope this helps you understand the Shift 2D Grid problem on leetcode and how to solve it using Python.

1