SDE - Intern

Brute Force Approach (Recursive Approach):
Since we are given a binary matrix of size N × M and an integer K, we maintain all possible combinations (as strings) of length M whose values sum to K.

For example, for the matrix [[1, 0, 1], [1, 1, 1], [1, 0, 1]] and K = 3, one possible combination could be 111, 102, 120, etc. We iterate over all the generated combination values, which represent the number of times each specific column is toggled. In each iteration, we maintain the maximum number of 1’s in any row, l_max, and update g_max = max(g_max, l_max), where g_max represents the global maximum number of 1’s in a row. We repeat these steps for all possible combinations to get the final answer.

Optimal Approach (Greedy + Hash Map Based Approach):
We take advantage of the fact that identical rows remain the same after performing K operations on columns (regardless of which columns).

Step 1: Create a hashmap to store the count of each identical row.
For example, for [[1, 0, 1], [1, 1, 1], [1, 0, 1]], the hashmap will look like:
101 -> 2, 111 -> 1

Step 2: Iterate over the hashmap and count the number of zeroes in each row. If the number of zeroes <= K and (K - number_of_zeroes) % 2 == 0, then it is possible to convert that row into all 1’s. Update g_max with map[key].

Explanation of the conditions:

The first condition is straightforward: to convert a row to all 1’s, the number of zeroes must be less than or equal to K.

Performing an operation twice on the same column nullifies its effect. That is why the second condition (K - number_of_zeroes) % 2 == 0 is necessary.

Since changing the links alone won’t work, the only way is to swap the node’s value with the next adjacent node’s value and then perform the normal deletion operation in the linked list.

I was explaining the standard Fenwick Tree code.