Describe the Painting solution and explanation
Google
5 more videos on this problem
Describe the Painting | Leetcode 1943 | Line Sweep Technique Concepts & Questions - 8 | MIKcodestorywithMIK · 34:07 · 3K views
LeetCode 1943. Describe the PaintingHappy Coding · 15:39 · 1K views
LeetCode 1943. Describe the Painting | C++ | in HINDINitesh Kumar · 10:23 · 1K views
1943. Describe the Painting (Leetcode Medium)Programming Live with Larry · 15:56 · 573 views
【每日一题】1943. Describe the Painting, 7/27/2021Huifeng Guan · 23:34 · 323 views
LeetCode 1943: Describe the PaintingAlitaCode · 30:59 · 3 views
The problem
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.
def get_painting(segments):
events = []
for start, end, color in segments:
events.append((start, color))
events.append((end, -color))
events.sort()
from collections import defaultdict
active_colors = defaultdict(int)
result = []
last_position = events[0][0]
current_sum = 0
for pos, color in events:
if last_position != pos and current_sum > 0:
result.append([last_position, pos, current_sum])
last_position = pos
if color > 0:
current_sum += color
active_colors[color] += 1
else:
current_sum += color
active_colors[-color] -= 1
if active_colors[-color] == 0:
del active_colors[-color]
return result
segments = [[1, 4, 5], [1, 7, 7], [4, 7, 12]]
painting = get_painting(segments)
for seg in painting:
print(seg)import java.util.*;
public class PaintingDescription {
public static List<int[]> getPainting(int[][] segments) {
List<int[]> events = new ArrayList<>();
for (int[] seg : segments) {
events.add(new int[]{seg[0], seg[2]});
events.add(new int[]{seg[1], -seg[2]});
}
events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1]));
Map<Integer, Integer> activeColors = new TreeMap<>();
List<int[]> result = new ArrayList<>();
int lastPosition = events.get(0)[0], currentSum = 0;
for (int[] event : events) {
int position = event[0];
int color = event[1];
if (lastPosition != position && currentSum > 0) {
result.add(new int[]{lastPosition, position, currentSum});
}
lastPosition = position;
if (color > 0) {
activeColors.put(color, activeColors.getOrDefault(color, 0) + 1);
currentSum += color;
} else {
color = -color;
currentSum -= color;
if (activeColors.get(color) == 1) {
activeColors.remove(color);
} else {
activeColors.put(color, activeColors.get(color) - 1);
}
}
}
return result;
}
public static void main(String[] args) {
int[][] segments = {{1, 4, 5}, {1, 7, 7}, {4, 7, 12}};
List<int[]> painting = getPainting(segments);
for (int[] seg : painting) {
System.out.println("[" + seg[0] + ", " + seg[1] + ", " + seg[2] + "]");
}
}
}#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
vector<vector<int>> get_painting(vector<vector<int>>& segments) {
vector<pair<int, int>> events;
for (const auto& seg : segments) {
events.emplace_back(seg[0], seg[2]); // start, color
events.emplace_back(seg[1], -seg[2]); // end
}
sort(events.begin(), events.end());
map<int, int> active_colors;
vector<vector<int>> result;
int last_position = events[0].first;
int current_sum = 0;
for (auto& [pos, color] : events) {
if (last_position != pos && current_sum > 0) {
result.push_back({last_position, pos, current_sum});
}
last_position = pos;
if (color > 0) {
active_colors[color]++;
current_sum += color;
} else {
current_sum += color;
if (--active_colors[-color] == 0) {
active_colors.erase(-color);
}
}
}
return result;
}
int main() {
vector<vector<int>> segments = {{1, 4, 5}, {1, 7, 7}, {4, 7, 12}};
auto painting = get_painting(segments);
for (const auto& seg : painting) {
cout << "[" << seg[0] << ", " << seg[1] << ", " << seg[2] << "]\n";
}
return 0;
}function getPainting(segments) {
let events = [];
for (let [start, end, color] of segments) {
events.push([start, color]);
events.push([end, -color]);
}
events.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
let activeColors = new Map();
let result = [];
let lastPosition = events[0][0];
let currentSum = 0;
for (let [pos, color] of events) {
if (lastPosition !== pos && currentSum > 0) {
result.push([lastPosition, pos, currentSum]);
}
lastPosition = pos;
if (color > 0) {
activeColors.set(color, (activeColors.get(color) || 0) + 1);
currentSum += color;
} else {
color = -color;
currentSum -= color;
if (activeColors.get(color) === 1) {
activeColors.delete(color);
} else {
activeColors.set(color, activeColors.get(color) - 1);
}
}
}
return result;
}
const segments = [[1, 4, 5], [1, 7, 7], [4, 7, 12]];
console.log(getPainting(segments));#include <stdio.h>
#include <stdlib.h>
#define MAX_EVENTS 40000
typedef struct { int pos, delta, color; } Event;
int cmp(const void *a, const void *b) {
Event *ea = (Event *)a, *eb = (Event *)b;
return (ea->pos != eb->pos) ? ea->pos - eb->pos : eb->delta - ea->delta;
}
int painting[MAX_EVENTS][3];
int painting_index = 0;
void add_painting_segment(int start, int end, int mix_sum) {
if (start < end) {
painting[painting_index][0] = start;
painting[painting_index][1] = end;
painting[painting_index][2] = mix_sum;
painting_index++;
}
}
int main() {
Event events[MAX_EVENTS];
int segments[][3] = {{1, 4, 5}, {1, 7, 7}, {4, 7, 12}};
int segments_length = 3;
int event_count = 0;
for (int i = 0; i < segments_length; ++i) {
int start = segments[i][0], end = segments[i][1], color = segments[i][2];
events[event_count++] = (Event){start, 1, color};
events[event_count++] = (Event){end, -1, color};
}
qsort(events, event_count, sizeof(Event), cmp);
int current_pos = 0, mix_sum = 0;
int active_segments[MAX_EVENTS] = {0};
int active_count = 0;
for (int i = 0; i < event_count; ++i) {
Event e = events[i];
if (i > 0 && current_pos < e.pos && mix_sum > 0) {
add_painting_segment(current_pos, e.pos, mix_sum);
}
current_pos = e.pos;
if (e.delta == 1) {
mix_sum += e.color;
active_segments[active_count++] = e.color;
} else {
for (int j = 0; j < active_count; ++j) {
if (active_segments[j] == e.color) {
mix_sum -= e.color;
active_segments[j] = active_segments[--active_count];
break;
}
}
}
}
for (int i = 0; i < painting_index; ++i) {
printf("[%d, %d, %d]\n", painting[i][0], painting[i][1], painting[i][2]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Painting {
public static List<int[]> GetPainting(int[][] segments) {
var events = new List<int[]>();
foreach (var seg in segments) {
events.Add(new int[] {seg[0], seg[2]});
events.Add(new int[] {seg[1], -seg[2]});
}
events.Sort((a, b) => a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
var activeColors = new SortedDictionary<int, int>();
var result = new List<int[]>();
int lastPosition = events[0][0];
int currentSum = 0;
foreach (var e in events) {
int position = e[0];
int color = e[1];
if (lastPosition != position && currentSum > 0) {
result.Add(new int[] {lastPosition, position, currentSum});
}
lastPosition = position;
if (color > 0) {
if (!activeColors.ContainsKey(color)) {
activeColors[color] = 0;
}
activeColors[color]++;
currentSum += color;
} else {
color = -color;
if (--activeColors[color] == 0) {
activeColors.Remove(color);
}
currentSum -= color;
}
}
return result;
}
public static void Main() {
int[][] segments = new int[][] {
new int[] {1, 4, 5},
new int[] {1, 7, 7},
new int[] {4, 7, 12}
};
var painting = GetPainting(segments);
foreach (var seg in painting) {
Console.WriteLine($"[{seg[0]}, {seg[1]}, {seg[2]}]");
}
}
}The Python solution makes use of tuples for events and utilizes the defaultdict for managing active color segment counts. Sorting the events and iterating with basic list operations achieves the calculation of the mixed color segments in a straightforward manner.
Time complexity: O(n log n) for sorting.
Space complexity: O(n) due to event storage and active color management.
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.
from collections import defaultdict
def describe_painting(segments):
interval_tree = defaultdict(int)
for start, end, color in segments:
interval_tree[start] += color
interval_tree[end] -= color
last_pos = None
current_sum = 0
result = []
for pos in sorted(interval_tree.keys()):
if last_pos is not None and current_sum != 0:
result.append([last_pos, pos, current_sum])
current_sum += interval_tree[pos]
last_pos = pos
return result
segments = [[1, 4, 5], [1, 7, 7], [4, 7, 12]]
print(describe_painting(segments))import java.util.*;
public class IntervalTreeDescription {
public static class IntervalTree {
TreeMap<Integer, Integer> tree = new TreeMap<>();
public void addInterval(int start, int end, int color) {
tree.put(start, tree.getOrDefault(start, 0) + color);
tree.put(end, tree.getOrDefault(end, 0) - color);
}
public List<int[]> getResult() {
List<int[]> result = new ArrayList<>();
int currentSum = 0, lastPosition = -1;
for (Map.Entry<Integer, Integer> entry : tree.entrySet()) {
if (lastPosition != -1 && currentSum != 0) {
result.add(new int[]{lastPosition, entry.getKey(), currentSum});
}
currentSum += entry.getValue();
lastPosition = entry.getKey();
}
return result;
}
}
public static List<int[]> describePainting(int[][] segments) {
IntervalTree itree = new IntervalTree();
for (int[] seg : segments) {
itree.addInterval(seg[0], seg[1], seg[2]);
}
return itree.getResult();
}
public static void main(String[] args) {
int[][] segments = {{1, 4, 5}, {1, 7, 7}, {4, 7, 12}};
List<int[]> painting = describePainting(segments);
for (int[] seg : painting) {
System.out.println("[" + seg[0] + ", " + seg[1] + ", " + seg[2] + "]");
}
}
}#include <vector>
#include <iostream>
#include <map>
using namespace std;
class IntervalTree {
private:
map<int, int> tree; // Position to mixed color sum
public:
void addInterval(int start, int end, int color) {
tree[start] += color;
tree[end] -= color;
}
vector<vector<int>> getResult() {
vector<vector<int>> result;
int currentSum = 0;
int lastPosition = -1;
for (auto &entry : tree) {
if (lastPosition != -1 && currentSum != 0) {
result.push_back({lastPosition, entry.first, currentSum});
}
currentSum += entry.second;
lastPosition = entry.first;
}
return result;
}
};
vector<vector<int>> describePainting(vector<vector<int>>& segments) {
IntervalTree itree;
for (auto& seg : segments) {
itree.addInterval(seg[0], seg[1], seg[2]);
}
return itree.getResult();
}
int main() {
vector<vector<int>> segments = {{1, 4, 5}, {1, 7, 7}, {4, 7, 12}};
auto painting = describePainting(segments);
for (auto &seg: painting) {
cout << "[" << seg[0] << ", " << seg[1] << ", " << seg[2] << "]\n";
}
return 0;
}function describePainting(segments) {
let treemap = {};
for (const [start, end, color] of segments) {
if (start in treemap) treemap[start] += color;
else treemap[start] = color;
if (end in treemap) treemap[end] -= color;
else treemap[end] = -color;
}
let currentSum = 0, lastPosition = null, result = [];
for (const pos of Object.keys(treemap).map(Number).sort((a, b) => a - b)) {
if (lastPosition !== null && currentSum != 0) {
result.push([lastPosition, pos, currentSum]);
}
currentSum += treemap[pos];
lastPosition = pos;
}
return result;
}
const segments = [[1, 4, 5], [1, 7, 7], [4, 7, 12]];
console.log(describePainting(segments));// Due to the complexity of implementing an efficient interval tree in C, a pseudocode description might be more appropriate here. Here's a higher level description:
// 1. Implement an interval tree using a struct that supports range insertion and query.
// 2. Parse segments into this structure, supporting overlap detection and management.
// 3. When adding a segment, calcualte the new mixture, updating stored sums where overlaps exist.
// 4. Once all segments are processed, extract non-overlapping resulting intervals from the tree with their associated sums.using System;
using System.Collections.Generic;
class IntervalTreeController {
public class IntervalTree {
SortedDictionary<int, int> tree = new SortedDictionary<int, int>();
public void AddInterval(int start, int end, int color) {
if (!tree.ContainsKey(start)) tree[start] = 0;
if (!tree.ContainsKey(end)) tree[end] = 0;
tree[start] += color;
tree[end] -= color;
}
public List<int[]> Result() {
List<int[]> result = new List<int[]>();
int currentSum = 0;
int lastPosition = -1;
foreach (var entry in tree) {
if (lastPosition != -1 && currentSum != 0)
result.Add(new int[] {lastPosition, entry.Key, currentSum});
currentSum += entry.Value;
lastPosition = entry.Key;
}
return result;
}
}
public static List<int[]> DescribePainting(int[][] segments) {
IntervalTree itree = new IntervalTree();
foreach (var seg in segments) {
itree.AddInterval(seg[0], seg[1], seg[2]);
}
return itree.Result();
}
public static void Main() {
int[][] segments = new int[][] { new int[] {1, 4, 5}, new int[] {1, 7, 7}, new int[] {4, 7, 12} };
var painting = DescribePainting(segments);
foreach (var seg in painting) {
Console.WriteLine($"[{seg[0]}, {seg[1]}, {seg[2]}]");
}
}
}This Python solution uses a dictionary to model the interval tree. Adjustments to endpoints efficiently control the overall summed colors, composing the final segments as the dictionary is processed in order.
Time complexity: O(n log n) - The sorting operation ensures efficient ordering to process segments.
Space complexity: O(n), maintaining tree data as dictionary entries.
Approach 3: Default Approach
func splitPainting(segments [][]int) [][]int64 {
d := make(map[int]int64)
for _, seg := range segments {
d[seg[0]] += int64(seg[2])
d[seg[1]] -= int64(seg[2])
}
dList := make([]int, 0, len(d))
for k := range d {
dList = append(dList, k)
}
sort.Ints(dList)
var ans [][]int64
i := dList[0]
cur := d[i]
for j := 1; j < len(dList); j++ {
it := d[dList[j]]
if cur > 0 {
ans = append(ans, []int64{int64(i), int64(dList[j]), cur})
}
cur += it
i = dList[j]
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sweep Line Technique with Events | Time complexity: O(n log n) for sorting. |
| Interval Tree Approach | Time complexity: O(n log n) - The sorting operation ensures efficient ordering to process segments. |
| Default Approach | – |
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. |
Frequently asked questions
Is Describe the Painting easy or hard?
The problem is generally rated Medium. The logic becomes straightforward once you recognize it as a sweep line event problem, but many candidates initially try complex interval merging strategies before identifying the prefix sum boundary trick.
Describe the Painting Python/Java solution
Both Python and Java implementations follow the same sweep line idea. Store boundary changes in a dictionary or TreeMap, sort the keys, maintain a running color sum, and record segments between consecutive coordinates when the sum is non‑zero. This keeps the algorithm O(n log n) with O(n) extra memory.
How to solve Describe the Painting in O(n log n)?
Create a map or array that records color changes at each boundary. For every segment [start, end, color], add +color at start and -color at end. Sort all unique coordinates and iterate through them while maintaining a running sum of colors. Whenever the current sum is positive, the region between consecutive coordinates forms a painted segment with that color value.
What is the best approach for Describe the Painting?
The sweep line technique with event points is the most efficient and simplest solution. Convert each interval into two events: +color at the start and -color at the end. After sorting event positions, maintain a running prefix sum of active colors and output segments where the value is non‑zero. The overall complexity is O(n log n) due to sorting.
Is Describe the Painting asked at Google/Amazon/Meta?
Problems involving sweep line processing and interval merging frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this question test understanding of interval events, prefix accumulation, and efficient handling of overlapping ranges.
What data structure is used in Describe the Painting?
The typical implementation uses a hash map or ordered map to store boundary events and a sorted list of keys to process them. The algorithm also relies on prefix sums to maintain the current color value while sweeping across coordinates.
What is the time complexity of Describe the Painting?
The optimal sweep line solution runs in O(n log n) time because all interval boundaries must be sorted before processing. The traversal afterward is linear across the unique event points. Space complexity is O(n) for storing boundary events and the resulting segments.