Code Implementation

class Solution:
    def shiftGrid(self, grid, k):
        m, n = len(grid), len(grid[0])
        total = m * n
        k = k % total
        flat = [grid[i][j] for i in range(m) for j in range(n)]
        flat = flat[-k:] + flat[:-k]
        return [flat[i*n:(i+1)*n] for i in range(m)]
      

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int total = m * n;
        k = k % total;
        vector<int> flat;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                flat.push_back(grid[i][j]);
        vector<int> shifted(total);
        for (int i = 0; i < total; ++i)
            shifted[(i + k) % total] = flat[i];
        vector<vector<int>> result(m, vector<int>(n));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                result[i][j] = shifted[i * n + j];
        return result;
    }
};
      

class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int total = m * n;
        k = k % total;
        int[] flat = new int[total];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                flat[i * n + j] = grid[i][j];
        int[] shifted = new int[total];
        for (int i = 0; i < total; ++i)
            shifted[(i + k) % total] = flat[i];
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; ++j)
                row.add(shifted[i * n + j]);
            result.add(row);
        }
        return result;
    }
}
      

var shiftGrid = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const total = m * n;
    k = k % total;
    const flat = [];
    for (let i = 0; i < m; ++i)
        for (let j = 0; j < n; ++j)
            flat.push(grid[i][j]);
    const shifted = [];
    for (let i = 0; i < total; ++i)
        shifted[(i + k) % total] = flat[i];
    const result = [];
    for (let i = 0; i < m; ++i)
        result.push(shifted.slice(i * n, (i + 1) * n));
    return result;
};
      

Problem Description

Given a 2D grid of size m x n and an integer k, shift all the elements of the grid to the right by k positions. Each shift moves every element to its right neighbor, with the last element of each row moving to the first element of the next row, and the last element of the grid moving to the first element of the grid. Return the new grid after performing k such shifts.

Key constraints:

• There is only one valid solution for each input.
• Each element is moved exactly k steps forward in row-major order, wrapping around at the end.
• No element is reused or skipped during the shift.

Thought Process

At first glance, the problem seems to require shifting each element one at a time, repeating the process k times. This brute-force approach would be inefficient, especially for large grids or large values of k.

To optimize, we can think of the 2D grid as a 1D array in row-major order. Shifting the grid by k is equivalent to rotating this 1D array by k positions to the right. After the rotation, we can reshape the 1D array back into a 2D grid.

This approach is much more efficient and easier to implement, as it reduces the problem to array manipulation and avoids repeated shifting.

Solution Approach

• Step 1: Flatten the Grid
  • Convert the 2D grid into a 1D array by traversing row by row.
• Step 2: Perform the Shift
  • Calculate the effective shift by taking k % (m * n) to handle cases where k is larger than the total number of elements.
  • Rotate the 1D array to the right by k positions. This can be done by slicing the array: take the last k elements and place them before the rest.
• Step 3: Build the New Grid
  • Reshape the shifted 1D array back into a 2D grid with m rows and n columns.

This design is chosen because it simplifies the shifting process and ensures that every element is moved exactly as required, with O(1) access time for each element.

Example Walkthrough

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

Step 1: Flatten the grid
1D array: [1,2,3,4,5,6,7,8,9]

Step 2: Shift by k=1
After shifting: [9,1,2,3,4,5,6,7,8]

Step 3: Reshape into 3x3 grid
[[9,1,2],[3,4,5],[6,7,8]]

Each element moves one position to the right, with 9 wrapping around to the front.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(k * m * n) because each shift involves moving every element, and we do this k times.
  • Space Complexity: O(m * n) for the output grid.
• Optimized Approach (Flatten & Rotate):
  • Time Complexity: O(m * n), since we flatten, shift, and rebuild the grid each in linear time.
  • Space Complexity: O(m * n) for the intermediate arrays.

The optimized approach is much faster and more scalable, especially for large grids or large k.

Summary

The Shift 2D Grid problem is elegantly solved by recognizing the equivalence between shifting a 2D grid and rotating a 1D array. By flattening the grid, performing a simple rotation, and reconstructing the grid, we achieve a solution that is both efficient and easy to understand. This approach avoids unnecessary repeated shifting and leverages the power of array manipulation for optimal performance.