Skip to main content

Matrix

Matrix Similarity After Cyclic Shifts Solution In C++/Python/java/JS

Matrix Similarity After Cyclic Shifts Problem Description:

You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.
The following process happens k times:
Even-indexed rows (0, 2, 4, ...) are cyclically shifted to the left.
Odd-indexed rows (1, 3, 5, ...) are cyclically shifted to the right.
Return true if the final modified matrix after k steps is identical to the original matrix, and false otherwise.
Matrix Similarity After Cyclic Shifts Problem Description

Examples:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4
Output: false
Explanation: In each step left shift is applied to rows 0 and 2 (even indices), and right shift to row 1 (odd index).

Input: mat = [[2,2],[2,2]], k = 3
Output: true
Explanation: As all the values are equal in the matrix, even after performing cyclic shifts the matrix will remain the same.

Constraints:

1 <= mat.length <= 25
1 <= mat[i].length <= 25
1 <= mat[i][j] <= 25
1 <= k <= 50

Brute Force Approach

Imagine you are given a grid or table of numbers — that’s your matrix. For example:

1 2 3  
4 5 6  
7 8 9

Now, you're told to perform an operation k times. What’s that operation?

  • Even-indexed rows (0, 2, 4...) should be shifted to the left by 1.
  • Odd-indexed rows (1, 3, 5...) should be shifted to the right by 1.

So, think of each row like a line of people holding hands. If they’re on an even row, everyone steps one spot to the left, and the person at the front wraps around to the back. If they’re on an odd row, it’s the opposite — everyone steps one spot to the right, and the person at the back wraps around to the front.

The goal is simple: after doing this k times, is the matrix back to exactly what it was originally?

Let’s break it down using just one shift operation.

Take this matrix again:

Row 0: 1 2 3  → Even → shift left → 2 3 1  
Row 1: 4 5 6  → Odd  → shift right → 6 4 5  
Row 2: 7 8 9  → Even → shift left → 8 9 7

So after 1 shift, the matrix becomes:

2 3 1  
6 4 5  
8 9 7

Notice how:

  • For left shift, we just move everything one place to the left and wrap the first item to the end.
  • For right shift, we move everything one place to the right and wrap the last item to the beginning.

This kind of operation is called a cyclic shift or circular rotation.

Now, if we keep repeating this shift operation, things will keep rotating over and over.

Let’s say your row has m elements. If you shift it m times, you’ll actually come back to the original row.

Example:

Row: [1, 2, 3, 4]

  • 1 shift left → [2, 3, 4, 1]
  • 2 shifts left → [3, 4, 1, 2]
  • 3 shifts left → [4, 1, 2, 3]
  • 4 shifts left → [1, 2, 3, 4] ← Back to start!

So doing 4 shifts (which is equal to the row size) brings us back to the start.

Imagine you have a row of m elements in an array, and you want to shift the elements either to the left or right. When you shift, you need to ensure that the elements stay within the bounds of the array.

For example, if you have an array like [1, 2, 3, 4, 5] (m = 5), and you want to shift the elements to the left by one position, the element 1 (which was at the start) should wrap around to the end of the array. So, the array would become [2, 3, 4, 5, 1].

To make sure the elements stay within bounds, you use the modulo operator (%). Here's why:

  • The modulo operation ensures that when you try to access an index that goes beyond the end of the array, it wraps around and starts from the beginning again.
  • For example, if you're shifting to the right and you want to move the last element (index m-1) to the front, you use (index + 1) % m to make sure that if the index goes beyond m-1, it wraps around to index 0.
  • Similarly, for shifting to the left, you use (index - 1 + m) % m to ensure that if the index goes below 0, it wraps around to the last index.

In simple terms, the mod operation helps manage the "circular" nature of the array when shifting elements, ensuring that everything stays within the valid range of indices.

In our brute-force approach, we just do k shifts directly to keep things simple and easy to follow.

Okay, now here’s the big idea.

