Amount of New Area Painted Each Day

Amount of New Area Painted Each Day

What is this problem about?

The "Amount of New Area Painted Each Day interview question" is an interval-tracking problem. You are given a series of painting tasks, where each task defines a range [start, end] on a 1D wall. On each day, you paint the specified range. However, you only count the "new" area—sections of the wall that haven't been painted on any previous day. You need to return an array containing the amount of new area painted on each specific day.

Why is this asked in interviews?

Uber and Google ask the "Amount of New Area Painted Each Day coding problem" to test a candidate's ability to manage overlapping intervals. The naive approach (using a boolean array or a set of points) works for small ranges but fails for large ones. This problem tests knowledge of advanced data structures like Segment Trees or the "Ordered Set interview pattern."

Algorithmic pattern used

While several patterns can solve this, the most common interview solutions use Interval Merging or a Disjoint Set Union (DSU) / Jump Pointer technique.

• Jump Pointers: Maintain an array where parent[i] points to the next unpainted spot after index i. When you paint a range, you skip over already-painted spots using these pointers and update them so that future days skip even further.
• Segment Tree: Use a segment tree with lazy propagation to mark ranges as "painted." For each new range, query the number of unpainted segments and then update the tree.

Example explanation

Day 1: [1, 4]. Area 1-2, 2-3, 3-4 are new. Amount: 3. Day 2: [2, 6].

• 2-3, 3-4 are already painted.
• 4-5, 5-6 are new. Amount: 2. Day 3: [1, 7].
• 1-6 is already painted.
• 6-7 is new. Amount: 1. Result: [3, 2, 1].

Common mistakes candidates make

• Inefficiency: Using a Set to store every single integer point. If the coordinates are up to $10^9$, this will cause a Memory Limit Exceeded error.
• Overlapping logic: Failing to correctly subtract only the already painted parts from the current day's range.
• Sorting: Trying to sort the days. You must process them in the given order because "new area" depends on what was painted on previous days.

Interview preparation tip

Master the "Intervals" category of problems. If the constraints are small, a simple sweep-line or array works. If they are large, look into coordinate compression or segment trees.