Leetcode: 2158. Amount of New Area Painted Each Day

Mistake: High constant factor in the implementation. Did not optimize when query an interval that was already full.
Blackbox: This is a variation of a classic problem: Segment Tree
Can we formulate the problem using a segment tree? Suppose we have a Lazy Segment Tree covering the full range (1 to \(10^5\)). The problem adding intervals to the segment tree while computing the number of new points covered. Time complexity is \(O(n \log m)\) with space \(O(min(m, n))\).

from typing import List


class SegTree:
    def __init__(self, left, right, count=0):
        self.left = left
        self.mid = left + (right - left) // 2
        self.right = right
        self.count = count
        self.left_child = self.right_child = None

    def add(self, left, right):
        if self.right < left or right < self.left:
            return 0
        if self.is_full() or left <= self.left <= self.right <= right:
            self.left_child = None
            self.right_child = None
            self.fill()
            return self.count
        self._extend()
        self.left_child.add(left, right)
        self.right_child.add(left, right)
        before = self.count
        after = self.count = self.left_child.count + self.right_child.count
        return after - before

    def is_full(self):
        return self.count == self.right - self.left + 1

    def fill(self):
        self.count = self.right - self.left + 1

    def _extend(self):
        if self.left_child is None and self.left < self.right:
            self.left_child = SegTree(self.left, self.mid)
            self.right_child = SegTree(self.mid + 1, self.right)
            if self.is_full():
                self.left_child.fill()
                self.right_child.fill()

    def _print(self, level=0):
        print(" " * level, (self.left, self.right), self.count)
        if self.left_child:
            self.left_child._print(level + 1)
            self.right_child._print(level + 1)


class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        st = SegTree(0, 50_000 + 1)
        ans = []
        for start, end in paint:
            ans.append(st.add(start, end - 1))
        return ans


assert Solution().amountPainted([[1, 4], [4, 7], [5, 8]]) == [3, 3, 1]
assert Solution().amountPainted([[1, 4], [5, 8], [4, 7]]) == [3, 3, 1]
assert Solution().amountPainted([[1, 5], [2, 4]]) == [4, 0]

Can we use brute-force to solve the problem? The brute-force means painting every single point and for that the answer is no. But we can improve on the brute-force algorithm by tracking the next possible empty cell using an array \(nxt\). While processing \(paint[i]\), we can set \(nxt[paint[i].start]=nxt[paint[i].start+1]=..=nxt[paint[i].end-1]=paint[i].end\). So, the next time that we reach any of those cells, we can jump directly to \(nxt[paint[i].end]\).

class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        N = len(paint)
        nxt = [None for i in range(50_001)]
        ans = []
        for start, end in paint:
            cur = 0
            while start < end:
                if nxt[start] is None:
                    nxt[start] = end
                    cur += 1
                    start += 1
                else:
                    nstart = nxt[start]
                    nxt[start] = max(nxt[start], end)
                    start = nstart
            ans.append(cur)
        return ans

Can we formulate the problem using graphs? The graph starts with \(m\) vertices and no edges. We process each paint on order and create the edges \((paint[i].start, paint[i].start+1), (paint[i].start+1, paint[i].start+2), ..., (paint[i].end-1, paint[i].end)\). While adding the edges to the graph, we keep track of the components created using Union-Find. Each component is rooted on the left-most position in the component. So, adding an edge \((u, u+1)\), we can jump to \(find(u+1)\) since it is the next available point to paint.

class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        N = len(paint)
        p = [i for i in range(50_001)]
        ans = []

        def find(a):
            if p[a] == a:
                return a
            p[a] = find(p[a])
            return p[a]

        def union(a, b):
            assert b > a
            pa = find(a)
            pb = find(b)
            p[pa] = pb
            return pb

        for start, end in paint:
            cur = 0
            start = find(start)
            while start < end:
                start = union(start, start + 1)
                cur += 1
            ans.append(cur)
        return ans