algoadvance

Leetcode 1260. Shift 2D Grid Sure, let’s break down the process of solving the problem:

Problem Statement

You are given a 2D grid of integers and an integer k. You need to shift the grid k times. In one shift operation:

  1. The element at grid[i][j] moves to grid[i][j+1].
  2. The element at the end of a row moves to the beginning of the next row.
  3. The element at the end of the last row moves to the beginning of the first row.

You need to return the 2D grid after applying the shift operation k times.

Clarifying Questions

  1. Will the number of rows and columns always be greater than zero?
  2. What is the maximum size of the grid?
  3. Can k be larger than the number of elements in the grid?

Strategy

  1. Flatten the 2D grid into a 1D array.
  2. Compute the actual effective shifts as k % total number of elements.
  3. Use the computed shifts to form the new 1D array ensuring the elements are placed correctly.
  4. Transform the 1D array back to the 2D grid.

Code

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int total = m * n;
        k = k % total; // To handle cases where k is larger than the number of elements

        if (k == 0) return grid;

        // Step 1: Flatten the grid into a 1D array
        vector<int> flattened(total);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                flattened[i * n + j] = grid[i][j];
            }
        }

        // Step 2: Shift the flattened array
        vector<int> newFlattened(total);
        for (int i = 0; i < total; ++i) {
            int newIndex = (i + k) % total;
            newFlattened[newIndex] = flattened[i];
        }

        // Step 3: Convert the shifted 1D array back to the 2D grid form
        vector<vector<int>> newGrid(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                newGrid[i][j] = newFlattened[i * n + j];
            }
        }

        return newGrid;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = \{\{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int k = 1;
    vector<vector<int>> result = sol.shiftGrid(grid, k);

    for (auto row : result) {
        for (auto val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Time Complexity

The time complexity of this approach is O(m * n) where m is the number of rows and n is the number of columns in the grid. This is because we:

  1. Flatten the 2D grid into a 1D array, which takes O(m * n) time.
  2. Shift the elements in the 1D array, which takes O(m * n) time.
  3. Convert the shifted 1D array back to the 2D grid, which takes O(m * n) time.

Hence, the overall time complexity remains O(m * n).

Would you like to proceed with more details on a particular step or another question?

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI