Facebook Pixel

2158. Amount of New Area Painted Each Day 🔒

HardSegment TreeArrayOrdered Set
Leetcode Link

Problem Description

You have a long painting represented as a number line that needs to be painted over multiple days. You're given a 2D array paint where each element paint[i] = [start_i, end_i] represents the painting task for day i. On day i, you need to paint the area from position start_i to position end_i (exclusive of end_i).

The key constraint is that each area of the painting should be painted at most once to avoid creating an uneven painting. If an area has already been painted on a previous day, you should not paint it again.

Your task is to return an array worklog where worklog[i] represents the amount of new area that was actually painted on day i. This means if some portions of the range [start_i, end_i] were already painted on previous days, you only count the unpainted portions.

For example, if on day 0 you paint [1, 4] (painting 3 units), and on day 1 you need to paint [3, 6], you would only paint the new area [4, 6] (2 units) since [3, 4] was already painted on day 0.

The solution uses a Segment Tree data structure to efficiently track which areas have been painted and to calculate the amount of new area painted each day. The segment tree maintains information about painted intervals and allows for efficient range updates and queries to determine how much of a given range is already painted.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The core challenge is tracking which parts of the painting have already been painted across multiple days. We need to efficiently determine for each new painting task how much of it overlaps with already-painted areas.

A naive approach would be to maintain a boolean array marking each position as painted or unpainted. For each day, we'd iterate through the range and count unpainted positions, then mark them as painted. However, this becomes inefficient when dealing with large ranges, potentially requiring O(n * range_size) operations.

The key insight is that we're dealing with interval operations - we need to mark entire ranges as "painted" and query how much of a range is already painted. This naturally leads us to consider data structures optimized for range operations.

A Segment Tree is perfect for this scenario because it excels at:

  1. Range Updates: Marking an entire interval [start, end] as painted in O(log n) time
  2. Range Queries: Checking how much of an interval is already painted in O(log n) time

The solution maintains a segment tree where each node stores how much of its range is painted. When we process a painting task for day i:

  • First, we query the range [start, end] to find out how much is already painted
  • The new area painted = total range size - already painted area
  • Then we update the segment tree to mark the entire range as painted

The lazy propagation technique in the segment tree ensures we don't unnecessarily update all affected nodes immediately, making the solution more efficient. The add field in each node acts as a lazy flag indicating that the entire subtree should be marked as painted when needed.

By transforming the problem into range query and update operations, we achieve an efficient O(n log m) solution where n is the number of painting tasks and m is the range of coordinates.

Learn more about Segment Tree patterns.

Solution Approach

The solution implements a Segment Tree with lazy propagation to efficiently handle range updates and queries. Let's walk through the implementation step by step:

Segment Tree Structure

The Node class represents each node in the segment tree:

  • l, r: The left and right boundaries of the interval this node represents
  • mid: The midpoint, calculated as (l + r) >> 1 (bitwise right shift for division by 2)
  • v: The count of painted units in this node's range
  • add: Lazy propagation flag (1 if the entire range should be marked as painted)

Core Operations

1. Tree Initialization

self.root = Node(1, 10**5 + 10)

Creates a root node covering the range [1, 100010], which accommodates all possible painting positions.

2. Query Operation (query(l, r))

  • Returns the number of already-painted units in range [l, r]
  • If the current node's range is completely within [l, r], return node.v
  • Otherwise, push down lazy updates and recursively query left and right children
  • Sum up the results from both subtrees

3. Modify Operation (modify(l, r, v))

  • Marks the range [l, r] as painted
  • If the current node's range is completely within [l, r], mark the entire range as painted:
    • Set node.v = node.r - node.l + 1 (all units in range are painted)
    • Set node.add = 1 (lazy flag for children)
  • Otherwise, push down lazy updates and recursively modify appropriate children
  • Update current node's value based on children (pushup)

