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]. This means that on the ith day you need to paint the area between starti and endi.

Painting the same area multiple times will create an uneven painting so you only want to paint each area of the painting at most once.

Return an integer array worklog of length n, where worklog[i] is the amount of new area that you painted on the ith day.

Examples

Example 1

 gantt
     title Painting representation across days
     dateFormat x
     axisFormat x
     section Day 0
     Paint (1-4): active, 1, 3
     section Day 1
     Paint (4-7): active, 4, 3
     section Day 2
     Paint (7-8): active, 7, 1
  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: paint = [[1,4],[4,7],[5,8]]
Output: [3,3,1]
Explanation:
On day 0, paint everything between 1 and 4.
The amount of new area painted on day 0 is 4 - 1 = 3.
On day 1, paint everything between 4 and 7.
The amount of new area painted on day 1 is 7 - 4 = 3.
On day 2, paint everything between 7 and 8.
Everything between 5 and 7 was already painted on day 1.
The amount of new area painted on day 2 is 8 - 7 = 1.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: paint = [[1,4],[5,8],[4,7]]
Output: [3,3,1]
Explanation:
On day 0, paint everything between 1 and 4.
The amount of new area painted on day 0 is 4 - 1 = 3.
On day 1, paint everything between 5 and 8.
The amount of new area painted on day 1 is 8 - 5 = 3.
On day 2, paint everything between 4 and 5.
Everything between 5 and 7 was already painted on day 1.
The amount of new area painted on day 2 is 5 - 4 = 1.

Example 3

1
2
3
4
5
6
7

Input: paint = [[1,5],[2,4]]
Output: [4,0]
Explanation:
On day 0, paint everything between 1 and 5.
The amount of new area painted on day 0 is 5 - 1 = 4.
On day 1, paint nothing because everything between 2 and 4 was already painted on day 0.
The amount of new area painted on day 1 is 0.

Constraints

  • 1 <= paint.length <= 10^5
  • paint[i].length == 2
  • 0 <= starti < endi <= 5 * 10^4

Solution

Given a series of intervals [starti, endi], on each day, you need to paint each interval but ensure no overlapping region is painted multiple times. For each interval, calculate the amount of new area painted during that day.

Method 1 - Using visited array

