LeetCode 1943 - Describe the Painting

The problem describes a painting laid out on a number line. Each segment of the painting is represented as a half-closed interval [start, end) and is painted with a unique color value.

leetcodemediumarrayhash-tablesortingprefix-sum

LeetCode Problem 1943

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting, Prefix Sum

Solution

Problem Understanding

The problem describes a painting laid out on a number line. Each segment of the painting is represented as a half-closed interval [start, end) and is painted with a unique color value. Since multiple segments may overlap, different colors can exist simultaneously over the same region.

Instead of returning the actual set of colors for each region, we only need to return the sum of the colors currently active on that interval.

The goal is to split the entire painted line into the minimum number of non-overlapping half-closed intervals such that every interval has a constant mixed color sum.

A key detail is that intervals are half-closed. The segment [a, b) includes a but excludes b. This means when one segment ends exactly where another begins, they do not overlap at that point.

The input is:

segments[i] = [starti, endi, colori]

where:

  • starti is the inclusive start of the segment
  • endi is the exclusive end
  • colori is the unique color assigned to that segment

The output should be:

[left, right, mixedColorSum]

for every continuous painted region where the mixed color sum remains constant.

The constraints are important:

  • Up to 2 * 10^4 segments
  • Coordinates up to 10^5
  • Colors up to 10^9

A brute-force simulation over every coordinate would be too slow if implemented naively, especially because coordinates can be large and colors are large integers.

Several edge cases are important:

  • Multiple segments may start or end at the same coordinate
  • Adjacent intervals can have the same color sum but still represent different color sets
  • Some regions may become unpainted and should not appear in the answer
  • Segments can overlap partially or completely
  • Coordinates are sparse, so iterating over every integer point is unnecessary

The fact that colors are unique is also useful. It guarantees that adding and removing colors can be handled cleanly using prefix-sum style updates.

Approaches

Brute Force Approach

A naive solution would simulate the painting across the entire number line.

We could create an array representing every coordinate position from 0 to 10^5. For every segment [start, end, color], we would iterate through all positions in that interval and add color to that position.

After processing all segments, we would scan the array and merge consecutive positions with the same color sum.

This approach is correct because every unit interval would explicitly store the exact mixed color sum active there.

However, it is inefficient because every segment may cover up to 10^5 positions. With 2 * 10^4 segments, the worst-case runtime becomes too large.

Optimal Approach

The key observation is that the mixed color sum only changes at segment boundaries.

If no segment starts or ends between two coordinates, then the active set of colors remains unchanged throughout that interval.

This means we do not need to process every coordinate individually. Instead, we can use a sweep line algorithm with prefix-sum style events.

For every segment:

  • Add +color at start
  • Add -color at end

Then we sort all event coordinates and sweep from left to right while maintaining the current active color sum.

Between two consecutive coordinates:

  • If the active sum is nonzero, that interval contributes to the answer
  • The active sum remains constant throughout that interval

This reduces the problem to processing only boundary points instead of every coordinate.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * maxCoordinate) O(maxCoordinate) Explicitly paints every coordinate
Optimal O(n log n) O(n) Sweep line using difference events

Algorithm Walkthrough

  1. Create a difference map.

We use a hash map where each coordinate stores how the active color sum changes at that point.

For every segment [start, end, color]:

  • Add color at start
  • Subtract color at end

Example:

[1,4,5]

produces:

diff[1] += 5
diff[4] -= 5
  1. Sort all event coordinates.

The active mixed color can only change at these coordinates, so we process them in increasing order. 3. Sweep through the sorted coordinates.

Maintain:

  • current_sum, the active mixed color sum
  • prev_position, the previous coordinate
  1. Before applying the update at the current coordinate, create an interval.

Suppose we move from prev_position to position.

If current_sum > 0, then the interval:

[prev_position, position)

has a constant mixed color sum equal to current_sum.

Add it to the answer. 5. Apply the difference update.

Update:

current_sum += diff[position]

This activates or deactivates colors beginning at this coordinate. 6. Continue until all coordinates are processed.

