algoadvance

Leetcode 2946. Matrix Similarity After Cyclic Shifts

Problem Statement

Given two matrices, matrixA and matrixB, return the minimum number of cyclic shifts needed to make matrixA identical to matrixB if possible. If it is not possible to make them identical with any number of cyclic shifts, return -1.

A cyclic shift is defined as shifting all elements of a row or a column to the left or up by one position in a circular manner (elements that move out from one end reappear on the opposite end).

Constraints:

  1. The elements of the matrices are integers.
  2. The matrices matrixA and matrixB are of the same size (m x n).

Clarifying Questions

  1. Cyclic Shifts Definition: Are we allowed to perform cyclic shifts on both rows and columns?
    • Yes, you can perform cyclic shifts on both rows and columns.
  2. Cyclic Shifts Direction: Should the shifts be only to the left for rows and up for columns, or can they include right and down as well?
    • You can consider left and up shifts primarily, and you can calculate the corresponding right and down shifts based on wrap-around properties.
  3. Matrix Dimensions: Should we assume that matrices are always non-empty?
    • Yes, you can assume the matrices are always non-empty and of the same dimensions.
  4. Range of Elements: Is there any constraint on the range of matrix elements?
    • No specific constraint provided, assume standard integer ranges.

Strategy

  1. Row and Column Shifts: Determine the number of cyclic shifts required for each row and column separately to align matrixA with matrixB.

  2. Check Feasibility: If aligning any row or column requires a different number of shifts than other rows or columns, return -1.

  3. Shift Calculation: Calculate and track the shifts required and find the minimum number of shifts.

Steps:

  1. For each row in matrixA, determine how many cyclic shifts would be required for it to match the corresponding row in matrixB.
  2. Similarly, for columns, determine the cyclic shifts needed.
  3. Verify if the shifts are consistent across rows and columns.
  4. Return the minimum number of shifts required if possible.

Code

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minimumShiftsToMakeIdentical(vector<vector<int>>& matrixA, vector<vector<int>>& matrixB) {
        int m = matrixA.size();
        int n = matrixA[0].size();

        // Check if cyclic shifts are same for rows
        for (int i = 0; i < m; i++) {
            vector<int> shifts;
            for (int shift = 0; shift < n; shift++) {
                if (isRowEqual(matrixA[i], matrixB[i], shift)) {
                    shifts.push_back(shift);
                }
            }
            if (shifts.empty()) return -1;
        }

        // Check if cyclic shifts are same for columns
        for (int j = 0; j < n; j++) {
            vector<int> shifts;
            for (int shift = 0; shift < m; shift++) {
                if (isColumnEqual(matrixA, matrixB, j, shift)) {
                    shifts.push_back(shift);
                }
            }
            if (shifts.empty()) return -1;
        }

        // Calculate minimum shifts (minimal intersection for both row and column shifts)
        int minShift = INT_MAX;
        for (int rowShift = 0; rowShift < n; rowShift++) {
            for (int colShift = 0; colShift < m; colShift++) {
                if (isMatrixEqualAfterShift(matrixA, matrixB, rowShift, colShift)) {
                    minShift = min(minShift, rowShift + colShift);
                }
            }
        }
        
        return minShift == INT_MAX ? -1 : minShift;
    }

private:
    bool isRowEqual(const vector<int>& rowA, const vector<int>& rowB, int shift) {
        int n = rowA.size();
        for (int i = 0; i < n; i++) {
            if (rowA[i] != rowB[(i + shift) % n]) {
                return false;
            }
        }
        return true;
    }

    bool isColumnEqual(const vector<vector<int>>& matrixA, const vector<vector<int>>& matrixB, int col, int shift) {
        int m = matrixA.size();
        for (int i = 0; i < m; i++) {
            if (matrixA[i][col] != matrixB[(i + shift) % m][col]) {
                return false;
            }
        }
        return true;
    }

    bool isMatrixEqualAfterShift(const vector<vector<int>>& matrixA, const vector<vector<int>>& matrixB, int rowShift, int colShift) {
        int m = matrixA.size();
        int n = matrixA[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrixA[i][j] != matrixB[(i + rowShift) % m][(j + colShift) % n]) {
                    return false;
                }
            }
        }
        return true;
    }
};

Time Complexity

This ensures that we efficiently check possible shifts and determine the minimal necessary shifts or return -1 if it’s not feasible.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI