2946. Matrix Similarity After Cyclic Shifts

EasyArrayMathMatrixSimulation
Leetcode Link

Problem Description

In this problem, we are given a 2D matrix of integers where each element of the matrix is at row i and column j. You are instructed to perform a specific operation on the matrix:

  • If the row index i is odd, you are to cyclically shift that row k times to the right.
  • If the row index i is even, you are to cyclically shift that row k times to the left.

A cyclic shift to the right means that the last column of the matrix will move to the first position, and all other columns will move one position to the right. Conversely, a cyclic shift to the left means that the first column of the matrix will move to the last position, and all other columns will move one position to the left.

Your task is to determine if after applying these shifts k times to each row, the final matrix obtained is identical to the initial matrix. You need to return true if they are identical, and false otherwise.

Intuition

The solution approach involves simulating the cyclic shifts on the matrix to compare the final positions of each element with their original positions.

Since we want to avoid actually performing k shifts (which could be costly if k is large), we instead calculate the final position of each element directly using modular arithmetic:

  • For an odd indexed row (shifts to the right): The new position of an element initially at index j will now be (j + k) % n where n is the number of columns.
  • For an even indexed row (shifts to the left): The new position of an element initially at index j will now be (j - k + n) % n.

The % n ensures that the calculation wraps around the row correctly, simulating the cyclic nature of the shift.

As we iterate through every element of the matrix, we check if after applying either the left or right shift (based on whether the row index is even or odd), the element in the original matrix is the same as the element in its calculated new position after the shift. If for any element the values differ, we can return false right away as the matrices will not be identical after the shifts. If we complete the iteration without finding any differences, we return true.

Learn more about Math patterns.

Solution Approach

The solution is quite straightforward and does not require complex data structures or algorithms. It simply makes use of a nested loop to iterate through each element in the input matrix mat, and applies conditional checks and modular arithmetic to validate the matrix's shift requirements.

