# Amount of New Area Painted Each Day

Published: Dec 17, 2022

Hard Hash Table Array

## Problem Description

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] = [start[i], end[i]]`. This means that on the i-th day you need to paint the area between `start[i]` and `end[i]`.

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 i-th day.

Constraints:

• `1 <= paint.length <= 10**5`
• `paint[i].length == 2`
• `0 <= start[i] < end[i] <= 5 * 10**4`

https://leetcode.com/problems/amount-of-new-area-painted-each-day/

## Examples

``````Exmaple 1
nput: 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
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
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.
``````

## How to Solve

As this problem is categorized to the hard, it is really a hard problem. Easy solution such that all range checks will get the time limit exceeded error. The problem requires an effective solution. Various approaches are there to solve this problem, for example, interval merges, binary search, ordered set, segment tree and more.

Among those, the solution here took the hash table approach. If the given start and end range doesn’t exist in the hash table, save all values from start to end (end is not included) as a key to the hash table with the end as a value. If the given start and end range overlaps to the existing range(s), update the end value to a bigger one. Also, skip the check to the original end value. When a single work check is completed, add the work sum to the worklog array.

## Solution

``````class AmountOfNewAreaPaintedEachDay {
public:
vector<int> amountPainted(vector<vector<int>>& paint) {
unordered_map<int, int> painted;
vector<int> worklog;
for (size_t i = 0; i < paint.size(); ++i) {
int start = paint[i], end = paint[i];
int work = 0;
while (start < end) {
if (painted.find(start) != painted.end()) {
int prev_end = painted[start];
painted[start] = max(painted[start], end);
start = prev_end;
} else {
painted[start] = end;
start++;
work++;
}
}
worklog.push_back(work);
}
return worklog;
}
};
``````
``````
``````
``````/**
* @param {number[][]} paint
* @return {number[]}
*/
var amountPainted = function(paint) {
let painted = new Map(), worklog = [];
for (let [start, end] of paint) {
let work = 0;
while (start < end) {
if (painted.has(start)) {
let prev_end = painted.get(start);
painted.set(start, Math.max(prev_end, end));
start = prev_end;
} else {
painted.set(start, end);
start++;
work++;
}
}
worklog.push(work);
}
return worklog;
};
``````
``````class AmountOfNewAreaPaintedEachDay:
def amountPainted(self, paint: List[List[int]]) -> List[int]:
painted = {}
worklog = []
for start, end in paint:
work = 0
while start < end:
if start in painted:
prev_end = painted[start]
painted[start] = max(painted[start], end)
start = prev_end
else:
painted[start] = end
start += 1
work += 1
worklog.append(work)
return worklog

``````
``````
``````

## Complexities

• Time: `O(m * n)` – m: length of paint, n: range size in the pain array
• Space: `O(m * n)`