We:

  1. Make a copy of the original matrix (call it ans) because we don’t want to mess up the original while shifting.
  2. For each of the k steps, we go row by row and shift based on whether the row index is even (left) or odd (right).
  3. After one full round of shifting (all rows processed), we update our copy with the newly shifted matrix.
  4. Repeat this whole shifting process k times.

At the end, we just check — is our final shifted matrix equal to the original matrix we started with?

If yes → return true.
If no → return false.

In simple terms, we’re simulating what happens when we repeatedly rotate rows left or right, according to the rules. We do it step by step for k times, and check if we land back exactly where we started.

Think of it like a dance move that everyone does in sync — after a few rounds, if everyone ends up back in their original spot, then it’s a perfect loop!

💡
Try it Yourself!

Let's understand with an example:

Matrix Similarity After Cyclic Shifts Example:

Initial Matrix:

[1, 2, 3] → Row 0 (even)
[4, 5, 6] → Row 1 (odd)
[7, 8, 9] → Row 2 (even)

Step-by-step Shifts (k = 4)

Step 1:

  • Row 0 → left → [2, 3, 1]
  • Row 1 → right → [6, 4, 5]
  • Row 2 → left → [8, 9, 7]

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

Step 2:

  • Row 0 → left → [3, 1, 2]
  • Row 1 → right → [5, 6, 4]
  • Row 2 → left → [9, 7, 8]

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

Step 3:

  • Row 0 → left → [1, 2, 3]
  • Row 1 → right → [4, 5, 6]
  • Row 2 → left → [7, 8, 9]

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

Back to the original matrix after 3 steps — but let’s do the 4th step as required.

Step 4:

  • Row 0 → left → [2, 3, 1]
  • Row 1 → right → [6, 4, 5]
  • Row 2 → left → [8, 9, 7]

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

Final Check:

Final matrix ≠ original matrix

Result: false

Steps to Implement the Solution:

  • Get matrix size
    • Store number of rows n and columns m.
  • Create two copies of the matrix
    • ans to track the current state of the matrix after each shift.
    • temp to store the result after each round of shifting.
  • Repeat for k times
    • For each row:
      • If even-indexed, shift elements left by 1 using (j + 1) % m.
      • If odd-indexed, shift elements right by 1 using (j - 1 + m) % m.
    • After all rows are processed, update ans = temp.
  • After all k shifts, compare ans with original mat.
    • If they match, return true.
    • Else, return false.

Matrix Similarity After Cyclic Shifts solution

Code Implementation / Leetcode solution of Matrix Similarity After Cyclic Shifts
1. Matrix Similarity After Cyclic Shifts solution in C++ Try on Compiler 
class Solution {
public:
    bool areSimilar(vector<vector<int>>& mat, int k) {

        // Get number of rows in the matrix
        int n = mat.size();

        // Get number of columns in the matrix
        int m = mat[0].size();

        // Create a copy of the original matrix to apply transformations
        vector<vector<int>> ans = mat;

        // Create a temporary matrix to store results of each shift round
        vector<vector<int>> temp = mat;

        // Repeat the shift operation k times
        while(k--)
        {
            // Loop through each row
            for(int i = 0; i < n; i++)
            {
                // If row index is even, perform a left shift
                if(i % 2 == 0)
                {
                    // Shift each element one position to the left
                    for(int j = 0; j < m; j++)
                    {
                        temp[i][j] = ans[i][(j + 1) % m];
                    }
                }
                // If row index is odd, perform a right shift
                else
                {
                    // Shift each element one position to the right
                    for(int j = 0; j < m; j++)
                    {
                        temp[i][j] = ans[i][(j - 1 + m) % m];
                    }
                }
            }

            // Update the current matrix state after one full round of shifting
            ans = temp;
        }

        // Return true if final matrix matches the original one, else false
        return ans == mat;
    }
};

