Cyclically Shift Rows and Columns solution and explanation
3 more videos on this problem
LeetCode 4052 Solution | Cyclically Shift Rows and Columns | Weekly Contest 519 | C++Plum Codes · 8:17 · 48 views
LeetCode 4052 | Cyclically Shift Rows and Columns | Weekly Contest 519 #leetcode #weeklycontest #dsaDebugging Life · 23:03 · 13 views
4052. Cyclically Shift Rows and Columns (Leetcode Easy)Programming Live with Larry · 6:07 · 2 views
Weekly Contest 519 Q1: Cyclically Shift Rows and ColumnsUnbound Coder · 10:40
The problem
You are given an integer n, a 2D integer array grid of size n x n, and two integer arrays rowShift and colShift, each of length n, where:
rowShift[i]represents the number of positions to cyclically shift theithrow ofgridto the left.colShift[j]represents the number of positions to cyclically shift thejthcolumn ofgridupward.
First, cyclically shift each row according to rowShift, then cyclically shift each column of the resulting grid according to colShift.
Return the resulting grid after performing all the shifts.
A cyclic left shift of a row by k positions moves the element at column j to column (j - k + n) % n. All other rows remain unchanged.
A cyclic upward shift of a column by k positions moves the element at row i to row (i - k + n) % n. All other columns remain unchanged.
Example 1:
Input: n = 2, grid = [[1,2],[3,4]], rowShift = [1,0], colShift = [0,1]
Output: [[2,4],[3,1]]
Explanation:
The grid changes as follows:
Example 2:
Input: n = 3, grid = [[1,2,3],[4,5,6],[7,8,9]], rowShift = [1,2,0], colShift = [2,2,1]
Output: [[7,8,5],[2,3,9],[6,4,1]]
Explanation:
The grid changes as follows:
Constraints:
1 <= n == grid.length == grid[i].length <= 101 <= grid[i][j] <= 100rowShift.length == colShift.length == n0 <= rowShift[i], colShift[i] < n
Approach overview
Problem Overview: You are given a 2D matrix and need to cyclically shift each row to the right by one position and each column downward by one position. The shift is cyclic, meaning elements wrap around to the beginning of the row or column.
Approach 1: Brute Force (O(n*m) time, O(n*m) space)
Create a new matrix of the same dimensions. For each element at (i, j), compute its new position: row stays the same but column becomes (j + 1) % m for row shift, and then column stays the same but row becomes (i + 1) % n for column shift. Copy the element to the new matrix. This approach is straightforward and easy to implement but uses extra memory for the result matrix. It is useful if you are not allowed to modify the input matrix in place.
Approach 2: In-Place Simulation (O(n*m) time, O(1) space)
Instead of using extra space, you can perform the shifts directly on the original matrix. First, save the last element of each row (or use a temporary variable) and shift all elements in that row to the right by one. Then, handle the column shifts similarly, saving the bottom element of each column and shifting elements down. This requires careful handling of overlapping operations—you can do row shifts first, then column shifts, or vice versa, using a single temporary variable per row/column. The key insight is that you only need to store one element at a time to avoid overwriting. This approach is memory-efficient and preferred when the matrix is large.
Recommended for interviews: Interviewers expect you to recognize that the problem can be solved with simple simulation. Start with the brute force to show you understand the problem, then optimize to the in-place version to demonstrate your ability to manage memory. The in-place approach shows you can think about data mutation carefully, which is a valuable skill for coding interviews.
For more practice on matrix manipulation, check out our matrix topic or arrays topic.
Solution
Thinking
n \le 10, so applying the two shifts exactly as stated is enough. There is no need to fold the mapping into a single index formula first.Rows must move left before columns move up, and the upward shift uses the new column index.
colShiftcannot be applied with the originalj.We therefore keep an intermediate grid for the row shifts, then write the column shifts into the answer.
The problem asks us to cyclically shift each row left according to rowShift, then cyclically shift each column up according to colShift.
Create an intermediate matrix t. After a left cyclic shift of rowShift[i], the entry grid[i][j] lands at
$
t[i][(j - rowShift[i] + n) bmod n]
Then create the answer matrix ans. After an upward cyclic shift of colShift[j], t[i][j] lands at
ans[(i - colShift[j] + n) bmod n][j]
The time complexity is O(n^2) and the space complexity is O(n^2), where n$ is the side length of the grid.
class Solution:
def cyclicShift(
self, n: int, grid: list[list[int]], rowShift: list[int], colShift: list[int]
) -> list[list[int]]:
t = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
t[i][(j - rowShift[i] + n) % n] = grid[i][j]
ans = [[0] * n for _ in range(n)]
for j in range(n):
for i in range(n):
ans[(i - colShift[j] + n) % n][j] = t[i][j]
return ansclass Solution {
public int[][] cyclicShift(int n, int[][] grid, int[] rowShift, int[] colShift) {
int[][] t = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
t[i][(j - rowShift[i] + n) % n] = grid[i][j];
}
}
int[][] ans = new int[n][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
ans[(i - colShift[j] + n) % n][j] = t[i][j];
}
}
return ans;
}
}class Solution {
public:
vector<vector<int>> cyclicShift(int n, vector<vector<int>>& grid, vector<int>& rowShift, vector<int>& colShift) {
vector<vector<int>> t(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
t[i][(j - rowShift[i] + n) % n] = grid[i][j];
}
}
vector<vector<int>> ans(n, vector<int>(n));
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
ans[(i - colShift[j] + n) % n][j] = t[i][j];
}
}
return ans;
}
};function cyclicShift(
n: number,
grid: number[][],
rowShift: number[],
colShift: number[],
): number[][] {
const t = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
t[i][(j - rowShift[i] + n) % n] = grid[i][j];
}
}
const ans = Array.from({ length: n }, () => Array(n).fill(0));
for (let j = 0; j < n; j++) {
for (let i = 0; i < n; i++) {
ans[(i - colShift[j] + n) % n][j] = t[i][j];
}
}
return ans;
}func cyclicShift(n int, grid [][]int, rowShift []int, colShift []int) [][]int {
t := make([][]int, n)
for i := range t {
t[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
t[i][(j-rowShift[i]+n)%n] = grid[i][j]
}
}
ans := make([][]int, n)
for i := range ans {
ans[i] = make([]int, n)
}
for j := 0; j < n; j++ {
for i := 0; i < n; i++ {
ans[(i-colShift[j]+n)%n][j] = t[i][j]
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n*m) | O(n*m) | When input can be modified or for clarity |
| In-Place Simulation | O(n*m) | O(1) | Memory-constrained environments |
Frequently asked questions
Cyclically Shift Rows and Columns Python solution
In Python, you can use list comprehensions or nested loops. For in-place, use a temporary variable to store the last element of each row/column, then shift elements using a loop. Example: for each row, store last element, then move elements from right to left.
Is Cyclically Shift Rows and Columns easy or hard?
It is rated as Easy on FleetCode with a 75.3% acceptance rate. The problem is straightforward if you understand how to perform cyclic shifts on arrays.
How to solve Cyclically Shift Rows and Columns in O(n)?
It's not possible to solve in O(n) because you need to process all n*m elements. The optimal time is O(n*m), which is linear in the total number of elements.
What is the best approach for Cyclically Shift Rows and Columns?
The best approach is in-place simulation using O(1) extra space. You shift each row right by one and each column down by one directly on the matrix, using temporary variables to avoid overwriting. This achieves O(n*m) time complexity.
Is Cyclically Shift Rows and Columns asked at Google/Amazon/Meta?
While not a frequently asked question at these companies, it tests basic matrix manipulation and in-place operations, which are common in coding interviews. It's a good warm-up problem.
What data structure is used in Cyclically Shift Rows and Columns?
The problem uses a 2D array (matrix). The solution uses simple array indexing and temporary variables for shifting. No advanced data structures are required.
What is the time complexity of Cyclically Shift Rows and Columns?
The time complexity is O(n*m), where n is the number of rows and m is the number of columns. You must visit every element at least once to perform the shifts.