Skip to main content
Talentd

Cyclically Shift Rows and Columns - Solution & Explanation

Easy8 min read
Practice this problem

Problem Statement

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 the ith row of grid to the left.
  • colShift[j] represents the number of positions to cyclically shift the jth column of grid upward.

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 <= 10
  • 1 <= grid[i][j] <= 100
  • rowShift.length == colShift.length == n
  • 0 <= rowShift[i], colShift[i] < n

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. colShift cannot be applied with the original j.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Video Solution

LeetCode 4052 Solution | Cyclically Shift Rows and Columns | Weekly Contest 519 | C++ • Plum Codes • 48 views views

Watch 3 more video solutions →

Ready to solve this problem?

Practice Cyclically Shift Rows and Columns with our built-in code editor and test cases.

Practice on FleetCode