Describe the Painting - Solution & Explanation
Problem Statement
There is a long and thin painting that can be represented by a number line. The painting was painted with multiple overlapping segments where each segment was painted with a unique color. You are given a 2D integer array segments, where segments[i] = [starti, endi, colori] represents the half-closed segment [starti, endi) with colori as the color.
The colors in the overlapping segments of the painting were mixed when it was painted. When two or more colors mix, they form a new color that can be represented as a set of mixed colors.
- For example, if colors
2,4, and6are mixed, then the resulting mixed color is{2,4,6}.
For the sake of simplicity, you should only output the sum of the elements in the set rather than the full set.
You want to describe the painting with the minimum number of non-overlapping half-closed segments of these mixed colors. These segments can be represented by the 2D array painting where painting[j] = [leftj, rightj, mixj] describes a half-closed segment [leftj, rightj) with the mixed color sum of mixj.
- For example, the painting created with
segments = [[1,4,5],[1,7,7]]can be described bypainting = [[1,4,12],[4,7,7]]because:[1,4)is colored{5,7}(with a sum of12) from both the first and second segments.[4,7)is colored{7}from only the second segment.
Return the 2D array painting describing the finished painting (excluding any parts that are not painted). You may return the segments in any order.
A half-closed segment [a, b) is the section of the number line between points a and b including point a and not including point b.
Example 1:
Input: segments = [[1,4,5],[4,7,7],[1,7,9]]
Output: [[1,4,14],[4,7,16]]
Explanation: The painting can be described as follows:
- [1,4) is colored {5,9} (with a sum of 14) from the first and third segments.
- [4,7) is colored {7,9} (with a sum of 16) from the second and third segments.
Example 2:
Input: segments = [[1,7,9],[6,8,15],[8,10,7]]
Output: [[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
Explanation: The painting can be described as follows:
- [1,6) is colored 9 from the first segment.
- [6,7) is colored {9,15} (with a sum of 24) from the first and second segments.
- [7,8) is colored 15 from the second segment.
- [8,10) is colored 7 from the third segment.
Example 3:
Input: segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
Output: [[1,4,12],[4,7,12]]
Explanation: The painting can be described as follows:
- [1,4) is colored {5,7} (with a sum of 12) from the first and second segments.
- [4,7) is colored {1,11} (with a sum of 12) from the third and fourth segments.
Note that returning a single segment [1,7) is incorrect because the mixed color sets are different.
Constraints:
1 <= segments.length <= 2 * 104segments[i].length == 31 <= starti < endi <= 1051 <= colori <= 109- Each
coloriis distinct.
Approach Overview
Problem Overview: You receive multiple painting segments where each interval [start, end) adds a color value to the canvas. Overlapping segments mix colors by summing their values. The task is to return the minimal set of non‑overlapping segments where the total color value stays constant.
Approach 1: Sweep Line Technique with Events (O(n log n) time, O(n) space)
This is the most practical solution and the one typically expected in interviews. Treat every interval boundary as an event: add the color value at start and subtract it at end. Store these changes in a map or array and process positions in sorted order using a sweep line. As you move from one coordinate to the next, maintain a running prefix sum of active color values. Whenever the accumulated value is non‑zero, the range between the current coordinate and the next one forms a valid painted segment.
The key insight is that the color value only changes at interval boundaries. Instead of examining every point on the line, you only process event positions and accumulate color contributions with a prefix sum. Sorting the event keys gives an ordered traversal of the painting. This approach relies heavily on concepts from Sorting, Prefix Sum, and Array event processing.
Approach 2: Interval Tree Approach (O(n log n) time, O(n) space)
An alternative solution builds a structure that manages overlapping intervals dynamically. Insert each painting segment into an interval tree where nodes represent ranges and track the cumulative color value for that region. When a new interval overlaps existing nodes, split the affected ranges and update their stored color sums. After all insertions, perform an in‑order traversal of the tree to collect contiguous ranges with their final color values.
This method models the painting more explicitly as interval segments that split whenever overlaps occur. While conceptually clean, the implementation is heavier than the sweep line approach because the tree must handle interval splitting and merging. The benefit is flexibility: interval trees work well when segments are inserted dynamically or when many overlap queries are required.
Recommended for interviews: The sweep line technique is the expected solution. It demonstrates strong understanding of event processing, coordinate sorting, and prefix accumulation. Interviewers typically want to see the transformation from overlapping intervals to boundary events. Implementing an interval tree shows deeper data‑structure knowledge but is rarely necessary for this problem.
Approach 1: Sweep Line Technique with Events
This approach involves representing each segment's start and end as events on the number line. We use a sweep line technique to iterate through sorted events, maintaining a running count of active segments and calculating the mixed color sums in between events.
In this C implementation, we handle segments as events (starting and ending). Using an array of these events, we sort them by position. As we iterate through the sorted events, we maintain a running sum of active color segments using a simple array to represent active segments, updating this as we encounter start and end events. Segments are added to the painting result whenever there is an interval between events and the sum of active segments is positive.
Complexity
Time complexity: O(n log n) due to sorting of events (where n is the number of segment endpoints).
Space complexity: O(n) for storing events and managing active segments.
Approach 2: Interval Tree Approach
An interval tree can help manage overlapping segments and mixed colors efficiently. Use an interval tree structure to add segments and query overlapping intervals as you iterate through the segments, dynamically updating and storing mixed color sums.
Implementing a sophisticated data structure like an interval tree efficiently in C requires detailed handling of pointers and possibly creating multiple struct extensions. With this approach, the interval tree dynamically manages color ranges, updating mixes as segments are inserted or queried.
Complexity
The complexity largely depends on the interval tree implementation but can be efficient with many operations falling under O(log n) for both insertions and queries, leading to a global complexity of O(n log n).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Sweep Line Technique with Events | Time complexity: O(n log n) due to sorting of events (where n is the number of segment endpoints). |
| Interval Tree Approach | The complexity largely depends on the interval tree implementation but can be efficient with many operations falling under O(log n) for both insertions and queries, leading to a global complexity of O(n log n). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sweep Line Technique with Events | O(n log n) | O(n) | Best general solution. Efficient for large sets of intervals where color changes occur only at boundaries. |
| Interval Tree Approach | O(n log n) | O(n) | Useful when intervals must be inserted dynamically or when many overlap queries are required. |
Video Solution
Describe the Painting | Leetcode 1943 | Line Sweep Technique Concepts & Questions - 8 | MIK • codestorywithMIK • 3,644 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Describe the Painting easy or hard?
Describe the Painting Python/Java solution
How to solve Describe the Painting in O(n log n)?
What is the best approach for Describe the Painting?
Is Describe the Painting asked at Google/Amazon/Meta?
What data structure is used in Describe the Painting?
What is the time complexity of Describe the Painting?
Ready to solve this problem?
Practice Describe the Painting with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor