2158. Amount of New Area Painted Each Day

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.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

  • 1 <= paint.length <= 105
  • paint[i].length == 2
  • 0 <= starti < endi <= 5 * 104

Solution

Naive solution in O(nm)\mathcal{O}(nm)

Let's split the number line into blocks such that for the iith block covers the interval [i,i+1][i, i+1]. Create a boolean array to store whether each block has been painted.

On day ii, we are tasked with painting blocks starti\text{start}_i to endi1\text{end}_i-1. We can check each of these blocks, painting the unpainted ones (we also keep count of how many blocks we paint because that's what the question asks for). In the worst case, we have to check every block on every day. Let nn be the number of days (up to 100000100000) and let mm be the largest number that appears in the input (up to 5000050000). The time complexity is O(nm)\mathcal{O}(nm). This is not fast enough.

A simple solution in O((n+m)logm)\mathcal{O}((n+m) \log m)

Instead of using a boolean array, we can use a BBST (balanced binary search tree) to store the indices of the unpainted blocks. At the start, we insert 0,1,2,,m1,m0, 1, 2, \ldots, m-1, m into the BBST. When we paint a node, we delete its node from the BBST. In our time complexity analysis, it will become clear why we chose to use a BBST.

On each day, we search for the first node lefti\ge \text{left}_i. If it's also <righti< \text{right}_i, we delete it. We repeatedly do this until there are no more blocks between lefti\text{left}_i and righti1\text{right}_i-1.

<mark style={{ backgroundColor: "lightblue" }}>The intuition behind this solution is that we don't want need to needlessly loop over painted blocks; as soon as a block is painted, it's no longer useful, so we delete it. Otherwise, in future days, we'd have to keep checking whether each block has been painted. A BBST can do what we need: find and delete single items quickly.

Time complexity

Inserting 0,1,2,,m1,m0, 1, 2, \ldots, m-1, m into the BBST at the start takes O(mlogm)\mathcal{O}(m \log m) time.

Finding the first node lefti\ge \text{left}_i and deleting a node both take O(logm)\mathcal{O}(\log m), and we do them at most n+mn+m and mm times, respectively.

In total, our algorithm takes O(mlogm+(n+m)logm+mlogm)=O((n+m)logm)\mathcal{O}(m \log m + (n+m) \log m + m \log m) = \mathcal{O}((n+m) \log m).

Space complexity

A BBST of mm elements takes O(m)\mathcal{O}(m) space.

Built-in BBSTs

Most programming languages have built-in BBSTS so we don't have to code them ourselves. C++ has set, Java has TreeSet, Python has SortedList, and JavaScript has SortedSet (but it's not supported on LeetCode).

C++ Solution

1class Solution {
2public:
3    vector<int> amountPainted(vector<vector<int>>& paint) {
4        set<int> unpainted;
5        vector<int> ans(paint.size());
6        for (int i = 0; i <= 50000; i++) {
7            unpainted.insert(i);
8        }
9        for (int i = 0; i < paint.size(); i++) {
10            int left = paint[i][0], right = paint[i][1];
11            // Repeatedly delete the first element >= left until it becomes >= right
12            // This clears values in [left, right) from the set
13            for (auto it = unpainted.lower_bound(left); *it < right; it = unpainted.erase(it), ans[i]++);
14        }
15        return ans;
16    }
17};

Java Solution

1class Solution {
2    public int[] amountPainted(int[][] paint) {
3        TreeSet<Integer> unpainted = new TreeSet<>();
4        int[] ans = new int[paint.length];
5        for (int i = 0; i <= 50000; i++) {
6            unpainted.add(i);
7        }
8        for (int i = 0; i < paint.length; i++) {
9            int left = paint[i][0], right = paint[i][1];
10            // Repeatedly delete the first element >= left until it becomes >= right
11            // This clears values in [left, right) from the TreeSet
12            while (true) {
13                int next = unpainted.ceiling(left);
14                if (next >= right)
15                    break;
16                unpainted.remove(next);
17                ans[i]++;
18            }
19        }
20        return ans;
21    }
22}

Python Solution

1from sortedcontainers import SortedList
2
3class Solution:
4    def amountPainted(self, paint: List[List[int]]) -> List[int]:
5        unpainted = SortedList([i for i in range(0, 50001)])
6        ans = [0 for _ in range(len(paint))]
7        for i in range(len(paint)):
8            left, right = paint[i]
9            # Repeatedly delete the first element >= left until it becomes >= right
10            # This clears values in [left, right) from the SortedList
11            while unpainted[ind := unpainted.bisect_left(left)] < right:
12                unpainted.__delitem__(ind)
13                ans[i] += 1
14        return ans

JavaScript Solution

1var SortedSet = require("collections/sorted-set");
2/**
3 * @param {number[][]} paint
4 * @return {number[]}
5 */
6var amountPainted = function (paint) {
7  const n = paint.length;
8  const ans = new Array(n).fill(0);
9  const unpainted = new SortedSet(Array.from(Array(50001).keys()));
10  for (let i = 0; i < n; i++) {
11    (left = paint[i][0]), (right = paint[i][1]);
12    // Repeatedly delete the first element >= left until it becomes >= right
13    // This clears values in [left, right) from the SortedSet
14    while ((node = unpainted.findLeastGreaterThanOrEqual(left)).value < right) {
15      unpainted.delete(node.value);
16      ans[i]++;
17    }
18  }
19  return ans;
20};

Alternative O(nlogn)\mathcal{O}(n \log n) solution

Instead of storing the unpainted blocks, we can store the painted segments. We store them as (left, right) pairs in a BBST, where no segments intersect. Each day, we delete segments fully contained in [left_i, right_i], then merge partially overlapping segments with it, all while keeping count of how many blocks we've painted this day. We create, delete, and check for overlaps in O(n)\mathcal{O}(n) segments for a total time complexity of O(nlogn)\mathcal{O}(n \log n). This solution is trickier to implement—code will not be presented here.

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

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Implementation


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