4. Lazy Propagation

  • pushdown: Creates children nodes if they don't exist and propagates the lazy flag
    • If node.add = 1, mark both children as fully painted
    • Clear the parent's lazy flag after propagation
  • pushup: Updates parent node's painted count as sum of children's counts

Main Algorithm

For each painting task [start, end]:

  1. Adjust coordinates: l = start + 1, r = end (shifting to 1-indexed)
  2. Query how many units in [l, r] are already painted: v = tree.query(l, r)
  3. Calculate new area painted: r - l + 1 - v (total range size minus already painted)
  4. Mark the entire range as painted: tree.modify(l, r, 1)
  5. Add the new painted area to the result

Time Complexity

  • Each query and modify operation: O(log m) where m is the coordinate range
  • Total for n painting tasks: O(n log m)

Space Complexity

  • O(m) for the segment tree nodes created on demand through lazy initialization

The elegance of this solution lies in using lazy propagation to avoid unnecessary updates - we only create and update nodes when actually needed, making it both time and space efficient.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with paint = [[1, 4], [3, 6], [2, 5]].

Initial State:

  • Segment tree covers range [1, 100010], all unpainted (v = 0)
  • Result array: []

Day 0: Paint [1, 4]

  • Convert to 1-indexed: query and modify range [2, 4]
  • Query [2, 4]: Returns 0 (nothing painted yet)
  • New area painted: (4 - 2 + 1) - 0 = 3 units
  • Modify [2, 4]: Mark positions 2, 3, 4 as painted
  • Tree state: Range [2, 4] has v = 3
  • Result: [3]

Day 1: Paint [3, 6]

  • Convert to 1-indexed: query and modify range [4, 6]
  • Query [4, 6]:
    • Check overlap with already painted [2, 4]
    • Position 4 is painted, positions 5, 6 are not
    • Returns 1 (one unit already painted)
  • New area painted: (6 - 4 + 1) - 1 = 2 units
  • Modify [4, 6]: Mark entire range as painted (4 already was, 5 and 6 newly painted)
  • Tree state: [2, 4] has v = 3, [5, 6] has v = 2 (internally merged as [2, 6] with v = 5)
  • Result: [3, 2]

Day 2: Paint [2, 5]

  • Convert to 1-indexed: query and modify range [3, 5]
  • Query [3, 5]:
    • Positions 3, 4, 5 are all already painted (from days 0 and 1)
    • Returns 3 (all three units already painted)
  • New area painted: (5 - 3 + 1) - 3 = 0 units
  • Modify [3, 5]: No actual change since already painted
  • Result: [3, 2, 0]

Final Output: [3, 2, 0]

The segment tree efficiently tracks painted intervals:

  • Day 0: Painted 3 new units
  • Day 1: Painted 2 new units (skipping the 1 overlapping unit)
  • Day 2: Painted 0 new units (entire range already covered)

Solution Implementation

