Is Amount of New Area Painted Each Day easy or hard?

Amount of New Area Painted Each Day is classified as a Hard problem because it requires efficient handling of overlapping intervals and large ranges. A naive simulation fails due to repeated work, so optimized data structures such as ordered sets or segment trees are required.

Amount of New Area Painted Each Day Python/Java solution

Python solutions typically use sorted structures or dictionaries with interval merging logic, while Java implementations often rely on TreeMap or TreeSet for ordered interval management. Both achieve O(n log n) complexity with careful overlap handling.

How to solve Amount of New Area Painted Each Day in O(n)?

An O(n) style solution can be achieved using a skip or next-pointer technique that jumps over already painted cells. Instead of revisiting painted positions, the algorithm links each painted index to the next unpainted index, similar to path compression. This ensures each position is processed at most once.

What is the best approach for Amount of New Area Painted Each Day?

The most practical solution uses an ordered set or balanced map to track disjoint painted intervals. For each new interval, you find overlapping segments, count only the uncovered parts, and merge intervals. This runs in O(n log n) time and O(n) space, which is efficient for large input sizes.

Is Amount of New Area Painted Each Day asked at Google/Amazon/Meta?

Interval tracking and range update problems like this appear in interviews at large tech companies including Google, Amazon, and Meta. The problem tests knowledge of interval merging, ordered maps, and advanced structures like segment trees.

What data structure is used in Amount of New Area Painted Each Day?

Common implementations use ordered sets or balanced binary search trees to store disjoint intervals. Some solutions also use segment trees for efficient range queries and updates. Both approaches manage overlapping intervals efficiently.

What is the time complexity of Amount of New Area Painted Each Day?

The optimal interval-merging or ordered set approach runs in O(n log n) time because each interval insertion and overlap lookup requires logarithmic operations. Space complexity is O(n) for storing disjoint painted intervals. Segment tree implementations typically run in O(n log R).

Description Hints 4 Solution Video 15:52

2158. Amount of New Area Painted Each Day

Hard55.3% acceptance2 companiesPremium elsewhere, free here

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.

Example 1:

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:

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.

Constraints:

1 <= paint.length <= 10⁵
paint[i].length == 2
0 <= start_i < end_i <= 5 * 10⁴

Asked at 2 companies

Google Uber

Topics

Hints open one at a time

Hint 1

What’s a good way to keep track of intervals that you have already painted?

Hint 2

Create an array of all 1’s, and when you have painted an interval, set the values in that interval to 0.

Hint 3

Using this array, how can you quickly calculate the amount of new area that you paint on a given day?

Hint 4

Calculate the sum of the new array in the interval that you paint.

15:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution