I like to read this solution as a small machine: keep the useful information, throw away the noise. For 861. Score After Flipping Matrix, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, bit manipulation, greedy.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are toggle, matrixScore.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02We have a two dimensional matrix A where each value is 0 or 1.
03
04A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.
05
06After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.
07
08Return the highest possible score.
09
10
11
12Example 1:
13
14Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
15Output: 39
16Explanation:
17Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
180b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
19
20
21Note:
22
231 <= A.length <= 20
241 <= A[0].length <= 20
25A[i][j] is 0 or 1.
26**/
27
28//Your runtime beats 53.22 % of cpp submissions.
29class Solution {
30public:
31 static int toggle(int x){return 1-x;}
32 int matrixScore(vector<vector<int>>& A) {
33 int rows = A.size();
34 int cols = A[0].size();
35
36 //toggle a row when its first element is 0
37 for(int i = 0; i < rows; i++){
38 if(A[i][0]!=1){
39 //in-place map elements of v to the function toggle
40 transform(A[i].begin(), A[i].end(), A[i].begin(), toggle);
41 }
42 // copy(A[i].begin(), A[i].end(), ostream_iterator<int>(cout, " "));
43 // cout << endl;
44 }
45
46 int sum = 0;
47 //toggle columns and calculate the sum simultaneously
48 for(int j = 0; j < cols; j++){
49 int colSum = 0;
50 for(int i = 0; i < rows; i++){
51 colSum += A[i][j];
52 }
53 //toggle a column if toggling makes its sum bigger
54 //, i.e. the original sum <= A.size()/2
55 // cout << j << "'th colSum: " << colSum << ", rows/2: " << rows/2 << ", rows: " << rows << endl;
56 colSum = colSum <= rows/2 ? rows-colSum : colSum;
57 // cout << j << "'th colSum: " << colSum << ",shift: " << (cols-1-j) << ",final col sum: " << (colSum<<(cols-1-j)) << endl;
58 sum += colSum<<(cols-1-j);
59 }
60 return sum;
61 }
62};
63
64/**
65Approach 1: Brute Force
66Intuition
67
68Notice that a 1 in the iith column from the right, contributes 2^i2
69i
70 to the score.
71
72Say we are finished toggling the rows in some configuration. Then for each column, (to maximize the score), we'll toggle the column if it would increase the number of 1s.
73
74We can brute force over every possible way to toggle rows.
75
76Algorithm
77
78Say the matrix has R rows and C columns.
79
80For each state, the transition trans = state ^ (state-1) represents the rows that must be toggled to get into the state of toggled rows represented by (the bits of) state.
81
82We'll toggle them, and also maintain the correct column sums of the matrix on the side.
83
84Afterwards, we'll calculate the score. If for example the last column has a column sum of 3, then the score is max(3, R-3), where R-3 represents the score we get from toggling the last column.
85
86In general, the score is increased by max(col_sum, R - col_sum) * (1 << (C-1-c)), where the factor (1 << (C-1-c)) is the power of 2 that each 1 contributes.
87
88Note that this approach may not run in the time allotted.
89
90//Java
91class Solution {
92 public int matrixScore(int[][] A) {
93 int R = A.length, C = A[0].length;
94 int[] colsums = new int[C];
95 for (int r = 0; r < R; ++r)
96 for (int c = 0; c < C; ++c)
97 colsums[c] += A[r][c];
98
99 int ans = 0;
100 for (int state = 0; state < (1<<R); ++state) {
101 // Toggle the rows so that after, 'state' represents
102 // the toggled rows.
103 if (state > 0) {
104 int trans = state ^ (state-1);
105 for (int r = 0; r < R; ++r) {
106 if (((trans >> r) & 1) > 0) {
107 for (int c = 0; c < C; ++c) {
108 colsums[c] += A[r][c] == 1 ? -1 : 1;
109 A[r][c] ^= 1;
110 }
111 }
112 }
113 }
114
115 // Calculate the score with the rows toggled by 'state'
116 int score = 0;
117 for (int c = 0; c < C; ++c)
118 score += Math.max(colsums[c], R - colsums[c]) * (1 << (C-1-c));
119 ans = Math.max(ans, score);
120 }
121
122 return ans;
123 }
124}
125
126Complexity Analysis
127
128Time Complexity: O(2^R * R * C), where R, C is the number of rows and columns in the matrix.
129
130Space Complexity: O(C) in additional space complexity.
131
132**/
133
134/**
135Approach 2: Greedy
136Intuition
137
138Notice that a 1 in the iith column from the right, contributes 2^i to the score.
139
140Since 2^n > 2^{n-1} + 2^{n-2} + ... + 2^0,
141maximizing the left-most digit is more important than any other digit.
142Thus, the rows should be toggled such that the left-most column is either all 0 or all 1
143(so that after toggling the left-most column [if necessary], the left column is all 1.)
144
145Algorithm
146
147If we toggle rows by the first column (A[r][c] ^= A[r][0]), then the first column will be all 0.
148
149Afterwards, the base score is max(col, R - col) where col is the column sum;
150and (1 << (C-1-c)) is the power of 2 that each 1 in that column contributes to the score.
151
152//Your runtime beats 100.00 % of cpp submissions.
153class Solution {
154public:
155 int matrixScore(vector<vector<int>>& A) {
156 int R = A.size(), C = A[0].size();
157 int ans = 0;
158 for (int c = 0; c < C; ++c) {
159 int col = 0;
160 for (int r = 0; r < R; ++r){
161 // cout << "r: " << r << ", c: " << c << ", A[r][c] ^ A[r][0]: " << (A[r][c] ^ A[r][0]) << endl;
162 //toggle all rows to have 0 at head(we should toggle all rows' head to either 0 or 1)
163 //^:XOR, 0 if operands are the same, 1 if different
164 col += A[r][c] ^ A[r][0];
165 }
166 ans += max(col, R - col) * (1 << (C-1-c));
167 }
168 return ans;
169 }
170};
171
172Complexity Analysis
173
174Time Complexity: O(R∗C), R, C is the number of rows and columns in the matrix.
175
176Space Complexity: O(1) in additional space complexity.
177**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.