1260. Shift 2D Grid
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 61.8%
Problem Breakdown
The problem requires shifting elements in a 2D grid k times. Each shift operation moves an element to its right neighbor, with the last element of each row moving to the first position of the next row, and the last element of the last row moving to the first position of the first row. The input is a 2D grid represented as a list of lists and an integer k indicating the number of shifts. The output should be the modified grid after performing the shift operation k times.
Inputs:
- A 2D grid (
grid: List[List[int]]) - An integer (
k: int)
Outputs:
- A 2D grid after shifting elements
ktimes
Implicit Constraints/Edge Cases:
- If
kis zero, the grid remains unchanged. - If
kis a multiple of the total number of elements in the grid, the grid also remains unchanged. - The grid can be empty or have only one row/column.
Intuition
A brute-force approach would involve repeatedly moving each element to its new position for k times. This approach has a time complexity of O(m * n * k), which is inefficient for large values of k.
The key insight is that shifting the grid k times is equivalent to shifting it k % (m * n) times, where m * n is the total number of elements in the grid. This reduces unnecessary full rotations and simplifies the problem.
We can then flatten the 2D grid into a 1D array, perform the shift operation on this array, and finally reshape it back into a 2D grid.
Approach
- Flatten the Grid: Convert the 2D grid into a 1D list to simplify the shifting process.
- Shift the Array: Use slicing to rearrange the elements in the flattened list according to the shift operation.
- Reshape the List: Convert the shifted 1D list back into a 2D grid with the original dimensions.
Complexity Analysis
- Time Complexity: O(m * n), where
mis the number of rows andnis the number of columns in the grid. This is because we only traverse the grid once to flatten it, perform the shift operation, and then reshape it. - Space Complexity: O(m * n) for storing the flattened list.
Solution
def shiftGrid(grid, k):
m, n = len(grid), len(grid[0])
total_elements = m * n
# Reduce k to avoid unnecessary full rotations
k %= total_elements
# Flatten the grid into a 1D list
flat_grid = [grid[i][j] for i in range(m) for j in range(n)]
# Perform the shift operation
shifted_flat_grid = flat_grid[-k:] + flat_grid[:-k]
# Reshape the flattened list back into a 2D grid
result = []
index = 0
for i in range(m):
row = []
for j in range(n):
row.append(shifted_flat_grid[index])
index += 1
result.append(row)
return result
Edge Cases Handled
- k = 0: The grid remains unchanged as no shifts are performed.
- k is a multiple of m * n: The grid remains unchanged due to full rotations.
- Empty Grid: The function handles an empty grid gracefully by returning an empty list.
- Single Row/Column Grid: The function correctly shifts elements in grids with only one row or column.