Hi everyone! I have an interesting problem for which I haven't devised a solution yet. Can you help me?
Problem Statement:
Imagine you have a 2D grid (with dimensions m×n), where each cell in the grid can either be 0 or 1. Your task is to count the number of rectangles (or submatrices) that are made entirely of 1's.
Constraint: mxn <= 1e6
Thanks for taking the time to read and help me!
You can simply apply area of histogram concept here.
So what you're gonna want to do is iterate through all possible lengths and widths of the rectangles. Let $$$l$$$ be the current length, and $$$w$$$ be the current width. $$$1 \le l \le n$$$ and $$$1 \le w \le m$$$. For each $$$(l, w)$$$ pair, iterate through all the possible rectangles in the grid with that length and width. For each one of these rectangles, what you're gonna wanna do is iterate through every element inside of it. If you find a $$$0$$$, break. Otherwise, add $$$1$$$ to your result. Time complexity should be $$$O(n^3m^3)$$$, which should comfortably pass.
Which year are you living in to have a comfort $$$\mathcal{O}(n^3 m^3)$$$ runtime for $$$nm \le 10^6$$$?
$$$nm \le 10^6$$$ does not imply that there must be a testcase where $$$nm = 10^6$$$
But if anyone added a testcase with $$$nm = 10^6$$$ to kill your petty solution, it wouldn't be against the rule, would it?
To be fair, I never said that my solution was deterministic.
I will do you the favor and cut your solution down to deterministic $$$O(n^2m^2)$$$ by ridding off the $$$0$$$ check with a 2D prefix sum. There.
If you feel this is still heuristics based on where the best rectangle could be, sure, the problem is there always existed a test to counter the way you iterate, and it can be done easily.
That is a nice optimization. I think that this problem is pretty similar. The idea is actually kind of cool.
Iterate over the grind and Make every 1 in the grid a top-left corner of a ractangle, then just calculate how far you can expand the rectangle, for this you can imagine the rectangle as a stack of lines:
1 1 1 1 1 1
1 1 1 1 0 0
1 1 1 1 0 0
1 1 1 0 0 0
1 1 0 0 0 0
1 0 0 0 0 0
The first line sets a upperbound, the next line cant be longer than the previous one, every line you add is size of the line extra number of rectangles, to see how long you can expand every line you can use some preffix array, complexity $$$O(m*n^2)$$$
A cheeky solution, but I don't think it will yet pass the TL.
First, create a 2D prefix sum to quickly count the amount of
1
s in any rectangle.WLOG:
1
s, and how far it could be extended downwards.From here:
Time complexity is $$$\mathcal{O}(nm^2)$$$, or if denoting $$$k = nm$$$, then we can write it as $$$\mathcal{O}(k \sqrt{k})$$$. Since it's around $$$10^9$$$, it could be pretty rough to fit TL, especially when $$$n$$$ and $$$m$$$ aren't too far apart.