Jobs

Interviews

Discussions

Matrix Similarity After Cyclic Shifts

Easy

Asked by:

23 views

Topics:

Arrays

You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.

The following proccess 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.

Example 1:

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).

Example 2:

Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2

Output: true

Explanation:

Example 3:

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

Try coding it in LeetCode

Matrix Similarity After Cyclic Shifts

Easy

Asked by:

23 views

Topics:

Arrays

You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.

The following proccess 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.

Example 1:

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).

Example 2:

Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2

Output: true

Explanation:

Example 3:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix and what are the upper and lower bounds on the integer values within the matrix?
Is an empty matrix or a matrix with only one row considered similar?
If the matrix cannot be made similar through cyclic shifts, what should I return?
Are we only concerned with cyclic shifts within a single row, or can we also cyclically shift entire columns?
Can I assume that all rows in the matrix have the same number of columns?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible way to shift each row of the matrix. We generate all possible shifted versions of each row and then compare the matrix with all these shifted combinations to see if any are similar.

Here's how the algorithm would work step-by-step:

For each row in the matrix, create all the different versions you can get by shifting the elements around like a carousel.
Think of the first row and take it as is, then shift it to the left by one position, then by two positions, and so on, until you've tried every possible shift.
Do the same thing for the second row, and for all other rows.
Now, you have a collection of possibilities for each row.
Take one possibility for the first row, one possibility for the second row, and so on, and put them together to create a new complete matrix.
Compare this newly created matrix with the original matrix. If they're similar according to the rules of the problem, you've found a solution.
Keep doing this, trying every single combination of shifted rows, until you either find a similar matrix or you've exhausted all the possibilities.

Code Implementation

def are_matrices_similar_brute_force(matrix_a, matrix_b):
    number_of_rows = len(matrix_a)
    number_of_columns = len(matrix_a[0])

    def shift_row(row, shift_amount):
        shifted_row = row[:] # Create a copy to avoid modifying the original
        for i in range(shift_amount):
            last_element = shifted_row.pop()
            shifted_row.insert(0, last_element)
        return shifted_row

    def compare_matrices(matrix_one, matrix_two):
        for row_index in range(number_of_rows):
            if matrix_one[row_index] != matrix_two[row_index]:
                return False
        return True

    # Generate all possible shift combinations.
    shift_combinations = []

    def generate_combinations(current_combination, row_index):
        if row_index == number_of_rows:
            shift_combinations.append(current_combination[:])
            return

        for shift_amount in range(number_of_columns):
            current_combination.append(shift_amount)
            generate_combinations(current_combination, row_index + 1)
            current_combination.pop()

    generate_combinations([], 0)

    # Iterate through shift combinations and apply shifts
    for shift_combination in shift_combinations:

        # Apply shifts to matrix_a
        shifted_matrix = []
        for row_index in range(number_of_rows):
            shifted_row = shift_row(matrix_a[row_index], shift_combination[row_index])
            shifted_matrix.append(shifted_row)

        # Compare shifted_matrix with matrix_b
        if compare_matrices(shifted_matrix, matrix_b):
            # Matrices are similar after shifts
            return True

    # No shift combination resulted in similar matrices
    return False

Big(O) Analysis

Time Complexity

O(n^(m+1)) – Let n be the number of columns in the matrix and m be the number of rows. For each of the m rows, we generate n shifted versions. This results in n^m possible combinations of shifted rows. For each of these n^m matrix combinations, we compare it to the original matrix, which takes O(n*m) time. Therefore the overall time complexity is O(n^m * n*m) which can be simplified to O(m*n^(m+1)). However since m is a constant, the time complexity can be expressed as O(n^(m+1)).

Space Complexity

O(N^2) – The algorithm generates all possible shifted versions of each row. For an N x N matrix, each row can be shifted N times, resulting in N shifted versions. Storing these shifted versions requires creating new lists, potentially leading to an auxiliary space of N * N = N^2. This auxiliary space is utilized to hold all possible matrix configurations during the comparison process as the algorithm explores various combinations of shifted rows. Therefore, the space complexity is O(N^2).

Optimal Solution

Approach

We're trying to see if two sets of rows from two matrices are essentially the same, even if one set is shifted. The clever approach is to combine each row with itself, and then check if any row from the second matrix exists within this combined row.

Here's how the algorithm would work step-by-step:

For each row in the first matrix, make a new, longer row by attaching the original row to the end of itself. This creates a string where every possible shift is present.
For each row in the second matrix, check if that row is contained within any of the combined, doubled rows from the first matrix.
If you find a match for every row in the second matrix, then the two matrices are considered similar after shifts.

