How does modular arithmetic optimize the Shift 2D Grid solution?

Modular arithmetic helps calculate the effective number of shifts by using k % totalElements, reducing redundant rotations and speeding up the solution.

What is the primary approach for solving the Shift 2D Grid problem?

The primary approach is simulating the shift step by step, moving elements of the grid to the right and wrapping the last element to the start.

What common mistake should I avoid in the Shift 2D Grid problem?

A common mistake is not using modular arithmetic for large k, resulting in unnecessary shifts and inefficiency.

How can GhostInterview assist with Shift 2D Grid?

GhostInterview provides tailored solutions and feedback, focusing on matrix manipulation and optimizing shift operations using modular arithmetic.

Can the Shift 2D Grid problem be solved without simulating each shift?

Yes, you can optimize the solution by using modular arithmetic and viewing the grid as a linear array, reducing the need for repeated shifts.

#1260

Easy

auto_awesome数组·matrix

LeetCode 题解工作台

二维网格迁移

给你一个 m 行 n 列的二维网格 grid 和一个整数 k 。你需要将 grid 迁移 k 次。每次「迁移」操作将会引发下述活动：位于 grid[i][j] （ j ）的元素将会移动到 grid[i][j + 1] 。位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1…

数组矩阵模拟

题目描述

给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。

每次「迁移」操作将会引发下述活动：

位于 grid[i][j]（j < n - 1）的元素将会移动到 grid[i][j + 1]。
位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。

请你返回 k 次迁移操作后最终得到的 二维网格。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[9,1,2],[3,4,5],[6,7,8]]

示例 2：

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

示例 3：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
输出：[[1,2,3],[4,5,6],[7,8,9]]

提示：

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

lightbulb

解题思路

方法一：二维数组展开

根据题目描述，如果我们将二维数组展开成一维数组，那么每次迁移操作就是将数组中的元素向右移动一个位置，最后一个元素移动到数组的首位。

因此，我们可以将二维数组展开成一维数组，然后计算每个元素在最后的位置 $idx = (x, y)$ ，更新答案数组 ans[x][y] = grid[i][j] 即可。

时间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别是二维数组 grid 的行数和列数。需要遍历二维数组 grid 一次，计算每个元素在最后的位置。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        ans = [[0] * n for _ in range(m)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                x, y = divmod((i * n + j + k) % (m * n), n)
                ans[x][y] = v
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests candidate’s ability to simulate a matrix transformation with a step-by-step approach.
question_mark
Looks for efficient use of modular arithmetic to reduce redundant operations.
question_mark
Assesses the candidate’s understanding of handling grid dimensions and shifting elements.

warning

常见陷阱

外企场景

error
Over-complicating the solution by applying unnecessary shifts when k is large. Use modular arithmetic to optimize the number of shifts.
error
Not correctly handling the wraparound of elements when shifting the last column of the grid.
error
Misunderstanding the problem by not simulating each shift step-by-step or incorrectly handling edge cases.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Shift 2D grid in multiple directions, not just to the right.
arrow_right_alt
Shift the grid only for specific rows or columns instead of the entire grid.
arrow_right_alt
Perform the shift operation in a circular or spiral pattern.

help

常见问题

外企场景

继续练习

#1275 找出井字棋的获胜者 #1222 可以攻击国王的皇后 #999 可以被一步捕获的棋子数