Since the last coordinate has no interval after it, the sweep naturally terminates.

Why it works

The algorithm relies on the invariant that between two consecutive event coordinates, the set of active segments never changes.

Since colors only start or end at event points, the mixed color sum remains constant throughout the entire interval between them.

By maintaining the running sum of active colors while sweeping left to right, we correctly reconstruct every maximal interval with a constant mixed color sum.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        diff = defaultdict(int)

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

        sorted_positions = sorted(diff.keys())

        result = []
        current_sum = 0
        prev_position = sorted_positions[0]

        for position in sorted_positions:
            if current_sum > 0 and prev_position < position:
                result.append([prev_position, position, current_sum])

            current_sum += diff[position]
            prev_position = position

        return result

The implementation begins by constructing the difference map. Every segment contributes a positive update at its start and a negative update at its end.

The coordinates where changes occur are then sorted. These coordinates define all possible interval boundaries.

The sweep line traversal maintains the currently active mixed color sum. Before applying updates at the current coordinate, the algorithm records the interval between the previous coordinate and the current coordinate, because the active color set remained unchanged throughout that region.

The condition:

current_sum > 0

ensures that unpainted intervals are excluded from the result.

The condition:

prev_position < position

prevents zero-length intervals.

Finally, after processing all coordinates, the constructed list is returned.

Go Solution

package main

import (
	"sort"
)

func splitPainting(segments [][]int) [][]int64 {
	diff := make(map[int]int64)

	for _, segment := range segments {
		start := segment[0]
		end := segment[1]
		color := int64(segment[2])

		diff[start] += color
		diff[end] -= color
	}

	positions := make([]int, 0, len(diff))
	for pos := range diff {
		positions = append(positions, pos)
	}

	sort.Ints(positions)

	result := [][]int64{}

	var currentSum int64 = 0
	prevPosition := positions[0]

	for _, position := range positions {
		if currentSum > 0 && prevPosition < position {
			result = append(result, []int64{
				int64(prevPosition),
				int64(position),
				currentSum,
			})
		}

		currentSum += diff[position]
		prevPosition = position
	}

	return result
}

The Go implementation follows the same sweep-line logic as the Python version.

One important difference is the use of int64. Since colors can be as large as 10^9 and there may be many overlapping segments, the total sum can exceed the range of a standard 32-bit integer.

Go maps also require explicit initialization with make, unlike Python's defaultdict.

The result type is [][]int64 because the LeetCode signature expects 64-bit integers.

Worked Examples

Example 1

Input:

segments = [[1,4,5],[4,7,7],[1,7,9]]

Step 1: Build Difference Map

Coordinate Change
1 +5
4 -5 +7
7 -7
1 +9
7 -9

Combined:

Coordinate Net Change
1 +14
4 +2
7 -16

Step 2: Sort Coordinates

[1, 4, 7]

Step 3: Sweep

Current Position Previous Position Current Sum Before Update Interval Added Update Applied New Sum
1 1 0 none +14 14
4 1 14 [1,4,14] +2 16
7 4 16 [4,7,16] -16 0

Final answer:

[[1,4,14],[4,7,16]]

Example 2

Input:

segments = [[1,7,9],[6,8,15],[8,10,7]]

Difference Map

Coordinate Net Change
1 +9
6 +15
7 -9
8 -15 +7
10 -7

Simplified:

Coordinate Net Change
1 +9
6 +15
7 -9
8 -8
10 -7

Sweep

Position Prev Sum Before Interval Update New Sum
1 1 0 none +9 9
6 1 9 [1,6,9] +15 24
7 6 24 [6,7,24] -9 15
8 7 15 [7,8,15] -8 7
10 8 7 [8,10,7] -7 0

Final answer:

[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]

Example 3

Input:

segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]

Difference Map

Coordinate Net Change
1 +12
4 -12 +12
7 -12

Simplified:

Coordinate Net Change
1 +12
4 0
7 -12

Sweep