Code Implementation

def are_matrices_similar(matrix_one, matrix_two):
    number_of_rows = len(matrix_one)
    number_of_columns = len(matrix_one[0])

    # Ensure matrices have the same dimensions.
    if number_of_rows != len(matrix_two) or number_of_columns != len(matrix_two[0]):
        return False

    for row_index in range(number_of_rows):
        first_matrix_row = matrix_one[row_index]
        second_matrix_row = matrix_two[row_index]

        # Create a doubled string to check for rotation.
        concatenated_row = first_matrix_row + first_matrix_row

        # Check if the second row is a substring of the doubled first row.
        is_rotation_found = False
        for start_index in range(len(concatenated_row) - number_of_columns + 1):
            if concatenated_row[start_index:start_index + number_of_columns] == second_matrix_row:
                is_rotation_found = True
                break

        # If any row isn't a rotation, matrices aren't similar.
        if not is_rotation_found:
            return False

    return True

Big(O) Analysis

Time Complexity

O(m*n*k) – Let 'm' be the number of rows in the second matrix, 'n' be the number of rows in the first matrix, and 'k' be the number of columns in both matrices. The outer loop iterates 'm' times (rows in the second matrix). Inside, there's a loop that iterates 'n' times (rows in the first matrix). For each row in the second matrix, we perform a substring search within the doubled row from the first matrix. Substring search typically takes O(k) time because we are comparing the row from the second matrix of length k against a doubled row of length 2k. Thus, the total time complexity is approximately m * n * k, which simplifies to O(m*n*k).

Space Complexity

O(N) – The dominant space usage comes from creating the doubled rows. For each of the M rows in the first matrix, a new row of length 2*N is created, where N is the number of columns in the matrix. While we are only storing one doubled row at a time, in the worst case, the space to store the doubled row will require 2*N space to store the row which contributes to auxiliary space usage. Thus, the overall auxiliary space complexity is O(N) where N is the number of columns.

Edge Cases

Case	How to Handle
matrix is null or empty	Return true, as an empty matrix can be considered to have all rows equal.
matrix contains an empty row	Treat an empty row as equal to other rows if all rows are empty, otherwise determine similarity based on non-empty rows only.
matrix has only one row	Return true, as a single row is trivially similar to itself.
All rows are identical	Return true, as the matrix is already similar.
Rows have different lengths	Return false, as cyclic shifts cannot make rows of different lengths equal.
No solution exists (rows are fundamentally different)	The core logic should return false when no cyclic shift aligns the rows.
Large matrix with very long rows (performance)	Ensure the shift comparison logic is efficient (e.g., using string matching or optimized comparison).
Integer overflow during comparisons if values are large	Use appropriate data types or comparison methods to prevent overflow, if comparing sums or products.

matrix is null or empty

How to Handle:

Return true, as an empty matrix can be considered to have all rows equal.

matrix contains an empty row

How to Handle:

Treat an empty row as equal to other rows if all rows are empty, otherwise determine similarity based on non-empty rows only.

matrix has only one row

How to Handle:

Return true, as a single row is trivially similar to itself.

All rows are identical

How to Handle:

Return true, as the matrix is already similar.

Rows have different lengths

How to Handle:

Return false, as cyclic shifts cannot make rows of different lengths equal.

No solution exists (rows are fundamentally different)

How to Handle:

The core logic should return false when no cyclic shift aligns the rows.

Large matrix with very long rows (performance)

How to Handle:

Ensure the shift comparison logic is efficient (e.g., using string matching or optimized comparison).

Integer overflow during comparisons if values are large

How to Handle:

Use appropriate data types or comparison methods to prevent overflow, if comparing sums or products.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix and what are the upper and lower bounds on the integer values within the matrix?
Is an empty matrix or a matrix with only one row considered similar?
If the matrix cannot be made similar through cyclic shifts, what should I return?
Are we only concerned with cyclic shifts within a single row, or can we also cyclically shift entire columns?
Can I assume that all rows in the matrix have the same number of columns?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For each row in the matrix, create all the different versions you can get by shifting the elements around like a carousel.
Think of the first row and take it as is, then shift it to the left by one position, then by two positions, and so on, until you've tried every possible shift.
Do the same thing for the second row, and for all other rows.
Now, you have a collection of possibilities for each row.
Take one possibility for the first row, one possibility for the second row, and so on, and put them together to create a new complete matrix.
Compare this newly created matrix with the original matrix. If they're similar according to the rules of the problem, you've found a solution.
Keep doing this, trying every single combination of shifted rows, until you either find a similar matrix or you've exhausted all the possibilities.

