LeetCode Problem 1260

Difficulty: 🟢 Easy
Topics: Array, Matrix, Simulation

Solution

LeetCode 1260 - Shift 2D Grid

Problem Understanding

This problem asks us to simulate repeated shift operations on a 2D matrix. We are given an m x n grid and an integer k, representing how many times the shift operation must be applied.

A single shift operation moves every element one position forward in row-major order. This means:

• Each element moves one column to the right.
• The last element of a row wraps to the beginning of the next row.
• The bottom-right element wraps all the way back to the top-left position.

If we think about the matrix as one continuous linear array, the operation is equivalent to rotating the array to the right by one position.

For example, the grid:

1 2 3
4 5 6
7 8 9

can be viewed as:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

After one shift:

[9, 1, 2, 3, 4, 5, 6, 7, 8]

which maps back to:

9 1 2
3 4 5
6 7 8

The input consists of:

• grid, a 2D integer matrix
• k, the number of shift operations

The output should be the transformed matrix after applying all shifts.

The constraints are relatively small:

• m, n <= 50
• Total cells <= 2500
• k <= 100

These limits mean even less efficient solutions may pass, but the problem is designed to test understanding of matrix indexing and simulation.

Several edge cases are important:

• k = 0, meaning no shifts occur
• k equal to the total number of cells, meaning the matrix returns to its original state
• Single-row matrices
• Single-column matrices
• A 1 x 1 matrix, where shifting changes nothing
• Large k values, where repeated simulation becomes wasteful unless optimized with modulo arithmetic

Approaches

Brute Force Approach

The most direct solution is to simulate the shift operation exactly k times.

For each shift:

1. Save the bottom-right value.
2. Move every element to its new position.
3. Put the saved value into grid[0][0].

This approach is straightforward and mirrors the problem statement exactly. Since each shift touches every cell, one shift costs O(m * n) time. Repeating this k times gives:

O(k * m * n)

This works within the constraints because k <= 100, but it performs unnecessary repeated work.

Optimal Approach

The key observation is that the grid behaves like a circular 1D array.

Instead of performing one shift at a time, we can directly compute where each element belongs after all k shifts.

For a grid with:

total = m * n

every element has a linear index:

index = row * n + col

After shifting right by k positions:

new_index = (index + k) % total

Then we convert the new linear index back into 2D coordinates:

new_row = new_index // n
new_col = new_index % n

This allows us to place every element directly into its final position in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k * m * n)	O(1)	Simulates every shift individually
Optimal	O(m * n)	O(m * n)	Computes final positions directly using index mapping

Algorithm Walkthrough

Optimal Algorithm

1. Determine the matrix dimensions.

Let:

m = number of rows
n = number of columns

The total number of elements is:

total = m * n

2. Reduce unnecessary rotations using modulo.

Shifting the grid by total positions returns it to its original state. Therefore:

k = k % total

This avoids redundant work. 3. Create a result matrix.

We allocate a new m x n matrix that will store the shifted values. 4. Traverse every element in the original grid.

For each position (row, col):

• Convert it into a 1D index:

current_index = row * n + col

• Compute its new position after shifting:

new_index = (current_index + k) % total

5. Convert the new 1D index back into 2D coordinates.

new_row = new_index // n
new_col = new_index % n

6. Place the value into the result matrix.

result[new_row][new_col] = grid[row][col]

7. Continue until all elements are processed.
8. Return the result matrix.

Why it works

The algorithm works because every position in the matrix corresponds uniquely to a linear index in row-major order. A shift operation is exactly equivalent to rotating this linear sequence to the right. By directly computing the destination index for each element using modular arithmetic, we guarantee that every value moves to the correct final position without overlaps or omissions.

Python Solution

from typing import List

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        rows = len(grid)
        cols = len(grid[0])

        total_cells = rows * cols
        k %= total_cells

        result = [[0] * cols for _ in range(rows)]

        for row in range(rows):
            for col in range(cols):
                current_index = row * cols + col
                new_index = (current_index + k) % total_cells

                new_row = new_index // cols
                new_col = new_index % cols

                result[new_row][new_col] = grid[row][col]

        return result

The implementation begins by determining the matrix dimensions and total number of cells. The modulo operation reduces unnecessary rotations because shifting by the matrix size produces the original configuration.

A new result matrix is allocated so values can be placed directly into their final positions without overwriting existing values.

The nested loops iterate through every cell exactly once. Each (row, col) coordinate is converted into a linear index using row-major ordering. The new shifted position is computed with modular arithmetic, then converted back into 2D coordinates.

Finally, the value is placed into the correct destination cell and the completed matrix is returned.

Go Solution

func shiftGrid(grid [][]int, k int) [][]int {
    rows := len(grid)
    cols := len(grid[0])

    totalCells := rows * cols
    k %= totalCells

    result := make([][]int, rows)

    for i := 0; i < rows; i++ {
        result[i] = make([]int, cols)
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            currentIndex := row*cols + col
            newIndex := (currentIndex + k) % totalCells

            newRow := newIndex / cols
            newCol := newIndex % cols

            result[newRow][newCol] = grid[row][col]
        }
    }

    return result
}