Here is the approach:

  1. Observation:
    • The problem involves tracking painted segments and ensuring that no segment is painted more than once. This can be solved using a Set or a visited status of the painting line.
  2. Key Idea:
    • Use an array (visited) to represent if a particular area is painted or not. This avoids complex calculations and directly enables checking painted regions.
  3. Steps:
    • Initialize a sufficiently large boolean array (visited) to represent the painting line as unpainted initially.
    • Iterate through each interval in paint:
      • For every point in the interval [starti, endi), check if the region has already been painted using the visited array.
      • Increment the counter for newly painted areas and mark areas as painted.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {

    public int[] amountPainted(int[][] paint) {
        int maxEnd = 0;
        for (int[] p : paint) {
            maxEnd = Math.max(maxEnd, p[1]); // Find the maximum range for visited
        }
        boolean[] visited = new boolean[maxEnd]; // To track painted status
        int[] ans = new int[paint.length];

        for (int i = 0; i < paint.length; i++) {
            int start = paint[i][0], end = paint[i][1];
            int count = 0;
            for (int j = start; j < end; j++) {
                if (!visited[j]) { // Paint unvisited segments
                    visited[j] = true;
                    count++;
                }
            }
            ans[i] = count; // Record newly painted segments for the day
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        max_end = max(end for _, end in paint)  # Calculate maximum range for visited
        visited = [False] * max_end  # To track painted status of each segment
        ans: List[int] = []
        
        for start, end in paint:
            count = 0
            for i in range(start, end):
                if not visited[i]:  # Only paint unvisited segments
                    visited[i] = True
                    count += 1
            ans.append(count)  # Record newly painted segments for the day

        return ans

Complexity

  • ⏰ Time complexity: O(L + N) where L is the total number of segments painted across all intervals and N is the number of intervals.
  • 🧺 Space complexity: O(K) where K is the total range covered by all intervals (size of visited array).

Method 2 - Using Segment tree

The segment tree provides an efficient way to manage and query ranges over a number line. In this problem, it is used to track painted areas dynamically and efficiently skip already painted portions of intervals. Here’s the detailed approach:

How the Segment Tree Works

  1. Representation: The segment tree is used to store the total number of painted positions in each segment/range, and lazy propagation is used to defer updates to child nodes when necessary.
  2. Implementation Steps:
    • Update the range [starti, endi): Mark the range as painted.
    • Query the range [starti, endi): Count how many positions have already been painted.
    • Subtract Query Result from the Total Range: Compute how many positions are newly painted in the range.
  3. Key Benefits:
    • Efficient updates and queries over overlapping intervals using lazy propagation.
    • Reduced complexity compared to naive iteration by splitting the range recursively.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class SegmentTree {
    private int[] tree;
    private int[] lazy;
    private int size;

    public SegmentTree(int size) {
        this.size = size;
        this.tree = new int[4 * size];  // Segment tree array
        this.lazy = new int[4 * size]; // Lazy propagation array
    }

    public int update(int ind, int left, int right, int ql, int qr) {
        // Apply any pending lazy updates
        if (lazy[ind] > 0) {
            tree[ind] += (right - left) * lazy[ind];  // Update this range
            if (left != right - 1) {  // Mark children for lazy updates
                lazy[2 * ind + 1] += lazy[ind];
                lazy[2 * ind + 2] += lazy[ind];
            }
            lazy[ind] = 0;  // Clear pending updates for this node
        }

        // No overlap case
        if (qr <= left || right <= ql) {
            return 0;
        }

        // Complete overlap case
        if (ql <= left && right <= qr) {
            int newPainted = (right - left) - tree[ind];  // Calculate new painted area
            tree[ind] = right - left;  // Mark this range as fully painted
            if (left != right - 1) {  // Mark children for lazy updates
                lazy[2 * ind + 1] += 1;
                lazy[2 * ind + 2] += 1;
            }
            return newPainted;
        }

        // Partial overlap case: split into children
        int mid = (left + right) / 2;
        int leftPainted = update(2 * ind + 1, left, mid, ql, qr);
        int rightPainted = update(2 * ind + 2, mid, right, ql, qr);
        tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2];  // Update current node based on children
        return leftPainted + rightPainted;
    }
}

class Solution {
    public int[] amountPainted(int[][] paint) {
        int maxEnd = 0;
        for (int[] p : paint) {
            maxEnd = Math.max(maxEnd, p[1]);
        }

        SegmentTree segTree = new SegmentTree(maxEnd);
        int[] ans = new int[paint.length];

        for (int i = 0; i < paint.length; i++) {
            int start = paint[i][0];
            int end = paint[i][1];
            // Update the range and get the number of newly painted segments
            ans[i] = segTree.update(0, 0, segTree.size, start, end);
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class SegmentTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (4 * size)  # Segment tree array
        self.lazy = [0] * (4 * size)  # Lazy propagation array

    def update(self, ind: int, left: int, right: int, ql: int, qr: int) -> int:
        # Apply any pending lazy updates
        if self.lazy[ind] > 0:
            self.tree[ind] += (right - left) * self.lazy[ind]  # Update this range
            if left != right - 1:  # Mark children for lazy updates
                self.lazy[2 * ind + 1] += self.lazy[ind]
                self.lazy[2 * ind + 2] += self.lazy[ind]
            self.lazy[ind] = 0  # Clear pending updates for this node

        # No overlap case
        if qr <= left or right <= ql:
            return 0
        
        # Complete overlap case
        if ql <= left and right <= qr:
            new_painted = (right - left) - self.tree[ind]  # Calculate new painted area
            self.tree[ind] = right - left  # Mark this range as fully painted
            if left != right - 1:  # Mark children for lazy updates
                self.lazy[2 * ind + 1] += 1
                self.lazy[2 * ind + 2] += 1
            return new_painted

        # Partial overlap case: split into children
        mid = (left + right) // 2
        left_painted = self.update(2 * ind + 1, left, mid, ql, qr)
        right_painted = self.update(2 * ind + 2, mid, right, ql, qr)
        self.tree[ind] = self.tree[2 * ind + 1] + self.tree[2 * ind + 2]  # Update current node based on children
        return left_painted + right_painted

class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        max_end = max(end for _, end in paint)  # Compute maximum end for segment tree size
        seg_tree = SegmentTree(max_end)
        ans: List[int] = []

        for start, end in paint:
            # Update the range and get the number of newly painted segments
            newly_painted = seg_tree.update(0, 0, seg_tree.size, start, end)
            ans.append(newly_painted)
        
        return ans

Complexity

  • ⏰ Time complexity:  O(n * log(max_end)).
    • Segment tree operations (update/query): O(log(max_end)).
    • For n intervals, the overall complexity is O(n * log(max_end)).
  • 🧺 Space complexity: O(4 * max_end) for Segment tree storage due to recursive node allocation