Code Implementation

def are_matrices_similar_brute_force(matrix_a, matrix_b):
    number_of_rows = len(matrix_a)
    number_of_columns = len(matrix_a[0])

    def shift_row(row, shift_amount):
        shifted_row = row[:] # Create a copy to avoid modifying the original
        for i in range(shift_amount):
            last_element = shifted_row.pop()
            shifted_row.insert(0, last_element)
        return shifted_row

    def compare_matrices(matrix_one, matrix_two):
        for row_index in range(number_of_rows):
            if matrix_one[row_index] != matrix_two[row_index]:
                return False
        return True

    # Generate all possible shift combinations.
    shift_combinations = []

    def generate_combinations(current_combination, row_index):
        if row_index == number_of_rows:
            shift_combinations.append(current_combination[:])
            return

        for shift_amount in range(number_of_columns):
            current_combination.append(shift_amount)
            generate_combinations(current_combination, row_index + 1)
            current_combination.pop()

    generate_combinations([], 0)

    # Iterate through shift combinations and apply shifts
    for shift_combination in shift_combinations:

        # Apply shifts to matrix_a
        shifted_matrix = []
        for row_index in range(number_of_rows):
            shifted_row = shift_row(matrix_a[row_index], shift_combination[row_index])
            shifted_matrix.append(shifted_row)

        # Compare shifted_matrix with matrix_b
        if compare_matrices(shifted_matrix, matrix_b):
            # Matrices are similar after shifts
            return True

    # No shift combination resulted in similar matrices
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

For each row in the first matrix, make a new, longer row by attaching the original row to the end of itself. This creates a string where every possible shift is present.
For each row in the second matrix, check if that row is contained within any of the combined, doubled rows from the first matrix.
If you find a match for every row in the second matrix, then the two matrices are considered similar after shifts.

Code Implementation

def are_matrices_similar(matrix_one, matrix_two):
    number_of_rows = len(matrix_one)
    number_of_columns = len(matrix_one[0])

    # Ensure matrices have the same dimensions.
    if number_of_rows != len(matrix_two) or number_of_columns != len(matrix_two[0]):
        return False

    for row_index in range(number_of_rows):
        first_matrix_row = matrix_one[row_index]
        second_matrix_row = matrix_two[row_index]

        # Create a doubled string to check for rotation.
        concatenated_row = first_matrix_row + first_matrix_row

        # Check if the second row is a substring of the doubled first row.
        is_rotation_found = False
        for start_index in range(len(concatenated_row) - number_of_columns + 1):
            if concatenated_row[start_index:start_index + number_of_columns] == second_matrix_row:
                is_rotation_found = True
                break

        # If any row isn't a rotation, matrices aren't similar.
        if not is_rotation_found:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
matrix is null or empty	Return true, as an empty matrix can be considered to have all rows equal.
matrix contains an empty row	Treat an empty row as equal to other rows if all rows are empty, otherwise determine similarity based on non-empty rows only.
matrix has only one row	Return true, as a single row is trivially similar to itself.
All rows are identical	Return true, as the matrix is already similar.
Rows have different lengths	Return false, as cyclic shifts cannot make rows of different lengths equal.
No solution exists (rows are fundamentally different)	The core logic should return false when no cyclic shift aligns the rows.
Large matrix with very long rows (performance)	Ensure the shift comparison logic is efficient (e.g., using string matching or optimized comparison).
Integer overflow during comparisons if values are large	Use appropriate data types or comparison methods to prevent overflow, if comparing sums or products.

matrix is null or empty

How to Handle:

Return true, as an empty matrix can be considered to have all rows equal.

matrix contains an empty row

How to Handle:

Treat an empty row as equal to other rows if all rows are empty, otherwise determine similarity based on non-empty rows only.

matrix has only one row

How to Handle:

Return true, as a single row is trivially similar to itself.

All rows are identical

How to Handle:

Return true, as the matrix is already similar.

Rows have different lengths

How to Handle:

Return false, as cyclic shifts cannot make rows of different lengths equal.

No solution exists (rows are fundamentally different)

How to Handle:

The core logic should return false when no cyclic shift aligns the rows.

Large matrix with very long rows (performance)

How to Handle:

Ensure the shift comparison logic is efficient (e.g., using string matching or optimized comparison).

Integer overflow during comparisons if values are large

How to Handle:

Use appropriate data types or comparison methods to prevent overflow, if comparing sums or products.