{x}
blog image

Shift 2D Grid

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.

 

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 Explanation for Shift 2D Grid

This problem involves shifting elements in a 2D grid k times. Each shift moves elements one position to the right, wrapping around from the rightmost column to the leftmost column of the next row, and from the bottom-right element to the top-left.

The most efficient approach avoids repeatedly shifting the grid. Instead, it calculates the final position of each element after k shifts and directly places it in the resulting grid.

Algorithm:

  1. Flatten the Grid (conceptually): Imagine the 2D grid as a 1D array. The index of an element grid[i][j] in this 1D representation is i * n + j, where n is the number of columns.

  2. Calculate Final Position: After k shifts, the new index of an element originally at index orig_idx becomes (orig_idx + k) % (m * n), where m is the number of rows. The modulo operator % handles the wrap-around.

  3. Map to 2D Coordinates: Convert the new 1D index back into 2D coordinates (new_row, new_col) using integer division and the modulo operator:

    • new_row = new_index / n
    • new_col = new_index % n

  4. Populate the Resulting Grid: Place the element grid[i][j] at the calculated (new_row, new_col) in the result grid.

Code (Python):

def shiftGrid(grid, k):
    m, n = len(grid), len(grid[0])
    result = [[0] * n for _ in range(m)]  # Initialize the result grid
 
    for i in range(m):
        for j in range(n):
            original_index = i * n + j
            new_index = (original_index + k) % (m * n)
            new_row = new_index // n
            new_col = new_index % n
            result[new_row][new_col] = grid[i][j]
 
    return result

Time Complexity: O(m*n) - We iterate through each element of the grid once.

Space Complexity: O(m*n) - We create a new grid of the same size as the input. This could be considered O(1) if we are allowed to modify the input grid in place, but the problem statement doesn't explicitly allow that.

Code in Other Languages (briefly):

The core logic remains the same across languages. The main differences are syntax and data structure handling:

  • Java: Uses ArrayList for the result grid.
  • C++: Uses vector<vector<int>> for the result grid.
  • Go: Uses slices for the grids.
  • Javascript/Typescript: Uses nested arrays.

The time and space complexity analysis remains consistent across all language implementations.