Describe the Painting

Medium
1440.

Describe the Painting

Describe the Painting is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

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^4
  • segments[i].length == 3
  • 1 <= start_i < end_i <= 10^5
  • 1 <= color_i <= 10^5
  • each color_i is distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} segments
 * @return {number[][]}
 */
var splitPainting = function(segments) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • segments[i].length == 3
  • 1 <= start_i < end_i <= 10^5
  • 1 <= color_i <= 10^5
  • each color_i is distinct

Hints for Describe the Painting

  1. Hint 1

    The colour set can only change at a stroke's start or end.

  2. Hint 2

    Because colours are distinct, it does change at every such point — so every endpoint is a boundary between pieces.

  3. Hint 3

    Sweep the endpoints in order keeping the running sum (+color at a start, -color at 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

  1. Create events (start, +color) and (end, -color) for every stroke and sort them by position.
  2. Walk the events grouped by equal position x, adding all their deltas to running.
  3. If another position y follows and running > 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 out

Java

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