We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shift 2D Grid

Number: 1386

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an m x n 2D grid and an integer k, the goal is to shift all elements of the grid k times. In each shift operation, every element moves one position to the right. The element at the end of a row moves to the beginning of the next row, and the last element of the grid moves to the first position.

Key Insights

  • The grid can be "flattened" into a single list.
  • Shifting k times is equivalent to a rotation of this list.
  • Use modulo arithmetic to handle k greater than the total number of elements.
  • After rotation, map the single list back into the 2D grid structure.

Space and Time Complexity

Time Complexity: O(m * n) because we process each element once. Space Complexity: O(m * n) for storing the flattened list and constructing the result grid.

Solution

The solution involves three primary steps:

  1. Flatten the 2D grid into a 1D list so that the shifting operation becomes a simple array rotation.
  2. Compute the effective shift using modulo: newIndex = (oldIndex + k) mod (m*n).
  3. Reconstruct the 2D grid from the rotated list by slicing it into chunks of length n.

The algorithm uses a straightforward rotation technique and then rebuilds the matrix. A key point is to use modulo arithmetic to efficiently handle cases where k is larger than the total number of elements, ensuring the rotation is performed in one pass.

Code Solutions

# Define the function shiftGrid to perform the grid shifting operation
def shiftGrid(grid, k):
    # Get dimensions of the grid
    m, n = len(grid), len(grid[0])
    total_elements = m * n
    
    # Flatten the grid into a single list
    flat_grid = [element for row in grid for element in row]
    
    # Compute effective shift to handle cases where k >= total_elements
    k = k % total_elements
    
    # Perform the rotation using list slicing
    rotated = flat_grid[-k:] + flat_grid[:-k]
    
    # Rebuild the 2D grid from the rotated list
    new_grid = []
    for i in range(m):
        # Slice the rotated list to form each row of length n
        new_grid.append(rotated[i * n: (i + 1) * n])
    
    return new_grid

# Example usage:
print(shiftGrid([[1,2,3],[4,5,6],[7,8,9]], 1))
← Back to All Questions