Describe the Painting

Describe the Painting

1. What is this problem about?

The Describe the Painting interview question involves processing a list of linear segments, each with a specific color (represented by an integer value). These segments can overlap. Your task is to return a "description" of the resulting painting: a list of non-overlapping intervals, each with the sum of the colors of all segments that cover that interval. This Describe the Painting coding problem is about calculating cumulative state over overlapping ranges.

2. Why is this asked in interviews?

Companies like Amazon and Google ask this to evaluate your proficiency with the Prefix Sum interview pattern and coordinate tracking. It tests your ability to handle "event-based" data processing—where points in time (or space) trigger changes in state. It's a test of efficient $O(N \log N)$ or $O(N)$ logic.

3. Algorithmic pattern used

This problem uses the Difference Array / Sweep Line pattern.

• Mark the "start" and "end" of each segment as events.
• At a "start" point, add the color value to a running sum.
• At an "end" point, subtract the color value.
• Sort all unique coordinate points and calculate the total color between each pair of adjacent points.

4. Example explanation

Segments: [1, 4, color:5], [2, 7, color:10].

1. Events: 1: +5, 2: +10, 4: -5, 7: -10.
2. Unique sorted points: 1, 2, 4, 7.
3. Interval [1, 2]: sum is 5.
4. Interval [2, 4]: sum is $5 + 10 = 15$.
5. Interval [4, 7]: sum is $15 - 5 = 10$. Result: [[1, 2, 5], [2, 4, 15], [4, 7, 10]].

5. Common mistakes candidates make

• Inefficient Simulation: Creating an array of all possible coordinates and incrementing each one ($O( ext{Range} imes N)$), which fails if the coordinates are large.
• Missing boundary points: Forgetting that an interval ends exactly where another might begin, and failing to correctly merge or split at these boundary events.
• Not handling zero sums: Sometimes an interval might have a total sum of 0 (if colors cancel out or no segments cover it); these should typically be excluded from the description.

6. Interview preparation tip

Whenever a problem involves "adding values to ranges," think of a Difference Array. It allows you to perform range updates in $O(1)$ and then retrieve all final values in a single $O(N)$ pass.