algoadvance

Leetcode 1260. Shift 2D Grid

Problem Statement

You are 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:

  1. Element at grid[i][j] moves to grid[i][j+1].
  2. Element at grid[i][n-1] moves to grid[i+1][0].
  3. Element at grid[m-1][n-1] moves to grid[0][0].

Return the 2D grid after applying the shift operation 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]]

Clarifying Questions

  1. What are the constraints on the values of m, n, and k?
  2. Will the grid always be non-empty?
  3. If k is greater than the total number of elements in the grid, should we take k % (m*n)?

Strategy

The strategy to solve this problem involves flattening the 2D grid into a 1D array, performing the shift on this 1D array, and then converting the 1D array back into the 2D grid.

Steps:

  1. Calculate the total number of elements in the grid (total = m * n).
  2. Normalize the number of shifts: k = k % total (since shifting by total times results in the same grid).
  3. Flatten the grid into a 1D array.
  4. Perform the shift on the 1D array.
  5. Convert the 1D array back to a 2D grid.

Code

import java.util.ArrayList;
import java.util.List;

public class Shift2DGrid {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int total = m * n;
        
        // Normalize the number of shifts
        k = k % total;
        
        // Flatten the grid into a 1D array
        int[] flattened = new int[total];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                flattened[i * n + j] = grid[i][j];
            }
        }
        
        // Create a new flattened array shifted by k positions
        int[] shifted = new int[total];
        for (int i = 0; i < total; i++) {
            shifted[(i + k) % total] = flattened[i];
        }

        // Unflatten the array back into a 2D grid
        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;
    }
}

Time Complexity

Therefore, the overall time complexity is O(m * n).

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