Given binary matrix of size n*n, task is to find the count of rectangular sub-matrices with OR value 1. Try solving this without searching this on internet. What is the best time complexity you could come up with? How much time did it take? What do you think is the difficulty level of this question?
O(n^2) worst case
Depends on if I am reading in the matrix or not and how it's provided You have to access every element anyway, so n^2 is the best you can do. The algorithm itself can run in order(total number of 1s), which you do by keeping a dict of previously seen 1s and calculating the total number of unique rectanges excluding any points you've seen so far. A easier way to do it if you aren't comfortable doing simple combinatorics on the fly is to create a cumulative matrix while you read in every element, and for every element >0 you add one to the counter, and do some math to count the other rectangles.. The algorithm is n^2, but if you have to read in the array from std it'll be faster than the combinatorics way. Math way took me 2 min, cumulative matrix way popped instantly. Probably a medium or easy on leetcode. It can become a hard depending on the modifications (online streaming 5 million ints without being given the dimensions of the matrix, etc)
Lol ibm
How about a matrix of 1000 by 1000 ?
i was recently asked this question..The matrix of 0 is always an rectangle, if present. complexity n^2.
Dp o(m*n) and o (m+1)
Correct me if I'm wrong, but as long as one vertex is a one, then you basically can create a rectangle with any other vertex. Then, you just need to dedupe if the other vertex is also 1.
Same technique as maximal square kinda
Would preprocessing the matrix to be a running OR help? Kind of like the question where you want to find sum of block with in a matrix. Though in this case to undo the over counting you use XOR rather than subtraction.
Maybe in O(N*M) by using dynamic programming where f(i, j) represents the number of rectangles having OR value 1 ending at i, j.
What is this “M”?
Assuming matrix of size N*M