gitgud

I don't know about G and Ex but for F I noticed two things.

For G, you can iterate over all pairs $$$(l, r)$$$ to consider all rectangles whose left column is $$$l$$$ and right column is $$$r$$$. Then, you can "compress" every row $$$i$$$ in this subgrid with two numbers: $$$sum_i$$$ (the sum of numbers in the i-th row) and $$$min_i$$$ (the minimum number in the i-th row). Both numbers can be preprocessed. Now your problem is: "given arrays $$$sum$$$ and $$$min$$$, what is the maximum value of (sum[l] + ... + sum[r]) * (min(min[l], ..., min[r])) over all possible pairs of $$$(l, r)$$$?". This can be solved with monotonic stack.

For Problem G,

We need to maximize the (sum of a rectangular region) * (minimum of that same region). Let's fix the minimum value(instead of going over all the cells) [Notice that 1 <= Ai <= 300].

For each minimum value mn_value we can generate a binary matrix, such that new_mat[i][j] = A[i][j] >= mn_value.

Now this problem reduces to finding the maximum area rectangle in new_mat which can be solved using the maximum area histogram as a subroutine with a slight modification. Using binary matrix we cannot obtain the actual sum of the rectangular region. So, for that prepare a prefix sum matrix and pass it to all the functions.

In the Largest rectangular histogram logic, when we are finding the maximum area, we can also find out the coordinates of the rectangle that produces the maximum area [Top left: (row - height + 1, pse + 1), Bottom right: (row, nse - 1)]. Since we know the coordinates of the rectangle, we can get the actual sum of that region from the Prefix Sum Matrix we created in O(1) time.

So, the time complexity of this solution is O(300 * n * m)

Subroutines used:

1. Previous Smaller Element (Using a Monotonic Stack)

2. Next Smaller Element (Using a Monotonic Stack)

3. Maximum Area Histogram (Using 1) and 2))

4. Largest Rectangular Area in a Binary Matrix (Using 3)

E was basically this, just the answer to be calculated changed.

The editorial seems to doubt that an $$$O(n^3 \log_2(n))$$$ solution could work, so $$$O(n^4)$$$ was probably unintended.

In addition, a solution akin to a finding the maximum-size rectangle in a histogram (bunch of stacks) can solve the problem without the constraint on $$$A$$$.

I am sending one leetcode problem link Count Squares.Hope you will understand from there and will able to debug your code.

Do a dfs from (2,2) and maintain a visited 2D array and move to that neighbour whichever has atleast one cell left unvisited.You can brute force to check the row or column have any unvisited cell or not.