2. Matrix Similarity After Cyclic Shifts solution in Java Try on Compiler 
class Solution {
    public boolean areSimilar(int[][] mat, int k) {

        // Get number of rows in the matrix
        int n = mat.length;

        // Get number of columns in the matrix
        int m = mat[0].length;

        // Copy the matrix into ans and temp
        int[][] ans = new int[n][m];
        int[][] temp = new int[n][m];

        // Initialize ans and temp with the original matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i][j] = mat[i][j];
                temp[i][j] = mat[i][j];
            }
        }

        // Repeat the shift operation k times
        while (k-- > 0) {

            // Loop through each row
            for (int i = 0; i < n; i++) {

                // If row index is even, perform a left shift
                if (i % 2 == 0) {

                    // Shift elements to the left
                    for (int j = 0; j < m; j++) {
                        temp[i][j] = ans[i][(j + 1) % m];
                    }

                }
                // If row index is odd, perform a right shift
                else {

                    // Shift elements to the right
                    for (int j = 0; j < m; j++) {
                        temp[i][j] = ans[i][(j - 1 + m) % m];
                    }

                }
            }

            // Update the current matrix with the shifted version
            for (int i = 0; i < n; i++) {
                System.arraycopy(temp[i], 0, ans[i], 0, m);
            }
        }

        // Check if the final matrix equals the original
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (ans[i][j] != mat[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
}

3. Matrix Similarity After Cyclic Shifts solution in Python Try on Compiler 
class Solution:
    def areSimilar(self, mat, k):

        # Get number of rows
        n = len(mat)

        # Get number of columns
        m = len(mat[0])

        # Make copies of the matrix
        ans = [row[:] for row in mat]
        temp = [row[:] for row in mat]

        # Repeat shift k times
        for _ in range(k):

            # Process each row
            for i in range(n):

                # For even-indexed rows, shift left
                if i % 2 == 0:
                    for j in range(m):
                        temp[i][j] = ans[i][(j + 1) % m]

                # For odd-indexed rows, shift right
                else:
                    for j in range(m):
                        temp[i][j] = ans[i][(j - 1 + m) % m]

            # Update ans with current shifted state
            ans = [row[:] for row in temp]

        # Compare final matrix with original
        return ans == mat

4. Matrix Similarity After Cyclic Shifts solution in Javascript Try on Compiler 
var areSimilar = function(mat, k) {

    // Get number of rows
    const n = mat.length;

    // Get number of columns
    const m = mat[0].length;

    // Create deep copies of the matrix
    let ans = mat.map(row => [...row]);
    let temp = mat.map(row => [...row]);

    // Perform shifting k times
    while (k-- > 0) {

        // Loop through each row
        for (let i = 0; i < n; i++) {

            // If even-indexed, shift left
            if (i % 2 === 0) {
                for (let j = 0; j < m; j++) {
                    temp[i][j] = ans[i][(j + 1) % m];
                }
            }

            // If odd-indexed, shift right
            else {
                for (let j = 0; j < m; j++) {
                    temp[i][j] = ans[i][(j - 1 + m) % m];
                }
            }
        }

        // Update ans with shifted temp
        ans = temp.map(row => [...row]);
    }

    // Compare final matrix with original
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (ans[i][j] !== mat[i][j]) return false;
        }
    }

    return true;
};

Matrix Similarity After Cyclic Shifts Complexity Analysis

Time Complexity: O(k × m × n)

Let's break down the time complexity of the brute-force solution step by step.

We perform k rounds of shifting, and in each round, we:

  • Traverse every element of the matrix.
  • Update each cell based on a modular index shift (either left or right).

Let’s define:

  • n = number of rows
  • m = number of columns
  • k = number of shift operations

We loop through each row (n rows), and for each row, we loop through each column (m columns). So:

  • Time per round = O(n × m)

We do this for k rounds, so total time:

  • Total Time = O(k × n × m)

At the end, we compare the final matrix with the original matrix element-by-element. That’s:

  • O(n × m) (just one final pass)

This doesn't change the overall time complexity since O(k × n × m) dominates.

