Author: rakesh272611
Tester: varan245
Editorialist: rakesh272611
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Two Pointer, Binary Search
PROBLEM:
You are given a matrix of size NXM. You have to find the minimum value K such that, a special square submatrix of size K is possible.
A matrix is considered as special matrix, if the OR of all the elements of matrix is greater than r,
Print minimum value of K that satisfies this condition.
If there is no K that satisfies the condition then print -1.
EXPLANATION:
We have to find a minimum K such that there is a square submatrix of size K that is special. For that we will apply binary search on K and for each K we will check whether there exists a special matrix of size K or not.
We can do this by a Two pointer approach. First we will fix the window of size K in rows and then iterate over the column and check for every K column by two pointer.
After that we will shift the window to the next row and check for every K columns by two pointers again.
By this we can check for all the submatrix whose bitwise or is greater than r.
ALTERNATIVE IDEA:
Binary search on K and prefix bitwise sum to check if the submatrix is special or not.
First for every i,j in our matrix we compute pre[i][j][k] which denotes the count of k^{th} bit present in the submatrix starting from (0,0) to (i,j). To do that, we write
pre[i][j][k] = pre[i-1][j][k] + pre[i][j-1][k] - pre[i-1][j-1][k] (for fixed i,j 0<=k<=20)
Now as we iterate over the 2-D matrix, at some index (i,j) we can easily binary search on value of K (smallest special sub-matrix of size K ending at (i,j)) while checking if submatrix from (i-K,j-K) to (i,j) is special or not by using the prefix bitwise sum.
Kindly refer to the tester’s code to understand thoroughly.
TIME COMPLEXITY:
The time complexity for the problem is: O(N * M*log(min(N,M))*20)
SOLUTIONS:
Setter's Solution
Tester's Solution
Any other solution or feedback can be posted in the comments. We are always open for them.