How hard is LeetCode 2158. Amount of New Area Painted Each Day?

LeetCode 2158. Amount of New Area Painted Each Day is rated Hard on LeetCode.

What topics does LeetCode 2158. Amount of New Area Painted Each Day cover?

LeetCode 2158. Amount of New Area Painted Each Day is tagged Segment Tree, Array and Ordered Set on LeetCode.

Is LeetCode 2158. Amount of New Area Painted Each Day a premium problem?

Yes. LeetCode 2158. Amount of New Area Painted Each Day is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Amount of New Area Painted Each Day — LeetCode 2158 Python Solution

HardLeetCode PremiumSegment TreeArrayOrdered Set

Problem: #2158
Reading time: 13 min
Source: leetcode.com

The problem

There is a long and thin painting that can be represented by a number line. You are given a 0-indexed 2D integer array paint of length n, where paint[i] = [starti, endi].

Example

Input: paint = [[1,4],[4,7],[5,8]]
Output: [3,3,1]
Explanation: On day 0, paint everything between 1 and 4.

Python solution

Python

class Node:
    def __init__(self, l, r):
        self.left = None
        self.right = None
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.v = 0
        self.add = 0


class SegmentTree:
    def __init__(self):
        self.root = Node(1, 10**5 + 10)

    def modify(self, l, r, v, node=None):
        if l > r:
            return
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            node.v = node.r - node.l + 1
            node.add = v
            return
        self.pushdown(node)
        if l <= node.mid:
            self.modify(l, r, v, node.left)
        if r > node.mid:
            self.modify(l, r, v, node.right)
        self.pushup(node)

    def query(self, l, r, node=None):
        if l > r:
            return 0
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            return node.v
        self.pushdown(node)
        v = 0
        if l <= node.mid:
            v += self.query(l, r, node.left)
        if r > node.mid:
            v += self.query(l, r, node.right)
        return v

    def pushup(self, node):
        node.v = node.left.v + node.right.v

    def pushdown(self, node):
        if node.left is None:
            node.left = Node(node.l, node.mid)
        if node.right is None:
            node.right = Node(node.mid + 1, node.r)
        if node.add:
            left, right = node.left, node.right
            left.v = left.r - left.l + 1
            right.v = right.r - right.l + 1
            left.add = node.add
            right.add = node.add
            node.add = 0


class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        tree = SegmentTree()
        ans = []
        for i, (start, end) in enumerate(paint):
            l, r = start + 1, end
            v = tree.query(l, r)
            ans.append(r - l + 1 - v)
            tree.modify(l, r, 1)
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(1) to O(n) auxiliary

Frequently asked questions

How hard is LeetCode 2158. Amount of New Area Painted Each Day?: LeetCode 2158. Amount of New Area Painted Each Day is rated Hard on LeetCode.
What topics does LeetCode 2158. Amount of New Area Painted Each Day cover?: LeetCode 2158. Amount of New Area Painted Each Day is tagged Segment Tree, Array and Ordered Set on LeetCode.
Is LeetCode 2158. Amount of New Area Painted Each Day a premium problem?: Yes. LeetCode 2158. Amount of New Area Painted Each Day is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.