1from typing import List, Optional
2
3
4class Node:
5    """Represents a node in the segment tree."""
6  
7    def __init__(self, left_bound: int, right_bound: int):
8        """
9        Initialize a segment tree node.
10      
11        Args:
12            left_bound: Left boundary of the interval this node represents
13            right_bound: Right boundary of the interval this node represents
14        """
15        self.left_child: Optional[Node] = None
16        self.right_child: Optional[Node] = None
17        self.left_bound = left_bound
18        self.right_bound = right_bound
19        self.mid = (left_bound + right_bound) >> 1  # Midpoint for splitting
20        self.painted_count = 0  # Number of painted cells in this interval
21        self.lazy_tag = 0  # Lazy propagation tag (1 if entire interval should be painted)
22
23
24class SegmentTree:
25    """Dynamic segment tree for tracking painted intervals."""
26  
27    def __init__(self):
28        """Initialize segment tree with range [1, 100010]."""
29        self.root = Node(1, 100010)
30  
31    def modify(self, left: int, right: int, value: int, node: Optional[Node] = None) -> None:
32        """
33        Mark interval [left, right] as painted.
34      
35        Args:
36            left: Left boundary of interval to paint
37            right: Right boundary of interval to paint
38            value: Value to set (1 for painted)
39            node: Current node in recursion (defaults to root)
40        """
41        if left > right:
42            return
43          
44        if node is None:
45            node = self.root
46          
47        # If current node's interval is completely covered by [left, right]
48        if node.left_bound >= left and node.right_bound <= right:
49            # Mark entire interval as painted
50            node.painted_count = node.right_bound - node.left_bound + 1
51            node.lazy_tag = value
52            return
53          
54        # Push down lazy updates before recursing
55        self.pushdown(node)
56      
57        # Recursively update left and right children
58        if left <= node.mid:
59            self.modify(left, right, value, node.left_child)
60        if right > node.mid:
61            self.modify(left, right, value, node.right_child)
62          
63        # Update current node's value based on children
64        self.pushup(node)
65  
66    def query(self, left: int, right: int, node: Optional[Node] = None) -> int:
67        """
68        Query number of painted cells in interval [left, right].
69      
70        Args:
71            left: Left boundary of query interval
72            right: Right boundary of query interval
73            node: Current node in recursion (defaults to root)
74          
75        Returns:
76            Number of painted cells in the queried interval
77        """
78        if left > right:
79            return 0
80          
81        if node is None:
82            node = self.root
83          
84        # If current node's interval is completely covered by query range
85        if node.left_bound >= left and node.right_bound <= right:
86            return node.painted_count
87          
88        # Push down lazy updates before querying children
89        self.pushdown(node)
90      
91        # Query left and right children
92        painted_cells = 0
93        if left <= node.mid:
94            painted_cells += self.query(left, right, node.left_child)
95        if right > node.mid:
96            painted_cells += self.query(left, right, node.right_child)
97          
98        return painted_cells
99  
100    def pushup(self, node: Node) -> None:
101        """
102        Update parent node's value based on children's values.
103      
104        Args:
105            node: Node to update based on its children
106        """
107        node.painted_count = node.left_child.painted_count + node.right_child.painted_count
108  
109    def pushdown(self, node: Node) -> None:
110        """
111        Push lazy updates from parent to children (lazy propagation).
112      
113        Args:
114            node: Node whose lazy updates need to be pushed to children
115        """
116        # Create children nodes if they don't exist (dynamic segment tree)
117        if node.left_child is None:
118            node.left_child = Node(node.left_bound, node.mid)
119        if node.right_child is None:
120            node.right_child = Node(node.mid + 1, node.right_bound)
121          
122        # If there's a lazy update to push down
123        if node.lazy_tag:
124            left_child = node.left_child
125            right_child = node.right_child
126          
127            # Mark children's entire intervals as painted
128            left_child.painted_count = left_child.right_bound - left_child.left_bound + 1
129            right_child.painted_count = right_child.right_bound - right_child.left_bound + 1
130          
131            # Propagate lazy tag to children
132            left_child.lazy_tag = node.lazy_tag
133            right_child.lazy_tag = node.lazy_tag
134          
135            # Clear parent's lazy tag
136            node.lazy_tag = 0
137
138
139class Solution:
140    def amountPainted(self, paint: List[List[int]]) -> List[int]:
141        """
142        Calculate amount of new area painted for each paint operation.
143      
144        Args:
145            paint: List of [start, end) intervals to paint
146          
147        Returns:
148            List where each element is the amount of new area painted
149        """
150        tree = SegmentTree()
151        result = []
152      
153        for start, end in paint:
154            # Convert to 1-indexed closed interval [left, right]
155            left, right = start + 1, end
156          
157            # Query how many cells are already painted
158            already_painted = tree.query(left, right)
159          
160            # Calculate newly painted cells
161            newly_painted = (right - left + 1) - already_painted
162            result.append(newly_painted)
163          
164            # Mark the interval as painted
165            tree.modify(left, right, 1)
166          
167        return result
168
1/**
2 * Node class representing a node in the segment tree
3 * Each node maintains information about a range [l, r]
4 */
5class Node {
6    Node left;          // Left child node
7    Node right;         // Right child node
8    int l;              // Left boundary of the range
9    int r;              // Right boundary of the range
10    int mid;            // Midpoint of the range
11    int v;              // Value stored in this node (count of painted segments)
12    int add;            // Lazy propagation flag (1 if entire range is painted, 0 otherwise)
13
14    /**
15     * Constructor to create a node with range [l, r]
16     * @param l left boundary
17     * @param r right boundary
18     */
19    public Node(int l, int r) {
20        this.l = l;
21        this.r = r;
22        this.mid = (l + r) >> 1;  // Calculate midpoint using bit shift (equivalent to division by 2)
23    }
24}
25
26/**
27 * Segment Tree implementation with lazy propagation
28 * Used to efficiently track painted ranges and query unpainted segments
29 */
30class SegmentTree {
31    private Node root = new Node(1, 100010);  // Root node covering range [1, 100010]
32
33    /**
34     * Default constructor
35     */
36    public SegmentTree() {
37    }
38
39    /**
40     * Public method to modify (paint) a range [l, r] with value v
41     * @param l left boundary of range to paint
42     * @param r right boundary of range to paint
43     * @param v value to set (1 for painted)
44     */
45    public void modify(int l, int r, int v) {
46        modify(l, r, v, root);
47    }
48
49    /**
50     * Private recursive method to modify a range in the segment tree
51     * @param l left boundary of range to modify
52     * @param r right boundary of range to modify
53     * @param v value to set
54     * @param node current node being processed
55     */
56    public void modify(int l, int r, int v, Node node) {
57        // Base case: invalid range
58        if (l > r) {
59            return;
60        }
61      
62        // If current node's range is completely within [l, r]
63        if (node.l >= l && node.r <= r) {
64            // Mark entire range as painted
65            node.v = node.r - node.l + 1;  // Set value to range size
66            node.add = v;                   // Set lazy propagation flag
67            return;
68        }
69      
70        // Push down lazy updates to children
71        pushdown(node);
72      
73        // Recursively modify left subtree if needed
74        if (l <= node.mid) {
75            modify(l, r, v, node.left);
76        }
77      
78        // Recursively modify right subtree if needed
79        if (r > node.mid) {
80            modify(l, r, v, node.right);
81        }
82      
83        // Update current node's value based on children
84        pushup(node);
85    }
86
87    /**
88     * Public method to query the count of painted segments in range [l, r]
89     * @param l left boundary of query range
90     * @param r right boundary of query range
91     * @return count of painted segments in the range
92     */
93    public int query(int l, int r) {
94        return query(l, r, root);
95    }
96
97    /**
98     * Private recursive method to query a range in the segment tree
99     * @param l left boundary of query range
100     * @param r right boundary of query range
101     * @param node current node being processed
102     * @return count of painted segments in the range
103     */
104    public int query(int l, int r, Node node) {
105        // Base case: invalid range
106        if (l > r) {
107            return 0;
108        }
109      
110        // If current node's range is completely within [l, r]
111        if (node.l >= l && node.r <= r) {
112            return node.v;  // Return the stored value
113        }
114      
115        // Push down lazy updates to children
116        pushdown(node);
117      
118        int totalPainted = 0;
119      
120        // Query left subtree if needed
121        if (l <= node.mid) {
122            totalPainted += query(l, r, node.left);
123        }
124      
125        // Query right subtree if needed
126        if (r > node.mid) {
127            totalPainted += query(l, r, node.right);
128        }
129      
130        return totalPainted;
131    }
132
133    /**
134     * Push up operation: update parent node's value based on children
135     * @param node parent node to update
136     */
137    public void pushup(Node node) {
138        node.v = node.left.v + node.right.v;  // Sum of left and right children values
139    }
140
141    /**
142     * Push down operation: propagate lazy updates to children
143     * Creates children nodes if they don't exist and applies pending updates
144     * @param node parent node with pending updates
145     */
146    public void pushdown(Node node) {
147        // Create left child if it doesn't exist
148        if (node.left == null) {
149            node.left = new Node(node.l, node.mid);
150        }
151      
152        // Create right child if it doesn't exist
153        if (node.right == null) {
154            node.right = new Node(node.mid + 1, node.r);
155        }
156      
157        // If there's a pending update, propagate it to children
158        if (node.add != 0) {
159            Node leftChild = node.left;
160            Node rightChild = node.right;
161          
162            // Apply update to left child
163            leftChild.add = node.add;
164            leftChild.v = leftChild.r - leftChild.l + 1;  // Mark entire range as painted
165          
166            // Apply update to right child
167            rightChild.add = node.add;
168            rightChild.v = rightChild.r - rightChild.l + 1;  // Mark entire range as painted
169          
170            // Clear parent's lazy flag
171            node.add = 0;
172        }
173    }
174}
175
176/**
177 * Solution class for the amount painted problem
178 */
179class Solution {
180    /**
181     * Calculate the amount of new area painted by each paint operation
182     * @param paint array of paint operations, where paint[i] = [start, end)
183     * @return array where ans[i] is the amount of new area painted by operation i
184     */
185    public int[] amountPainted(int[][] paint) {
186        SegmentTree tree = new SegmentTree();
187        int n = paint.length;
188        int[] ans = new int[n];
189      
190        for (int i = 0; i < n; ++i) {
191            // Convert to 1-indexed range [l, r] (inclusive)
192            int l = paint[i][0] + 1;
193            int r = paint[i][1];
194          
195            // Query how many segments are already painted
196            int alreadyPainted = tree.query(l, r);
197          
198            // Calculate newly painted segments
199            ans[i] = r - l + 1 - alreadyPainted;
200          
201            // Mark the range as painted
202            tree.modify(l, r, 1);
203        }
204      
205        return ans;
206    }
207}
208
1class Node {
2public:
3    Node* left;
4    Node* right;
5    int rangeLeft;     // Left boundary of the range this node represents
6    int rangeRight;    // Right boundary of the range this node represents
7    int rangeMid;      // Midpoint of the range for splitting
8    int paintedCount;  // Number of painted units in this range
9    int lazyTag;       // Lazy propagation tag (1 if entire range should be painted)
10
11    Node(int l, int r) {
12        this->rangeLeft = l;
13        this->rangeRight = r;
14        this->rangeMid = (l + r) >> 1;  // Equivalent to (l + r) / 2
15        this->left = this->right = nullptr;
16        paintedCount = lazyTag = 0;
17    }
18};
19
20class SegmentTree {
21private:
22    Node* root;
23
24public:
25    // Initialize segment tree with range [1, 100010]
26    SegmentTree() {
27        root = new Node(1, 100010);
28    }
29
30    // Public interface for range modification
31    void modify(int l, int r, int v) {
32        modify(l, r, v, root);
33    }
34
35    // Recursively modify range [l, r] with value v
36    void modify(int l, int r, int v, Node* node) {
37        if (l > r) return;
38      
39        // If current node's range is completely within [l, r]
40        if (node->rangeLeft >= l && node->rangeRight <= r) {
41            // Mark entire range as painted
42            node->paintedCount = node->rangeRight - node->rangeLeft + 1;
43            node->lazyTag = v;
44            return;
45        }
46      
47        // Push down lazy tag to children before continuing
48        pushdown(node);
49      
50        // Recursively modify left and right subtrees if they overlap with [l, r]
51        if (l <= node->rangeMid) {
52            modify(l, r, v, node->left);
53        }
54        if (r > node->rangeMid) {
55            modify(l, r, v, node->right);
56        }
57      
58        // Update current node's value based on children
59        pushup(node);
60    }
61
62    // Public interface for range query
63    int query(int l, int r) {
64        return query(l, r, root);
65    }
66
67    // Recursively query the number of painted units in range [l, r]
68    int query(int l, int r, Node* node) {
69        if (l > r) return 0;
70      
71        // If current node's range is completely within [l, r]
72        if (node->rangeLeft >= l && node->rangeRight <= r) {
73            return node->paintedCount;
74        }
75      
76        // Push down lazy tag to children before querying
77        pushdown(node);
78      
79        int totalPainted = 0;
80        // Query left subtree if it overlaps with [l, r]
81        if (l <= node->rangeMid) {
82            totalPainted += query(l, r, node->left);
83        }
84        // Query right subtree if it overlaps with [l, r]
85        if (r > node->rangeMid) {
86            totalPainted += query(l, r, node->right);
87        }
88      
89        return totalPainted;
90    }
91
92    // Update parent node's value based on children's values
93    void pushup(Node* node) {
94        node->paintedCount = node->left->paintedCount + node->right->paintedCount;
95    }
96
97    // Push lazy tag down to children and create children nodes if necessary
98    void pushdown(Node* node) {
99        // Create children nodes dynamically if they don't exist
100        if (!node->left) {
101            node->left = new Node(node->rangeLeft, node->rangeMid);
102        }
103        if (!node->right) {
104            node->right = new Node(node->rangeMid + 1, node->rangeRight);
105        }
106      
107        // If there's a lazy tag, propagate it to children
108        if (node->lazyTag) {
109            Node* leftChild = node->left;
110            Node* rightChild = node->right;
111          
112            // Mark children's entire ranges as painted
113            leftChild->paintedCount = leftChild->rangeRight - leftChild->rangeLeft + 1;
114            rightChild->paintedCount = rightChild->rangeRight - rightChild->rangeLeft + 1;
115          
116            // Pass down the lazy tag
117            leftChild->lazyTag = node->lazyTag;
118            rightChild->lazyTag = node->lazyTag;
119          
120            // Clear current node's lazy tag
121            node->lazyTag = 0;
122        }
123    }
124};
125
126class Solution {
127public:
128    vector<int> amountPainted(vector<vector<int>>& paint) {
129        int n = paint.size();
130        vector<int> ans(n);
131        SegmentTree* tree = new SegmentTree();
132      
133        // Process each paint operation
134        for (int i = 0; i < n; ++i) {
135            // Adjust range: add 1 to left boundary for 1-indexed segment tree
136            int left = paint[i][0] + 1;
137            int right = paint[i][1];
138          
139            // Query how many units are already painted in this range
140            int alreadyPainted = tree->query(left, right);
141          
142            // Calculate newly painted units
143            ans[i] = right - left + 1 - alreadyPainted;
144          
145            // Mark the range as painted in the segment tree
146            tree->modify(left, right, 1);
147        }
148      
149        return ans;
150    }
151};
152
1class TreeNode {
2    left: TreeNode | null;
3    right: TreeNode | null;
4    rangeLeft: number;     // Left boundary of the range this node represents
5    rangeRight: number;    // Right boundary of the range this node represents
6    rangeMid: number;      // Midpoint of the range for splitting
7    paintedCount: number;  // Number of painted units in this range
8    lazyTag: number;       // Lazy propagation tag (1 if entire range should be painted)
9
10    constructor(l: number, r: number) {
11        this.rangeLeft = l;
12        this.rangeRight = r;
13        this.rangeMid = Math.floor((l + r) / 2);  // Midpoint for range splitting
14        this.left = null;
15        this.right = null;
16        this.paintedCount = 0;
17        this.lazyTag = 0;
18    }
19}
20
21// Global variable for segment tree root
22let segmentTreeRoot: TreeNode | null = null;
23
24// Initialize segment tree with range [1, 100010]
25function initializeSegmentTree(): void {
26    segmentTreeRoot = new TreeNode(1, 100010);
27}
28
29// Public interface for range modification
30function modifyRange(l: number, r: number, v: number): void {
31    if (segmentTreeRoot) {
32        modifyRangeRecursive(l, r, v, segmentTreeRoot);
33    }
34}
35
36// Recursively modify range [l, r] with value v
37function modifyRangeRecursive(l: number, r: number, v: number, node: TreeNode): void {
38    if (l > r) return;
39  
40    // If current node's range is completely within [l, r]
41    if (node.rangeLeft >= l && node.rangeRight <= r) {
42        // Mark entire range as painted
43        node.paintedCount = node.rangeRight - node.rangeLeft + 1;
44        node.lazyTag = v;
45        return;
46    }
47  
48    // Push down lazy tag to children before continuing
49    pushDownLazyTag(node);
50  
51    // Recursively modify left and right subtrees if they overlap with [l, r]
52    if (l <= node.rangeMid && node.left) {
53        modifyRangeRecursive(l, r, v, node.left);
54    }
55    if (r > node.rangeMid && node.right) {
56        modifyRangeRecursive(l, r, v, node.right);
57    }
58  
59    // Update current node's value based on children
60    pushUpValues(node);
61}
62
63// Public interface for range query
64function queryRange(l: number, r: number): number {
65    if (segmentTreeRoot) {
66        return queryRangeRecursive(l, r, segmentTreeRoot);
67    }
68    return 0;
69}
70
71// Recursively query the number of painted units in range [l, r]
72function queryRangeRecursive(l: number, r: number, node: TreeNode): number {
73    if (l > r) return 0;
74  
75    // If current node's range is completely within [l, r]
76    if (node.rangeLeft >= l && node.rangeRight <= r) {
77        return node.paintedCount;
78    }
79  
80    // Push down lazy tag to children before querying
81    pushDownLazyTag(node);
82  
83    let totalPainted = 0;
84    // Query left subtree if it overlaps with [l, r]
85    if (l <= node.rangeMid && node.left) {
86        totalPainted += queryRangeRecursive(l, r, node.left);
87    }
88    // Query right subtree if it overlaps with [l, r]
89    if (r > node.rangeMid && node.right) {
90        totalPainted += queryRangeRecursive(l, r, node.right);
91    }
92  
93    return totalPainted;
94}
95
96// Update parent node's value based on children's values
97function pushUpValues(node: TreeNode): void {
98    let leftCount = node.left ? node.left.paintedCount : 0;
99    let rightCount = node.right ? node.right.paintedCount : 0;
100    node.paintedCount = leftCount + rightCount;
101}
102
103// Push lazy tag down to children and create children nodes if necessary
104function pushDownLazyTag(node: TreeNode): void {
105    // Create children nodes dynamically if they don't exist
106    if (!node.left) {
107        node.left = new TreeNode(node.rangeLeft, node.rangeMid);
108    }
109    if (!node.right) {
110        node.right = new TreeNode(node.rangeMid + 1, node.rangeRight);
111    }
112  
113    // If there's a lazy tag, propagate it to children
114    if (node.lazyTag) {
115        let leftChild = node.left;
116        let rightChild = node.right;
117      
118        // Mark children's entire ranges as painted
119        leftChild.paintedCount = leftChild.rangeRight - leftChild.rangeLeft + 1;
120        rightChild.paintedCount = rightChild.rangeRight - rightChild.rangeLeft + 1;
121      
122        // Pass down the lazy tag
123        leftChild.lazyTag = node.lazyTag;
124        rightChild.lazyTag = node.lazyTag;
125      
126        // Clear current node's lazy tag
127        node.lazyTag = 0;
128    }
129}
130
131function amountPainted(paint: number[][]): number[] {
132    const n = paint.length;
133    const ans: number[] = new Array(n);
134  
135    // Initialize the segment tree
136    initializeSegmentTree();
137  
138    // Process each paint operation
139    for (let i = 0; i < n; i++) {
140        // Adjust range: add 1 to left boundary for 1-indexed segment tree
141        const left = paint[i][0] + 1;
142        const right = paint[i][1];
143      
144        // Query how many units are already painted in this range
145        const alreadyPainted = queryRange(left, right);
146      
147        // Calculate newly painted units
148        ans[i] = right - left + 1 - alreadyPainted;
149      
150        // Mark the range as painted in the segment tree
151        modifyRange(left, right, 1);
152    }
153  
154    return ans;
155}
156

