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

  • 0

    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]:
                    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

Log in to reply

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