Sponsored
Sponsored
By considering identical or opposite binary patterns within rows, the task reduces to finding the maximum similar pattern. If row 'A' can be made equal to row 'B', they must have the same or opposite pattern for all columns.
Time Complexity: O(m * m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the transformation key.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int transform(int* row, int* pattern, int n) {
6 int key[n];
7 for (int i = 0; i < n; ++i) {
8 key[i] = (row[i] == pattern[i]) ? 0 : 1;
9 }
10 return key;
11}
12
13int maxEqualRowsAfterFlips(int** matrix, int matrixSize, int* matrixColSize) {
14 int n = *matrixColSize;
15 int maxEqualRows = 0;
16
17 for (int i = 0; i < matrixSize; ++i) {
18 int* currPattern = matrix[i];
19
20 int count = 0;
21 for (int j = 0; j < matrixSize; ++j) {
22 int match = 1;
23 for (int k = 0; k < n; ++k) {
24 if ((matrix[j][k] == currPattern[k]) != (matrix[0][k] == currPattern[k])) {
25 match = 0;
26 break;
27 }
28 }
29 if (match) count++;
30 }
31 if (count > maxEqualRows) {
32 maxEqualRows = count;
33 }
34 }
35 return maxEqualRows;
36}Transform each row into a consistent pattern using a reference row and check for identical transformations. The transformation involves flipping columns only when required to match the pattern.
This alternative method evaluates each row by considering both its native and entirely flipped transformations, tallying frequency counts using these dual patterns in order to discover the maximal frequency count of equivalent rows.
Time Complexity: O(m * n), Space Complexity: Usage is reduced because of the hash bucket with a distant hash-field.
1#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
unordered_map<string, int> patternCount;
for (auto& row : matrix) {
string original(row.size(), '0');
for (int j = 0; j < row.size(); j++)
original[j] = (row[j] == 1) ? '1' : '0';
patternCount[original]++;
string rev(row.size(), '0');
for (int j = 0; j < row.size(); j++)
rev[j] = (row[j] == 0) ? '1' : '0';
patternCount[rev]++;
}
int maxEqualRows = 0;
for (const auto& p : patternCount) {
maxEqualRows = max(maxEqualRows, p.second);
}
return maxEqualRows;
}With original and reversed patterns accounted utilizing an unordered_map, diversification of representation finds the top quantity by which any row's pattern can be referred. Simple mapping permits direct pattern comparison.