Final Time Complexity: O(k × n × m)

Space Complexity: O(m × n)

  1. Auxiliary Space Complexity: O(1)
    The extra space used in the algorithm — like: loop counters i, j: loop counters,k: shift counter
    — are all primitive integer variables.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(m × n)
    We are working with a 2D input grid of size m × n, which is provided to us. However, during each shift, we also create a temporary grid temp of the same size to hold the intermediate result of one shift.So while we don’t use extra space that grows beyond m × n, we do use an additional grid of the same size.
    Therefore, the total space used in the process is:
  • One for the input grid → O(m × n)
  • One temporary grid temp → O(m × n)

But since we're not stacking these up, it's still considered linear in terms of the number of elements.

So, the total space complexity is O(m × n) due to the input grid.

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O(m × n × k), where:

  • m is the number of rows in the grid
  • n is the number of columns
  • k is the number of times we perform the shift operation

Given the constraints:

  • 1 ≤ m ≤ 25
  • 1 ≤ n ≤ 25
  • 1 ≤ k ≤ 50

In the worst-case scenario, this algorithm would perform up to:
O(25 × 25 × 50) = 31,250 operations

Even though this is a brute-force approach, the absolute number of operations — around a quarter million — is still well within the acceptable limits for most online judges, including LeetCode, which generally allows up to 10⁶ (1 million) operations per test case.

So, although this solution isn’t the most optimized in terms of time complexity, it performs efficiently in practice for the given constraints and is simple and easy to understand, making it a solid starting point.

How to optimize it?

In the brute-force approach, we are performing the shift operation k times, one step after another. For each row, depending on whether the row's index is even or odd, we either shift left (even-indexed rows) or shift right (odd-indexed rows). After performing these shifts for all k rounds, we compare the final matrix with the original one to check if they are identical.

The time complexity of this approach is O(m × n × k), where:

  • m is the number of rows,
  • n is the number of columns, and
  • k is the number of shifts.

This method works fine for small inputs but can become inefficient when k is large, especially because each shift operation requires looping over the entire matrix k times.

Matrix Similarity After Cyclic Shifts Algorithm

Instead of performing k individual shifts, where each shift involves looping through the entire row of the matrix m × n times, we can take advantage of the cyclic nature of shifting.

Cyclic nature of shifts: Shifting a row of size m by m times (or any multiple of m) brings the row back to its original position. So, shifting a row by k times is effectively the same as shifting by k % m times, because after m shifts, the row will return to its original form.

Instead of performing k shifts on each row, we can compute how many effective shifts we need (i.e., k % m) and apply that shift to each row directly. This reduces the number of operations we need to perform, making the solution faster and more efficient.

Example: Suppose you have a row of size 5 (i.e., m = 5) and you want to perform 12 shifts. Instead of shifting the row 12 times, notice that 12 % 5 = 2. This means that performing 12 shifts is the same as performing only 2 shifts. This dramatically reduces the number of operations, especially when k is large and m is small.

The idea now is to avoid shifting one element at a time for each of the k rounds. Instead, we can compute the total effective shift for each row and apply that shift all at once.

Let’s say we have the following matrix and k = 2.

mat = [
    [1, 2, 3],  // Row 0 (even index)
    [4, 5, 6],  // Row 1 (odd index)
    [7, 8, 9]   // Row 2 (even index)
]

We need to apply k = 2 shifts.

Step 1: Calculate effective shifts:

  • For a row of size m = 3, shifting by k = 2 is the same as shifting by k % 3 = 2 positions. This means each row will be shifted by 2 positions.

Step 2: Apply the shifts:

  • Row 0 (even-indexed): Perform a left shift by 2 positions. The elements in row 0 ([1, 2, 3]) will be rearranged as [3, 1, 2].
  • Row 1 (odd-indexed): Perform a right shift by 2 positions. The elements in row 1 ([4, 5, 6]) will be rearranged as [5, 6, 4].
  • Row 2 (even-indexed): Perform a left shift by 2 positions. The elements in row 2 ([7, 8, 9]) will be rearranged as [9, 7, 8].

Final result:

ans = [
    [3, 1, 2],  // Row 0 after left shift
    [5, 6, 4],  // Row 1 after right shift
    [9, 7, 8]   // Row 2 after left shift
]

Step 3: Compare the resulting matrix (ans) with the original matrix (mat) to determine if the matrix has returned to its original form after k shifts.

By using modulus operation, we can directly calculate how many shifts we actually need to perform, reducing unnecessary operations and making the algorithm faster.

Now that we understand the concept of effective shifts, we can proceed with the optimization. Instead of performing k individual shifts, we apply the shift directly by calculating the effective shifts.

Here’s how we can implement the logic:

  • For even-indexed rows (i % 2 == 0): We perform a left shift by k % m positions.
  • For odd-indexed rows (i % 2 != 0): We perform a right shift by k % m positions.

The logic works as follows:

  • Left shift for even-indexed rows: For each element in the row, we shift it k % m positions to the left. This can be achieved by using the formula (j + k % m) % m, which ensures that the shift wraps around properly.
  • Right shift for odd-indexed rows: For each element in the row, we shift it k % m positions to the right. The formula (j - k % m + m) % m handles the rightward shift, ensuring proper wrapping around if the index goes negative.

By applying the effective shift directly, we avoid repeating the shifting process k times.

In Conclusion:

  • Instead of performing k individual shifts, we reduce the number of shifts to k % n for each row, taking advantage of the cyclic behavior of shifts.
  • This approach ensures that we are not performing redundant shifts and reduces the total number of operations required, resulting in a much more efficient solution.

This optimized approach will run faster and perform well even with larger inputs, as we are effectively reducing the number of operations that we perform for each row.

Let us understand this with a video,

0:00
/0:52

Matrix Similarity After Cyclic Shifts Optimal Approach Animation

💡
Try it Yourself!

Let's understand with an example:

Matrix Similarity After Cyclic Shifts Example:

Input:

mat = [
[1, 2, 1, 2], // Row 0 (even-indexed)
[5, 5, 5, 5], // Row 1 (odd-indexed)
[6, 3, 6, 3] // Row 2 (even-indexed)
]

k = 2

Step 1: Calculate effective shifts

  • The matrix has 4 columns, so m = 4.
  • We need to calculate k % m = 2 % 4 = 2.

Thus, each row will be shifted by 2 positions (effective shifts).

Step 2: Apply the shifts

