Describe the Painting: Sweep Line on Segments

LeetCode 1943, Describe the Painting, gives you a set of overlapping colored segments and asks you to merge them into a single painting where each region's color is the sum of all the individual colors covering it. It is a clean application of the sweep line technique, and once you see the pattern, the solution is short and satisfying.

The problem

You are given a list of segments, where each segment is [start, end, color]. A segment paints the half-open interval [start, end) with the given color value. When multiple segments overlap, the resulting color in that region is the sum of all overlapping colors.

Return a list of non-overlapping segments [start, end, mixed_color] that describes the entire painting. Two adjacent segments in the output must have different mixed colors.

Input: segments = [[1,4,5],[4,7,7],[1,7,9]]
Output: [[1,4,14],[4,7,16]]

From position 1 to 4, segments [1,4,5] and [1,7,9] overlap, so the mixed color is 5 + 9 = 14. From position 4 to 7, segments [4,7,7] and [1,7,9] overlap, giving 7 + 9 = 16.

Why this is a sweep line problem

Whenever you have overlapping intervals that each contribute some value, and you need to know the total contribution across every region, you are looking at a sweep line problem. The core idea is to stop thinking about each segment individually and instead think about the events that change the running total.

Each segment creates exactly two events: a "start" event that adds its color, and an "end" event that removes it. If you process these events in order from left to right, you always know the current mixed color at every point on the number line.

The approach: difference array + sweep

Here is the plan:

1. For each segment [start, end, color], record +color at position start and -color at position end.
2. Collect all events into a dictionary keyed by position, summing deltas at the same position.
3. Sort the positions.
4. Walk through the sorted positions from left to right, maintaining a running sum of colors.
5. Between consecutive positions, if the running sum is not zero, emit a result segment [prev_pos, curr_pos, running_sum].

That is the entire algorithm. The key insight is that the mixed color only changes at segment endpoints. Between any two consecutive endpoints, the color sum is constant.

Step-by-step walkthrough

Notice how position 4 is both the end of one segment and the start of another. The delta at position 4 is -5 + 7 = +2, which correctly transitions the running sum from 14 to 16 in a single step. This is why using a difference array is so clean. You do not need to handle starts and ends separately.

The code

from collections import defaultdict

def splitPainting(segments):
    diff = defaultdict(int)

    for start, end, color in segments:
        diff[start] += color
        diff[end] -= color

    result = []
    prev = 0
    running = 0

    for pos in sorted(diff):
        if running and prev != pos:
            result.append([prev, pos, running])
        running += diff[pos]
        prev = pos

    return result

1. Build the difference map. For each segment, add the color at start and subtract it at end.
2. Sort all positions that have events. This gives you the sweep order.
3. Walk through positions. Before applying the delta at the current position, check if there is an active painting (running sum is not zero). If so, emit the segment from prev to the current position with the current running sum.
4. Apply the delta to update the running sum, then move prev forward.

The order matters: you emit the segment for the region before the current position, then update the running sum. This ensures each emitted segment uses the correct color for its range.

Complexity analysis

Time: O(n log n). Building the difference map is O(n). Sorting the positions is O(n log n) in the worst case (each segment contributes at most 2 unique positions, so there are at most 2n keys). The sweep itself is O(n).

Space: O(n). The difference map and the result list each hold at most O(n) entries.

Building blocks

1. Difference array / event decomposition

The idea of recording "+value at start, -value at end" is a general technique called a difference array. It converts range updates into point updates. After all updates, a prefix sum recovers the actual values.

diff = defaultdict(int)
for start, end, value in ranges:
    diff[start] += value
    diff[end] -= value

This building block appears in many problems: range addition queries, car pooling (tracking passenger counts), and calendar booking (counting overlapping events). Any time you need to apply many range updates and then query the result, a difference array is the right tool.

2. Sweep line aggregation

Once you have your events, the sweep is a simple left-to-right pass. You maintain some running state (a sum, a count, a set) and update it at each event. Between events, the state is constant, so you can emit results for the gaps.

running = 0
prev = None
for pos in sorted(events):
    if prev is not None and running > 0:
        emit(prev, pos, running)
    running += events[pos]
    prev = pos

The sweep line pattern generalizes beyond sums. In the skyline problem, you track the maximum height. In meeting rooms, you track the count of active meetings. The structure is always the same: sort events, sweep, and aggregate.

Edge cases

• Non-overlapping segments. Each segment becomes its own result entry with its original color. The difference array still works because only one segment is active in each region.
• Fully overlapping segments with the same range. Two segments [1,5,3] and [1,5,7] produce a single result [1,5,10]. The deltas at position 1 add up to +10 and at position 5 to -10.
• Adjacent segments. Segments [1,3,5] and [3,6,5] share position 3 as both an end and a start. The running sum at position 3 transitions seamlessly. If the new sum equals the old sum, these get merged into one result segment because the color does not change. Actually, in this case the problem requires that adjacent result segments have different mixed colors, which is automatically satisfied because you only emit when the sum is nonzero and the sum changes at event points.
• Single segment. Returns that segment as the only result entry.
• Large coordinate values. Because we only process segment endpoints (not every integer in the range), the algorithm works even when coordinates go up to 10^5 or beyond.

From understanding to recall

The sweep line with a difference array is one of those patterns that feels obvious after you see it, but it can be tricky to reconstruct under pressure. The details matter: do you emit the segment before or after updating the running sum? Do you check for a nonzero sum or a changed sum?

The answer is that you emit before updating, and you check that the running sum is nonzero (meaning there is paint in that region). These are small decisions that determine correctness.

Reading the solution once gives you the concept. But if you want to write it from scratch in an interview, you need to have practiced it enough that the emit-then-update order feels automatic. Spaced repetition is the most effective way to build that fluency. Write the solution, verify it, and revisit it in a few days.

Related posts

• Insert Interval - another interval manipulation problem using a three-phase scan
• Meeting Rooms II - sweep line for counting overlapping intervals and finding the peak
• My Calendar I - interval overlap detection with a simpler booking constraint

CodeBricks organizes problems like Describe the Painting into pattern families so you can drill the sweep line technique across multiple variations. Instead of solving one problem and moving on, you revisit the pattern at increasing intervals until it sticks.