# Python, O(nm^2) time, O(m^2) space, or O(n^3)/O(n^2) with optimization

• Explanation/solution below, but I have a BIG question about the asymptotic analysis on this. Since `m` is getting squared in our time/space complexity, we could guarantee that we make `m` the smaller of the width or height. If the width is smaller, we can do top-down as below. If the height is smaller, we could instead apply the same solution, but from left to right.

In extreme examples, this makes a huge difference. For example, a 100x2 grid would take 2 * 100^2 (or 20,000) iterations when done top-down, but would only take 100 * 2^2 (or 400) iterations when done left-to-right.

If we add a check to the solution below to always approach this the right way (top-down for narrow grids, left-right for wide grids), would it be an improvement to the asymptotic analysis? The new time/space complexity with that optimization would be...

Time: O(n^3), Space: O(n^2), where `n` is either the width or height of the grid, whichever is smaller.

Is this an asymptotically meaningful improvement?

Keep a record of the number of "top-left" and "top-right" pairs that have been seen already... then when we find another pair that matches on a lower row, that new pair completes a rectangle for every matching pair we've seen, so add that to the count.

``````class Solution(object):
def countCornerRectangles(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n, m = len(grid), len(grid[0])
count = 0
if n < 2 or m < 2:
return count
seen = {}
for row in range(n):
for col in range(m - 1):
if not grid[row][col]:
continue
for i in range(col + 1, m):
if grid[row][i]:
if (col, i) not in seen:
seen[(col, i)] = 0
count += seen[(col, i)]
seen[(col, i)] += 1
return count
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.