Time and Space Complexity

Time Complexity: O(n * log(M)) where n is the number of paint operations and M is the range size (10^5 in this case).

  • The SegmentTree is initialized with a range [1, 10^5 + 10], creating a root node in O(1) time.
  • For each paint operation in the list:
    • query(l, r): In the worst case, this traverses from root to leaves, creating nodes lazily along the path. The tree height is O(log M), so query takes O(log M) time.
    • modify(l, r, v): Similarly, this operation traverses the tree from root to potentially multiple leaves, taking O(log M) time.
  • Since we perform these operations for each of the n paint intervals, the total time complexity is O(n * log M).

Space Complexity: O(min(n * log(M), M))

  • The segment tree uses lazy propagation and dynamic node creation (nodes are only created when needed via pushdown).
  • In the worst case, if we need to access many different ranges, we could create up to O(M) nodes to cover the entire range.
  • However, since nodes are created lazily during the n operations, and each operation creates at most O(log M) nodes along its path, the space used is also bounded by O(n * log M).
  • Therefore, the space complexity is O(min(n * log(M), M)), which represents the minimum of the theoretical maximum nodes and the nodes actually created through operations.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Interval Conversion Between 0-indexed and 1-indexed Systems

The most common pitfall in this solution is mishandling the conversion between the problem's 0-indexed half-open intervals [start, end) and the segment tree's 1-indexed closed intervals [left, right].