Position Prev Sum Before Interval Update New Sum
1 1 0 none +12 12
4 1 12 [1,4,12] 0 12
7 4 12 [4,7,12] -12 0

Final answer:

[[1,4,12],[4,7,12]]

Even though the sums are both 12, the intervals must remain separate because the underlying color sets differ.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting all event coordinates dominates the runtime
Space O(n) The difference map stores at most 2n coordinates

Each segment contributes exactly two events, one start event and one end event.

If there are n segments, there are at most 2n distinct coordinates. Sorting these coordinates requires O(n log n) time.

The sweep itself is linear in the number of event points, so it does not change the overall complexity.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        diff = defaultdict(int)

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

        positions = sorted(diff.keys())

        result = []
        current_sum = 0
        prev = positions[0]

        for pos in positions:
            if current_sum > 0 and prev < pos:
                result.append([prev, pos, current_sum])

            current_sum += diff[pos]
            prev = pos

        return result

sol = Solution()

# Example 1
assert sol.splitPainting(
    [[1,4,5],[4,7,7],[1,7,9]]
) == [[1,4,14],[4,7,16]]

# Example 2
assert sol.splitPainting(
    [[1,7,9],[6,8,15],[8,10,7]]
) == [[1,6,9],[6,7,24],[7,8,15],[8,10,7]]

# Example 3
assert sol.splitPainting(
    [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
) == [[1,4,12],[4,7,12]]

# Single segment
assert sol.splitPainting(
    [[2,5,10]]
) == [[2,5,10]]

# Completely overlapping segments
assert sol.splitPainting(
    [[1,5,3],[1,5,7]]
) == [[1,5,10]]

# Nested overlap
assert sol.splitPainting(
    [[1,10,5],[3,7,8]]
) == [[1,3,5],[3,7,13],[7,10,5]]

# Touching but non-overlapping segments
assert sol.splitPainting(
    [[1,3,4],[3,5,6]]
) == [[1,3,4],[3,5,6]]

# Multiple changes at same coordinate
assert sol.splitPainting(
    [[1,4,5],[4,6,7],[4,8,9]]
) == [[1,4,5],[4,6,16],[6,8,9]]

# Large color values
assert sol.splitPainting(
    [[1,3,10**9],[2,4,10**9]]
) == [[1,2,10**9],[2,3,2*10**9],[3,4,10**9]]

# Complex overlap chain
assert sol.splitPainting(
    [[1,5,1],[2,6,2],[3,7,3]]
) == [
    [1,2,1],
    [2,3,3],
    [3,5,6],
    [5,6,5],
    [6,7,3]
]
Test Why
Example 1 Basic overlap handling
Example 2 Partial overlaps and independent regions
Example 3 Same sum but different intervals
Single segment Simplest valid input
Completely overlapping segments Entire interval shares same mixed color
Nested overlap One segment fully inside another
Touching segments Verifies half-closed interval behavior
Multiple changes at same coordinate Ensures updates are combined correctly
Large color values Verifies large integer handling
Complex overlap chain Stress test with multiple simultaneous overlaps

Edge Cases

One important edge case occurs when multiple segments start or end at the same coordinate. A buggy implementation might process these events separately and accidentally create zero-length intervals or incorrect transitions. The difference-map approach naturally combines all updates at the same coordinate before continuing the sweep, which guarantees correctness.

Another important case is touching intervals such as [1,3) and [3,5). Since intervals are half-closed, these do not overlap. A naive implementation might incorrectly merge them. The sweep-line method handles this correctly because one color is removed at coordinate 3 before the next interval begins.

A third tricky case happens when two adjacent intervals have the same numeric sum but different underlying color sets. For example:

[1,4) -> {5,7}
[4,7) -> {1,11}

Both sums equal 12, but they represent different color mixtures. The algorithm still keeps them separate because interval boundaries are determined by event coordinates, not by whether neighboring sums happen to match.

Another subtle case is unpainted regions. After all active colors disappear, the current sum becomes zero. The implementation explicitly skips intervals with current_sum == 0, ensuring that blank regions are not included in the result.