algoadvance

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. Element at grid[i][j] moves to grid[i][j + 1].
  2. Element at the end of a row moves to the beginning of the next row.
  3. Element at the end of the grid moves to the beginning of the grid.

Return the 2D grid after performing k shift operations.

Example:

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

Constraints:

Clarifying Questions

  1. Q: What should be done with zero or invalid k values?
    • A: If k is zero, the grid should be returned as is.
  2. Q: How should negative integers in the grid be handled?
    • A: The grid elements are within -1000 and 1000, and our operations do not need to handle them differently.
  3. Q: Can k be larger than the number of elements in the grid?
    • A: Yes, k can be larger. We should use k % (m * n) to optimize the number of actual shifts needed.

Strategy

  1. Flatten the Grid: Convert the 2D grid to a 1D list for easier manipulation.
  2. Determine Effective Shifts: Optimize k shifts by computing k % total_elements.
  3. Shift the Grid: Perform the shift on the 1D list.
  4. Reconstruct the Grid: Convert the shifted 1D list back to a 2D grid format.

Code

from typing import List

def shiftGrid(grid: List[List[int]], k: int) -> List[List[int]]:
    # Get dimensions of the grid
    m, n = len(grid), len(grid[0])
    # Flatten the grid
    flat_grid = [grid[i][j] for i in range(m) for j in range(n)]
    # Total number of elements in the grid
    total_elements = m * n
    # Optimize k
    k = k % total_elements
    
    if k == 0:
        return grid
    
    # Perform the shift
    flat_grid = flat_grid[-k:] + flat_grid[:-k]
    
    # Reconstruct the shifted grid
    new_grid = [
        [flat_grid[i * n + j] for j in range(n)]
        for i in range(m)
    ]
    return new_grid

# Example usage
grid = [[1,2,3],[4,5,6],[7,8,9]]
k = 1
print(shiftGrid(grid, k))  # Output: [[9,1,2],[3,4,5],[6,7,8]]

Time Complexity

  1. Flattening the Grid: O(m*n)
  2. Shifting the List: O(m*n)
  3. Reconstructing the Grid: O(m*n)

Thus, the overall time complexity is O(m*n), which is efficient given the constraints.

Try our interview co-pilot at AlgoAdvance.com