Skip to main content
Talentd

Amount of New Area Painted Each Day - Solution & Explanation

HardPremiumFree on FleetCodeArraySegment TreeOrdered Set8 min readAsked at: Uber, Google
Practice this problem

Problem Statement

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]]
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 <= 105
  • paint[i].length == 2
  • 0 <= starti < endi <= 5 * 104

Approach Overview

Problem Overview: Each day you paint an interval [start, end) on a long wall. Some sections may already be painted from previous days. For every day, return how much new area gets painted that wasn’t covered before.

Approach 1: Direct Simulation with Painted Array (Brute Force) (Time: O(n * R), Space: O(R))

Track every painted unit using a boolean array representing the wall. For each day’s interval, iterate from start to end - 1. If a position is not painted yet, mark it painted and increase the count for that day. This approach is simple but inefficient when intervals are large because you repeatedly scan already-painted cells. It works only when the coordinate range is small.

Approach 2: Ordered Set / Interval Merging (Time: O(n log n), Space: O(n))

Store previously painted segments in an ordered structure such as a TreeMap, TreeSet, or balanced BST. For a new interval, locate overlapping segments using ordered lookups. Skip regions that are already painted and count only the uncovered parts. Merge overlapping intervals afterward to maintain a disjoint set of painted segments. Each operation involves logarithmic searches and merges, giving overall O(n log n) complexity. This method relies on interval management and ordered traversal, commonly implemented using an Ordered Set.

Approach 3: Segment Tree with Lazy Propagation (Time: O(n log R), Space: O(R))

Model the wall as a range and build a Segment Tree where each node tracks how much of its interval is already painted. For each day, query how many cells are currently painted inside [start, end), then update the segment tree to mark the entire range as painted. The difference between interval length and already-painted cells gives the new area for that day. This structure efficiently supports range queries and updates on large coordinate ranges.

Recommended for interviews: The ordered interval approach is usually the cleanest solution. It shows you understand interval merging, logarithmic lookups, and efficient state tracking using data structures like arrays and ordered maps. Brute force demonstrates the baseline idea, but the ordered structure or segment tree solution shows the optimization interviewers expect.

Solution

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation with Painted ArrayO(n * R)O(R)When coordinate range is very small and implementation simplicity matters
Ordered Set / Interval MergingO(n log n)O(n)General case where intervals overlap frequently and efficient merging is required
Segment Tree with Lazy PropagationO(n log R)O(R)When the coordinate range is large and many range queries/updates are needed

Video Solution

AMOUNT OF NEW AREA PAINTED EACH DAY | LEETCODE # 2158 | PYTHON SIMPLE SOLUTION • Cracking FAANG • 5,738 views views

Watch 8 more video solutions →

Frequently Asked Questions

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).

Ready to solve this problem?

Practice Amount of New Area Painted Each Day with our built-in code editor and test cases.

Practice on FleetCode
Previous

Average Height of Buildings in Each Segment

Next

Describe the Painting