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 <vector>
2#include <unordered_map>
3#include <algorithm>
4using namespace std;
5
6int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
7 unordered_map<string, int> patternCount;
8 for (auto& row : matrix) {
9 string base(row.size(), '0');
10 for (int j = 0; j < row.size(); ++j) {
11 base[j] = row[j] == row[0] ? '0' : '1';
12 }
13 patternCount[base]++;
14 }
15 int maxEqualRows = 0;
16 for (auto& [pattern, count] : patternCount) {
17 maxEqualRows = max(maxEqualRows, count);
18 }
19 return maxEqualRows;
20}Utilize a hashmap to store identical patterns derived from each row in comparison to a canonical form. The canonical version is created by treating each row's entries as a transformation of the leading element in that row.
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.
This approach introduces a hashing mechanism to efficiently count the occurrences of different row patterns. Two interpretations, original and flipped, are hashed for each row, then comparison pairs are reduced via a single pass lookup.