Row 0 (even-indexed):

  • Perform a left shift by 2 positions.
  • Original row: [1, 2, 1, 2]
  • After left shift by 2:
    New order: [1, 2, 1, 2] → [1, 2, 1, 2] (remains unchanged since it's a cyclic shift).

Row 1 (odd-indexed):

  • Perform a right shift by 2 positions.
  • Original row: [5, 5, 5, 5]
  • After right shift by 2:
    New order: [5, 5, 5, 5] → [5, 5, 5, 5] (remains unchanged due to identical elements).

Row 2 (even-indexed):

  • Perform a left shift by 2 positions.
  • Original row: [6, 3, 6, 3]
  • After left shift by 2:
    New order: [6, 3, 6, 3] → [6, 3, 6, 3] (remains unchanged).

Step 3: Final matrix

After applying the shifts, the matrix looks like this:

ans =
[
[1, 2, 1, 2], // Row 0 (unchanged)
[5, 5, 5, 5], // Row 1 (unchanged)
[6, 3, 6, 3] // Row 2 (unchanged)
]
Step 4: Compare with original matrix

Now, we compare the final matrix ans with the original matrix:

mat = [
[1, 2, 1, 2],
[5, 5, 5, 5],
[6, 3, 6, 3]
]

Since the final matrix is the same as the original matrix, the result is true.

How to code it up:

Step 1: Initialize the Matrix Dimensions

  • Get the number of rows n and columns m from the matrix mat.

Step 2: Create the Answer Matrix

  • Create a new matrix ans that will store the result after performing the shifts on the matrix mat. Initialize ans as a copy of mat.

Step 3: Apply the Shifts

  • Loop through each row of the matrix:
    • For even-indexed rows (i.e., rows 0, 2, 4, ...):
      • Perform a left cyclic shift by k positions.
      • For each element in the row, update it to the value that corresponds to (j + k) % m (where j is the index of the current element in the row).
    • For odd-indexed rows (i.e., rows 1, 3, 5, ...):
      • Perform a right cyclic shift by k positions.
      • For each element in the row, update it to the value that corresponds to (j - k % m + m) % m to ensure the right shift wraps around correctly.

Step 4: Compare the Final Matrix with Original

  • After performing the shifts, compare the modified matrix ans with the original matrix mat.
  • If they are identical, return true; otherwise, return false.

Matrix Similarity After Cyclic Shifts Solution

Code Implementation / Leetcode Solution of Matrix Similarity After Cyclic Shifts
1. Matrix Similarity After Cyclic Shifts solution in C++ Try on Compiler 
class Solution {
public:
    // Function to check if matrix is similar after k shifts
    bool areSimilar(vector<vector<int>>& mat, int k) {
        // Get the number of rows in the matrix
        int n = mat.size();
        
        // Get the number of columns in the matrix
        int m = mat[0].size();

        // Initialize the answer matrix as a copy of the original matrix
        vector<vector<int>> ans = mat;

        // Loop through each row in the matrix
        for(int i = 0; i < n; i++) {
            // Check if the row is even-indexed
            if(i % 2 == 0) {
                // Perform a left cyclic shift for even-indexed rows
                for(int j = 0; j < m; j++) {
                    // Shift the element to the left by k positions
                    ans[i][j] = mat[i][(j + k) % m];
                }
            } else {
                // Perform a right cyclic shift for odd-indexed rows
                for(int j = 0; j < m; j++) {
                    // Shift the element to the right by k positions
                    ans[i][j] = mat[i][(j - k % m + m) % m];
                }
            }
        }

        // Compare the final matrix with the original matrix and return the result
        return ans == mat;
    }
};

2. Matrix Similarity After Cyclic Shifts solution in Java Try on Compiler 
class Solution {
    public boolean areSimilar(int[][] mat, int k) {
        // Get the number of rows in the matrix
        int n = mat.length;
        
        // Get the number of columns in the matrix
        int m = mat[0].length;

        // Initialize the answer matrix as a copy of the original matrix
        int[][] ans = new int[n][m];
        for (int i = 0; i < n; i++) {
            System.arraycopy(mat[i], 0, ans[i], 0, m);
        }

        // Loop through each row in the matrix
        for (int i = 0; i < n; i++) {
            // Check if the row is even-indexed
            if (i % 2 == 0) {
                // Perform a left cyclic shift for even-indexed rows
                for (int j = 0; j < m; j++) {
                    ans[i][j] = mat[i][(j + k) % m];
                }
            } else {
                // Perform a right cyclic shift for odd-indexed rows
                for (int j = 0; j < m; j++) {
                    ans[i][j] = mat[i][(j - k % m + m) % m];
                }
            }
        }

        // Compare the final matrix with the original matrix and return the result
        return Arrays.deepEquals(ans, mat);
    }
}

3. Matrix Similarity After Cyclic Shifts solution in Python Try on Compiler 
class Solution:
    def areSimilar(self, mat, k):
        # Get the number of rows in the matrix
        n = len(mat)
        
        # Get the number of columns in the matrix
        m = len(mat[0])

        # Initialize the answer matrix as a copy of the original matrix
        ans = [row[:] for row in mat]

        # Loop through each row in the matrix
        for i in range(n):
            # Check if the row is even-indexed
            if i % 2 == 0:
                # Perform a left cyclic shift for even-indexed rows
                for j in range(m):
                    ans[i][j] = mat[i][(j + k) % m]
            else:
                # Perform a right cyclic shift for odd-indexed rows
                for j in range(m):
                    ans[i][j] = mat[i][(j - k % m + m) % m]

        # Compare the final matrix with the original matrix and return the result
        return ans == mat

4. Matrix Similarity After Cyclic Shifts solution in Javascript Try on Compiler 
var areSimilar = function(mat, k) {

    /// Get the number of rows in the matrix
    const n = mat.length;
    
    // Get the number of columns in the matrix
    const m = mat[0].length;

    // Initialize the answer matrix as a copy of the original matrix
    const ans = mat.map(row => row.slice());

    // Loop through each row in the matrix
    for (let i = 0; i < n; i++) {
        // Check if the row is even-indexed
        if (i % 2 === 0) {
            // Perform a left cyclic shift for even-indexed rows
            for (let j = 0; j < m; j++) {
                ans[i][j] = mat[i][(j + k) % m];
            }
        } else {
            // Perform a right cyclic shift for odd-indexed rows
            for (let j = 0; j < m; j++) {
                ans[i][j] = mat[i][(j - k % m + m) % m];
            }
        }
    }
    
    // Compare final matrix with original
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (ans[i][j] !== mat[i][j]) return false;
        }
    }

    return true;
};

