MinhBoss13's blog

Counting Rectangles of 1's in a Binary Grid
By MinhBoss13, history, 5 hours ago, In English

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!

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You can simply apply area of histogram concept here.

→ Reply
  • »
    »
    1 minute ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    brute forces with are can get tle

    → Reply
»
5 hours ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Which year are you living in to have a comfort $$$\mathcal{O}(n^3 m^3)$$$ runtime for $$$nm \le 10^6$$$?

    → Reply
    • »
      »
      »
      4 hours ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      $$$nm \le 10^6$$$ does not imply that there must be a testcase where $$$nm = 10^6$$$

      → Reply
      • »
        »
        »
        »
        4 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But if anyone added a testcase with $$$nm = 10^6$$$ to kill your petty solution, it wouldn't be against the rule, would it?

        → Reply
        • »
          »
          »
          »
          »
          4 hours ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          To be fair, I never said that my solution was deterministic.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 hours ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              That is a nice optimization. I think that this problem is pretty similar. The idea is actually kind of cool.

              → Reply
»
4 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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)$$$

→ Reply
»
3 hours ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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 1s in any rectangle.

WLOG:

  • We'll assume $$$n \ge m$$$. This way, $$$m \le \sqrt{nm} \le 10^3$$$.
  • We'll pick a subsegment specified by a range of columns, and then scan all the rows if that subsegment is full of 1s, and how far it could be extended downwards.

From here:

  • Pick a starting column $$$i$$$ ($$$1 \le i \le m$$$).
  • Pick an ending column $$$j$$$ ($$$i \le j \le m$$$).
  • Now, we have the segment specified by $$$[i, j]$$$ so that we would scan all the rows for that.
  • Think of it as a 1D array instead, we'll see this as a simple "find the longest contiguous subarray consisting of a single value". This can be done in linear complexity based on two-pointer technique.
  • Now, do the same in the scanning: with the specified $$$[i, j]$$$, iterate row $$$x$$$ in range $$$[1, n]$$$ as if you are doing a 1D array of size $$$n$$$.

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.

→ Reply
»
96 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Not sure if you know the problem of finding the maximum area of a rectangle that consists of all 1 in the 2D grid, but I think the solution should be pretty similar here, instead of taking the max, we should add the area of that rectangle to the sum

→ Reply