[Python] Evolving Linear-time Sweep (3 Approaches), The Best
Intuition\nApproach 1: Sort the queries, then for each result row scan the queries and maintain a min-heap of query right columns. This puts the solution in slo
# Intuition\nApproach 1: Sort the queries, then for each result row scan the queries and maintain a min-heap of query right columns. This puts the solution in slowest 5%, narrowly avoiding TLE.\n\nApproach 2: Get rid of sorting and min-heap, and instead scan the queries for each row, adding $$1$$ at left column and $$-1$$ after right column. Then, recreate the result of previous approach by scanning each row. This puts the solution at roughly top 33%\u201350% running time.\n\nApproach 3: Instead of scanning queries per row, scan them once, adding $$1$$ at first row and $$-1$$ below last row. Then, recreate the prerequisites of previous approach by scanning each column. This puts the solution at top 5% running time.\n\nFinal variation: Compactify code lines a bit at some expense of running time. :)\n\nThe Best!\n\n# Complexity\n- Time complexity: $$O(n^2+m)$$\n- Space complexity: $$O(1)$$ extra space\n\n# Code\nApproach 1: $$O(n^2+nm\\log m)$$ / $$O(m)$$\n```py\ndef rangeAddQueries(self, n: int, queries: list[list[int]]) -> list[list[int]]:\n    queries.sort(key=lambda q: q[1])\n    res, qlen = [[0]*n for row in range(n)], len(queries)\n    for row in range(n):\n        ends, qidx = [], 0\n        for col in range(n):\n            while qidx < qlen and col == queries[qidx][1]:\n                (r1, c1, r2, c2), qidx = queries[qidx], qidx+1\n                if r1 <= row <= r2:\n                    heapq.heappush(ends, c2)\n            while ends and col > ends[0]:\n                heapq.heappop(ends)\n            res[row][col] = len(ends)\n    return res\n```\n\nApproach 2: $$O(n^2 + nm)$$ / $$O(1)$$\n```py\ndef rangeAddQueries(self, n: int, queries: list[list[int]]) -> list[list[int]]:\n    res = [[0]*n for row in range(n)]\n    for r1, c1, r2, c2 in queries:\n        for row in range(r1, r2+1):\n            res[row][c1] += 1\n        if c2 != n-1:\n            for row in range(r1, r2+1):\n                res[row][c2+1] -= 1\n    for row in range(n):\n        ins = 0\n        for col in range(n):\n            res[row][col] = ins = ins + res[row][col]\n    return res\n```\n\nApproach 3: $$O(n^2+m)$$ / $$O(1)$$\n```py\ndef rangeAddQueries(self, n: int, queries: list[list[int]]) -> list[list[int]]:\n    res = [[0]*n for row in range(n)]\n    for r1, c1, r2, c2 in queries:\n        res[r1][c1] += 1\n        if c2 != n-1:\n            res[r1][c2+1] -= 1\n        if r2 != n-1:\n            res[r2+1][c1] -= 1\n            if c2 != n-1:\n                res[r2+1][c2+1] += 1\n    for row in range(n):\n        for col in range(n):\n            res[row][col] += res[row-1][col] if row else 0\n    for row in range(n):\n        for col in range(n):\n            res[row][col] += res[row][col-1] if col else 0\n    return res\n```\n\nFinal variation: $$O(n^2+m)$$ / $$O(1)$$\n```py\ndef rangeAddQueries(self, n: int, queries: list[list[int]]) -> list[list[int]]:\n    res = [[0]*n for row in range(n)]\n    for r1, c1, r2, c2 in queries:\n        res[r1][c1] += 1\n        res[r1][min(c2+1, n-1)] -= c2 != n-1\n        res[min(r2+1, n-1)][c1] -= r2 != n-1\n        res[min(r2+1, n-1)][min(c2+1, n-1)] += max(r2, c2) != n-1\n    for row in range(n):\n        for col in range(n):\n            res[row][col] += res[row-1][col] if row else 0\n    for row in range(n):\n        for col in range(n):\n            res[row][col] += res[row][col-1] if col else 0\n    return res\n```
['Python3']