Matrix Similarity After Cyclic Shifts Complexity Analysis

Time Complexity: O(n × m)

Let's break down the time complexity of the optimized approach that you've implemented. We'll analyze it step by step:

  1. Initializing the Answer Matrix:
    • The matrix ans is a copy of the original matrix mat.
    • This involves copying each element from mat to ans, which requires O(n * m) time, where n is the number of rows and m is the number of columns in the matrix.
  3. Looping Through Rows:Since we do this for each of the n rows, and each operation inside the row is O(m), the total time complexity for shifting all rows is O(n * m).
    • We loop through all n rows of the matrix (from 0 to n-1). This is a O(n) operation.
    • For each row:
      • Even-indexed rows (0, 2, 4, ...): We perform a left shift by k positions, which involves O(m) operations for each element in the row. So, for each even-indexed row, the time complexity is O(m).
      • Odd-indexed rows (1, 3, 5, ...): We perform a right shift by k positions, which also involves O(m) operations for each element in the row.
  5. Comparison:
    • Finally, we compare the modified matrix ans with the original matrix mat.
    • The comparison involves checking each element of the n x m matrix. This takes O(n * m) time.

Total Time Complexity:

Now, summing up all the operations:

  • O(n * m) for copying the matrix.
  • O(n * m) for applying the shifts to each row.
  • O(n * m) for comparing the final result with the original matrix.

Thus, the total time complexity is:

O(n * m)

Where:

  • n is the number of rows in the matrix.
  • m is the number of columns in the matrix.

Space Complexity: O(n × m)

  1. Auxiliary Space Complexity: O(n × m)
    We create a new 2D result grid (ans) of the same size as the input matrix to store the final shifted values. Since this grid has the same dimensions as the original matrix (n × m), the space used by ans is O(n × m).
  2. Total Space Complexity: O(n × m)
    The total space complexity is O(n × m) because we construct a new grid of the same size as the input to hold the shifted values. No additional space beyond that is used significantly.
    Therefore, the total space complexity is O(n × m).

Similar Problems

In programming, manipulating an array is a fundamental task that often requires performing various operations, such as shifting or rotating elements. This is especially common when working with matrices, which are essentially 2D arrays. Matrix manipulation can simulate real-world scenarios where data needs to be transformed or adjusted repeatedly. These simulations help solve complex problems efficiently, whether it's through simple operations or more advanced techniques that optimize performance.

Now that we have successfully tackled this problem, let's try similar problems.

1. Shift 2D Grid

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].

Element at grid[i][n - 1] moves to grid[i + 1][0].

Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

2. Equal Row and Column Pairs

Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8