Here's a step-by-step explanation of the implementation:

  1. We first determine the number of columns n in the matrix by inspecting the length of the first row (len(mat[0]) since it's a 0-indexed m x n integer matrix).
  2. The outer loop iterates through each row of the matrix. For each row, our goal is to determine if its elements would end up in the same position if we cyclically shifted the row k times, corresponding to its index (even or odd).
  3. Inside this outer loop, we create an inner loop to iterate over each element (x) in the current row.
  4. We use a conditional (if-else) statement to check if we are at an even (i % 2 == 0) or odd (i % 2 == 1) row, as this determines the direction of the shift (left or right).
  5. For each element x, we calculate its expected position after the shifts, as follows:
    • If we're in an odd-indexed row (i % 2 == 1), we calculate the new index by right shifting, using (j + k) % n. We check if the current element x matches the element in the column (j + k) % n of the initial matrix.
    • If we're in an even-indexed row (i % 2 == 0), we calculate the new index by left shifting, using (j - k + n) % n. We check if the current element x matches the element in the column (j - k + n) % n of the initial matrix.
  6. If at any point during the iteration we find a mismatch (i.e., x does not equal the value at its new position), we immediately return false, as the matrix will no longer be the same after the cyclic shifts.
  7. If the loop completes successfully without finding any mismatches, it means all elements retain their position after the cyclic shifts, and we return true signifying that the initial and final matrices are exactly the same.

The code snippet for this solution makes use of efficient indexing and modular arithmetic to avoid the need for actual shifting, which is an optimization that allows the algorithm to run in O(m * n) time, where m is the number of rows and n is the number of columns in the matrix mat. This time complexity is derived from the fact that we must check every element in the matrix exactly once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Example Walkthrough

Let's assume we have the following small 3x3 matrix mat and the number of times we need to perform the shift is k = 2.

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

Following the steps of the solution approach to check whether a cyclic shift of k times would result in the same matrix:

  1. Number of columns n is 3 as there are 3 elements in the first row of mat.

  2. We iterate through each row:

    • Row 0 (even index, shift left): [1, 2, 3]
      • Element 1 (index 0) would move to index (0 - 2 + 3) % 3 = 1. But the element at index 1 is 2. Not a match, so we return false.

    Thus, without needing to continue further, we can already conclude that the matrix will not be identical after the shifts since in the very first step, the element 1 would not end up in the same position.

Here's how the matrix would look after applying the cyclic shifts considering all elements, although the mismatch in the first check precludes this:

Even row (row 0): Left shift by k (2 times): Original row: [1, 2, 3] -> After shift: [3, 1, 2]

Odd row (row 1): Right shift by k (2 times): Original row: [4, 5, 6] -> After shift: [5, 6, 4]

Even row (row 2): Left shift by k (2 times): Original row: [7, 8, 9] -> After shift: [9, 7, 8]

It's evident that the shifted matrix would not match the original mat. Hence, our function would return false:

1Shifted mat = [
2  [3, 1, 2],
3  [5, 6, 4],
4  [9, 7, 8]
5]
6
7// This does not match the original `mat`, so the result is false.

This example illustrates the core intuition behind the prescribed solution approach and showcases how an early mismatch can shortcut the process, providing a quick response without having to process the entire matrix.

Solution Implementation

1from typing import List
2
3class Solution:
4    def are_similar(self, matrix: List[List[int]], shift_amount: int) -> bool:
5        '''
6        Check if the matrix has a special similarity property.
7
8        The function checks if each row (when considered as a ring) 
9        can be rotated by a fixed number of steps 'shift_amount' to 
10        match either the next row or the previous row, depending on 
11        whether the index is odd or even.
12
13        Args:
14        matrix : A list of lists, where each sublist represents a row of the matrix.
15        shift_amount : An integer representing the fixed number of steps of rotation.
16
17        Returns:
18        A boolean value indicating whether the matrix has the similarity as per the mentioned conditions.
19        '''
20      
21        # Calculate the number of columns in the matrix
22        num_columns = len(matrix[0])
23      
24        # Loop through each row and each element in the row
25        for row_index, row in enumerate(matrix):
26            for col_index, element in enumerate(row):
27                # For odd-indexed rows, check if the current element matches the element in the shifted
28                # position of the same row to the right by 'shift_amount' steps
29                if row_index % 2 == 1 and element != matrix[row_index][(col_index + shift_amount) % num_columns]:
30                    return False
31              
32                # For even-indexed rows, check if the current element matches the element in the shifted
33                # position of the same row to the left by 'shift_amount' steps
34                if row_index % 2 == 0 and element != matrix[row_index][(col_index - shift_amount + num_columns) % num_columns]:
35                    return False
36      
37        # If all elements match the shifted positions, the matrix has the similarity property
38        return True
39
1class Solution {
2
3    // Method to check if a given matrix can be made similar by rotating every row either left or right
4    public boolean areSimilar(int[][] matrix, int k) {
5        // m is the number of rows in the matrix
6        int numRows = matrix.length;
7        // n is the number of columns in the matrix
8        int numCols = matrix[0].length;
9
10        // Normalize the rotation step k to be in the range of [0, numCols)
11        k %= numCols;
12
13        // Loop through each row of the matrix
14        for (int i = 0; i < numRows; ++i) {
15            // Loop through each column of the current row
16            for (int j = 0; j < numCols; ++j) {
17                // For odd rows, check if rotating to the right gives the correct entry
18                if ((i % 2 == 1) && matrix[i][j] != matrix[i][(j + k) % numCols]) {
19                    return false; // If not, the matrix cannot be made similar
20                }
21                // For even rows, check if rotating to the left gives the correct entry
22                if ((i % 2 == 0) && matrix[i][j] != matrix[i][(j - k + numCols) % numCols]) {
23                    return false; // If not, the matrix cannot be made similar
24                }
25            }
26        }
27
28        // If all rows satisfy the condition, the matrix can be made similar
29        return true;
30    }
31}
32
1#include <vector>
2
3class Solution {
4public:
5    bool areSimilar(std::vector<std::vector<int>>& matrix, int rotationCount) {
6        int numRows = matrix.size(); // Number of rows in the matrix
7        int numCols = matrix[0].size(); // Number of columns in the matrix
8      
9        // Reduce the rotation count to its equivalent
10        // within the range of the number of columns.
11        rotationCount %= numCols;
12      
13        // Loop through each cell in the matrix.
14        for (int row = 0; row < numRows; ++row) {
15            for (int col = 0; col < numCols; ++col) {
16                // If the current row is odd, check if the value in the
17                // current cell is equal to the value in the cell
18                // obtained by rotating the current row right by rotationCount steps.
19                if (row % 2 == 1 && matrix[row][col] != matrix[row][(col + rotationCount) % numCols]) {
20                    return false; // Return false if they are not equal.
21                }
22              
23                // If the current row is even, check if the value in the
24                // current cell is equal to the value in the cell
25                // obtained by rotating the current row left by rotationCount steps.
26                if (row % 2 == 0 && matrix[row][col] != matrix[row][(col - rotationCount + numCols) % numCols]) {
27                    return false; // Return false if they are not equal.
28                }
29            }
30        }
31      
32        // If all comparisons passed, the rotated matrix is similar
33        // to the original matrix.
34        return true;
35    }
36};
37
1function areSimilar(matrix: number[][], shiftAmount: number): boolean {
2    const rowCount = matrix.length;  // m represents the number of rows in the matrix.
3    const colCount = matrix[0].length;  // n represents the number of columns in the matrix.
4    shiftAmount %= colCount;  // Normalize the shifting amount to be within the bounds of the columns.
5  
6    // Loop through each row of the matrix.
7    for (let row = 0; row < rowCount; ++row) {
8        // Loop through each column in the current row.
9        for (let col = 0; col < colCount; ++col) {
10            // If the row is odd (1-indexed), check if the current element is equal to the element at the shifted position.
11            if (row % 2 === 1 && matrix[row][col] !== matrix[row][(col + shiftAmount) % colCount]) {
12                return false;
13            }
14            // If the row is even (1-indexed), check if the current element is equal to the element at the shifted position.
15            if (row % 2 === 0 && matrix[row][col] !== matrix[row][(col - shiftAmount + colCount) % colCount]) {
16                return false;
17            }
18        }
19    }
20    return true; // If all elements match their respective shifted positions, return true.
21}
22

Time and Space Complexity

Time Complexity

The time complexity of the function is determined by the nested loops which iterate over every element of the matrix. Since mat is an n x n matrix, where n is the length of its rows, and there are two for-loops iterating over n rows and n columns, the time complexity is O(n^2).

Space Complexity

The space complexity of the function is O(1). This is because the function uses a constant amount of additional memory space, regardless of the input size. There are only a few variable assignments, and there's no use of any additional data structures that scale with input size.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of these properties could exist for a graph but not a tree?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