Problem Statement:

You can simply apply area of histogram concept here.

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 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.

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

Since the solution has already been mentioned, I thought that these two links might be useful if you haven't done the problems yet:

Largest rectangle in histogram: LeetCode

Maximal rectangle: LeetCode

The second problem is almost the same as this one, but it should work almost the same, just need to add the areas instead

I think I have an $$$\mathcal{O}(nm)$$$ solution.

First, calculate $$$\operatorname{down}_{i,j}$$$ — the number of $$$1$$$ down you can go from position $$$(i, j)$$$ before reaching a zero. Note that if position $$$(i, j)$$$ is a zero, then $$$\operatorname{down}_{i,j} = 0$$$. To calculate this, if the entry at position $$$(i-1, j)$$$ is a $$$1$$$ then $$$\operatorname{down}_{i,j} = \operatorname{down}_{i-1,j} - 1$$$. Otherwise, you can calculate it naively by iterating down.

Next, iterate one row at a time. For each row, let's consider a rectangle with the top edge as $$$(i, l) \implies (i, r)$$$ ($$$1 \le l \le r \le m$$$). The number of rectangles we can form with this as the top edge is $$$\min\limits_{l \le j \le r}{\operatorname{down}_{i,j}}$$$ in this range.

This reduces the problem to finding $$$\sum\limits_{1 \le l \le r \le m}{\bigl(\min\limits_{l \le j \le r}{\operatorname{down}_{i,j}}\bigr)}$$$. To solve this, let's use a monotonic stack to find $$$\operatorname{left}_{i,j}$$$ and $$$\operatorname{right}_{i,j}$$$ for each position. The former is the next earlier index on the same row with a strictly lower $$$\operatorname{down}_{i,j}$$$ value. The latter is the next later index on the same row with a lower or equal $$$\operatorname{down}_{i,j}$$$ value. Then the contribution of each position is $$$(j - \operatorname{left}_{i,j}) \cdot (\operatorname{right}_{i,j} - j) \cdot \operatorname{down}_{i,j}$$$.

That solves the entire problem in $$$\mathcal{O}(nm)$$$... I think. If I've done something wrong, let me know.