The Go solution follows the exact same logic as the Python version. The primary difference is explicit allocation of the 2D slice using make.

Go integer division automatically truncates toward zero, which is exactly what we need for converting linear indices back into row indices.

Since the constraints are small, integer overflow is not a concern.

Worked Examples

Example 1

Input:

grid = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

k = 1

Matrix dimensions:

rows = 3
cols = 3
total = 9

Shift amount:

k = 1 % 9 = 1

Original Position	Value	Linear Index	New Index	New Position
(0,0)	1	0	1	(0,1)
(0,1)	2	1	2	(0,2)
(0,2)	3	2	3	(1,0)
(1,0)	4	3	4	(1,1)
(1,1)	5	4	5	(1,2)
(1,2)	6	5	6	(2,0)
(2,0)	7	6	7	(2,1)
(2,1)	8	7	8	(2,2)
(2,2)	9	8	0	(0,0)

Final grid:

[
  [9,1,2],
  [3,4,5],
  [6,7,8]
]

Example 2

Input:

grid = [
  [3,8,1,9],
  [19,7,2,5],
  [4,6,11,10],
  [12,0,21,13]
]

k = 4

Total cells:

16

Shifting by 4 positions moves every row down by one row because each row contains exactly 4 elements.

Final result:

[
  [12,0,21,13],
  [3,8,1,9],
  [19,7,2,5],
  [4,6,11,10]
]

Example 3

Input:

grid = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

k = 9

Since:

k % 9 = 0

No effective shift occurs.

Final result:

[
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Every cell is processed exactly once
Space	O(m * n)	A separate result matrix is allocated

The algorithm performs a single traversal of the matrix. Every operation inside the loop is constant time, so the total runtime is proportional to the number of cells.

Additional space is required because the shifted values are written into a new matrix rather than modifying the original matrix in place.

Test Cases

from typing import List

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        rows = len(grid)
        cols = len(grid[0])

        total_cells = rows * cols
        k %= total_cells

        result = [[0] * cols for _ in range(rows)]

        for row in range(rows):
            for col in range(cols):
                current_index = row * cols + col
                new_index = (current_index + k) % total_cells

                new_row = new_index // cols
                new_col = new_index % cols

                result[new_row][new_col] = grid[row][col]

        return result

solution = Solution()

# Example 1
assert solution.shiftGrid(
    [[1,2,3],[4,5,6],[7,8,9]], 1
) == [[9,1,2],[3,4,5],[6,7,8]]

# Example 2
assert solution.shiftGrid(
    [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], 4
) == [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

# Example 3, full rotation returns original
assert solution.shiftGrid(
    [[1,2,3],[4,5,6],[7,8,9]], 9
) == [[1,2,3],[4,5,6],[7,8,9]]

# No shift
assert solution.shiftGrid(
    [[1,2],[3,4]], 0
) == [[1,2],[3,4]]

# Single element grid
assert solution.shiftGrid(
    [[42]], 100
) == [[42]]

# Single row grid
assert solution.shiftGrid(
    [[1,2,3,4]], 2
) == [[3,4,1,2]]

# Single column grid
assert solution.shiftGrid(
    [[1],[2],[3],[4]], 1
) == [[4],[1],[2],[3]]

# Large k reduced by modulo
assert solution.shiftGrid(
    [[1,2],[3,4]], 6
) == [[3,4],[1,2]]

# Negative values
assert solution.shiftGrid(
    [[-1,-2],[-3,-4]], 1
) == [[-4,-1],[-2,-3]]

Test	Why
3x3 grid with k=1	Basic right-shift behavior
4x4 grid with k=4	Whole-row rotation
k equal to total cells	Verifies modulo behavior
k=0	No changes should occur
1x1 grid	Smallest valid input
Single row matrix	Tests horizontal wrapping
Single column matrix	Tests vertical wrapping
Large k value	Ensures modulo optimization works
Negative numbers	Confirms values themselves do not affect logic

Edge Cases

Shift Count Equal to Zero

When k = 0, the matrix should remain unchanged. A buggy implementation might still attempt unnecessary movement or accidentally overwrite values. This implementation handles the case naturally because:

new_index = current_index

so every element maps directly back to its original position.

Shift Count Larger Than Total Cells

If k exceeds the number of cells, repeated shifts begin cycling through previously seen states. Without modulo reduction, an implementation could waste time performing redundant operations.

For example:

total cells = 4
k = 100

is equivalent to:

k = 100 % 4 = 0

The implementation avoids unnecessary work by reducing k immediately.

Single Row or Single Column Matrices

These special matrix shapes often expose indexing bugs.

For a single row:

[[1,2,3,4]]

the operation becomes a normal circular array rotation.

For a single column:

[[1],[2],[3]]

elements wrap vertically.

Because the algorithm uses a unified linear indexing system, both cases work automatically without requiring separate handling.

Single Cell Matrix

A 1 x 1 matrix never changes regardless of k. Some implementations may accidentally divide by zero or mishandle wrapping logic in tiny matrices.

Here:

total_cells = 1
k % 1 = 0

and the lone element simply maps back to itself.