The Pitfall:

# Incorrect conversions that often occur:
left, right = start, end - 1  # Wrong! Doesn't shift to 1-indexed
left, right = start + 1, end + 1  # Wrong! Over-shifts the right boundary
left, right = start, end  # Wrong! Uses 0-indexed directly

Why This Happens:

  • The problem uses [start, end) where end is exclusive (painting positions start to end-1)
  • The segment tree implementation uses 1-indexed closed intervals [left, right] where both boundaries are inclusive
  • The conversion requires both shifting indices by 1 AND adjusting for the exclusive/inclusive difference

The Correct Solution:

# Correct conversion:
left, right = start + 1, end

This works because:

  • start in 0-indexed becomes start + 1 in 1-indexed
  • end (exclusive) in 0-indexed becomes end (inclusive) in 1-indexed
  • Example: [0, 3) in problem space (painting positions 0, 1, 2) becomes [1, 3] in segment tree space

2. Segment Tree Range Initialization Too Small

The Pitfall:

# Wrong: Range too small for the problem constraints
self.root = Node(1, 10**4)  # May not cover all possible positions

The Solution:

# Correct: Ensure range covers all possible painting positions
self.root = Node(1, 100010)  # or Node(1, 10**5 + 10)

Always check the problem constraints and add a small buffer to avoid index out of bounds issues.

3. Forgetting to Handle Empty Intervals

The Pitfall: Not checking for invalid intervals where left > right after conversion can cause incorrect results or infinite recursion.

The Solution:

def modify(self, left: int, right: int, value: int, node: Optional[Node] = None) -> None:
    if left > right:  # Critical check
        return
    # ... rest of the code

4. Misunderstanding Lazy Propagation Logic

The Pitfall:

# Wrong: Forgetting to clear the parent's lazy tag after propagation
def pushdown(self, node: Node) -> None:
    if node.lazy_tag:
        # ... propagate to children
        # Forgot: node.lazy_tag = 0  # This line is crucial!

Why This Matters: Without clearing the parent's lazy tag, the same update gets applied multiple times on subsequent operations, leading to incorrect painted counts.

The Solution: Always clear the parent's lazy tag after propagating it to children to prevent duplicate updates.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More