Describe the Painting — Solution in Python, Java & C++
Describe the Painting solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Describe the Painting is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A long, thin painting lies along a number line. It was painted with overlapping strokes: segments[i] = [start, end, color] paints the half-open range [start, end) with color. All colours are distinct.
Where strokes overlap, their colours mix. A mix is a set of colours, and we write it down as the sum of its colours (so a mix of 2, 4 and 6 is written 12).
Describe the painting with the fewest half-open pieces [left, right, mix] such that every point of a piece is painted with exactly the same set of colours. Leave out the parts that are not painted at all. Note that two neighbouring pieces must stay separate when their sets differ, even if their sums happen to be equal.
Return the pieces sorted by left.
Constraint note: colours are capped at 10^5 (the original allows 10^9) so every mix sum fits in a 32-bit integer.
Example 1
Input: segments = [[2,6,3],[4,9,5],[11,12,4]]
Output: [[2,4,3],[4,6,8],[6,9,5],[11,12,4]]
Explanation: [9,11) is unpainted and left out.
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]]
Example 3
Input: segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
Output: [[1,4,12],[4,7,12]]
Explanation: Both pieces sum to 12, but the sets {5,7} and {1,11} differ, so they are not merged.
Constraints
1 <= segments.length <= 2 * 10^4segments[i].length == 31 <= start_i < end_i <= 10^51 <= color_i <= 10^5each color_i is distinct
Hints for Describe the Painting
Hint 1
The colour set can only change at a stroke's
startorend.Hint 2
Because colours are distinct, it does change at every such point — so every endpoint is a boundary between pieces.
Hint 3
Sweep the endpoints in order keeping the running sum (
+colorat a start,-colorat an end); between two consecutive endpoints, emit a piece if the sum is positive.
How to solve Describe the Painting
Treat each stroke as +color at start and -color at end. Sorted by position, a running total gives the mix of every gap between consecutive event points, and with distinct colours every event point really is a boundary.
Approach
- Create events
(start, +color)and(end, -color)for every stroke and sort them by position. - Walk the events grouped by equal position
x, adding all their deltas torunning. - If another position
yfollows andrunning > 0, append[x, y, running].
Why it works
Between consecutive event positions no stroke begins or ends, so the colour set — and its sum running — is constant there. At an event position at least one stroke enters or leaves, and since all colours are distinct the set strictly changes, so a piece boundary is mandatory exactly there. Pieces with running == 0 are unpainted and skipped; positive colours mean a painted set never sums to 0.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Merging neighbours because their sums match is wrong — sets, not sums, decide (third example).
- Group all events at the same position before emitting, or zero-length pieces appear.
- With the original colour range the sums need 64 bits.
Reference solution
Python
from typing import List
def splitPainting(segments: List[List[int]]) -> List[List[int]]:
events = []
for start, end, color in segments:
events.append((start, color))
events.append((end, -color))
events.sort()
out = []
running = 0
i, m = 0, len(events)
while i < m:
x = events[i][0]
while i < m and events[i][0] == x:
running += events[i][1]
i += 1
if i < m and running > 0:
out.append([x, events[i][0], running])
return outJava
public static int[][] splitPainting(int[][] segments) {
int m = 2 * segments.length;
int[][] events = new int[m][];
for (int i = 0; i < segments.length; i++) {
events[2 * i] = new int[] { segments[i][0], segments[i][2] };
events[2 * i + 1] = new int[] { segments[i][1], -segments[i][2] };
}
Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> out = new ArrayList<>();
long running = 0;
int at = 0;
while (at < m) {
int x = events[at][0];
while (at < m && events[at][0] == x) running += events[at++][1];
if (at < m && running > 0) out.add(new int[] { x, events[at][0], (int) running });
}
return out.toArray(new int[0][]);
}C++
vector<vector<int>> splitPainting(vector<vector<int>>& segments) {
vector<pair<int, int>> events;
for (auto& s : segments) {
events.push_back({s[0], s[2]});
events.push_back({s[1], -s[2]});
}
sort(events.begin(), events.end());
vector<vector<int>> out;
long long running = 0;
size_t at = 0, m = events.size();
while (at < m) {
int x = events[at].first;
while (at < m && events[at].first == x) running += events[at++].second;
if (at < m && running > 0) out.push_back({x, events[at].first, (int) running});
}
return out;
}JavaScript
var splitPainting = function(segments) {
var events = [];
for (var i = 0; i < segments.length; i++) {
events.push([segments[i][0], segments[i][2]]);
events.push([segments[i][1], -segments[i][2]]);
}
events.sort(function(a, b) { return a[0] - b[0]; });
var out = [];
var running = 0, at = 0, m = events.length;
while (at < m) {
var x = events[at][0];
while (at < m && events[at][0] === x) {
running += events[at][1];
at++;
}
if (at < m && running > 0) out.push([x, events[at][0], running]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets