1943. Describe the Painting

Problem Description

In this problem, we're asked to describe a painted mural represented as a series of segments on a number line, with each segment colored in a unique color. These segments can overlap, and when they do, the colors mix. The mixing of colors is not a blend but rather a union of distinct colors, and what's interesting is that you only need to report the sum of the mixed colors, rather than the set of colors themselves.

Each segment is defined by its start and end points, and its unique color value which is a number. What complicates the problem is that the mixing of colors from overlapping segments can create a patchwork of colored segments where each part may have a different mixed color.

Our task is to reduce this patchwork of segments into the minimum number of non-overlapping half-closed segments. These segments should capture the color mixing effect, and this final simplified description must exclude any part of the canvas that has not been painted. As an added twist, the segments in the output can be presented in any order.

We are provided with a 2D integer array segments where segments[i] = [start_i, end_i, color_i]. We need to return another 2D array painting which represents these simplified half-closed segments [left_j, right_j, mix_j] with mix_j being the sum of colors on that segment.

A half-closed segment [a, b) includes point a but not point b.


To solve this problem, we need to find a way to efficiently represent the changes in color on the mural due to the overlapping segments. We need to account for when a new color starts (an increase in the sum of colors), when a color ends (a decrease in the sum), and maintain this accounting across the entire range of the painting.

The solution follows a common pattern in interval problems which involves marking the start and end of each segment with their corresponding color contributions using a dictionary or map. The key insight is to recognize that the coloring changes only at the endpoints of each segment (start and end). We don't care about the middle of the segments, since any internal points will just inherit the current mix of colors up to that point.

We use a dictionary to accumulate the color value (positive at the start, negative at the end) for each unique point on the number line where a color starts or ends. After processing all segments, we sort this dictionary to prepare for a sweep along the number line.

During the sweep, we accumulate the color values. If the accumulated color value is nonzero, it indicates that we have a painted segment. As we move from one point to the next, we detect changes in accumulated color values which mark the end of one segment and potentially the start of a new one.

The final result is obtained by creating segments between points where the color value changes from non-zero to another non-zero value. We ignore transitions from or to zero since this indicates an unpainted part of the mural.

By the end of this processing, we collect a list of the simplified half-closed segments, each with its sum of mixed colors, effectively compressing the painting into the desired output.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following array represent a max heap?

Solution Approach

The solution utilizes a common technique in dealing with intervals or segments: marking the start and end points and then performing a "sweep" line approach, moving through the entire range of the mural to accumulate changes and construct the final set of segments.

Here is a step-by-step explanation of the process using a dictionary and a sorting strategy:

  1. Use a Dictionary: A dictionary, named d, is initialized to keep track of the start and end points of segments and how they influence the color changes at those points. Data structure choice is essential: a dictionary allows for efficient updates and lookups.

  2. Mark the Changes: Iterate through each segment, represented by (l, r, c), and modify the dictionary: increment the value at the start point l by c and decrement the value at the end point r by c. This sets up our "events" where color changes will occur.

  3. Sort the Points: Transform the dictionary into a sorted list, s, of tuples (k, v) where k is the point on the number line and v is the accumulated change in color at that point. Sorting by the number line ensures we'll process events in the correct order.

  4. Accumulate Color Changes: Iterate through the sorted list, accumulating the color values to track the current color sum. This accumulation reflects the presence of possibly multiple overlapping segments at each point.

  5. Build Resulting Segments: After accumulating the color values, iterate through the sorted list again, using s[i][1] to check if this segment should be added to the final output. A segment is created between consecutive points s[i][0] and s[i+1][0], with the color sum as the third element, but only if s[i][1] is non-zero. This inclusion check ensures that we don't consider unpainted parts of the mural.

  6. Return the Result: Construct the solution as a list of half-closed segments [s[i][0], s[i + 1][0], s[i][1]], where i ranges from 0 to n-2. Each of these segments has a start point, an end point, and a mixed color sum representing the painting described by the input array segments.

By employing this approach, the implementation details the specifics of processing intervals with efficient data structures like a dictionary for marking changes, sorting to prepare for a linear sweep, and accumulation to monitor the ongoing color sum. The code avoids unnecessary complexity, which can typically arise with overlapping intervals, by distilling the problem down to its essence: we only care about the points where color changes happen, and these are the starts and ends of the given segments.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's consider the following example to illustrate the solution approach. Suppose we're given the following array of segments as input:

1segments = [[1, 4, 5], [3, 7, 6], [6, 8, 3]]

Each inner array represents a segment with start point, end point, and a unique color coded as a number.

  1. Use a Dictionary: We initiate a dictionary d to keep track of points and their corresponding color changes. Currently, d is empty.

  2. Mark the Changes: We process each segment in the segments array:

    • For the segment [1, 4, 5], we update d to reflect the start and end color effects:
      • d[1] is incremented by 5 (since 5 is the color at the start point).
      • d[4] is decremented by 5 (since 5 is the color at the end point).
    • For [3, 7, 6], we do analogously:
      • d[3] is incremented by 6.
      • d[7] is decremented by 6.
    • For [6, 8, 3], we update again:
      • d[6] is incremented by 3.
      • d[8] is decremented by 3.

    After processing all segments, our dictionary may look something like this:

    1d = {
    2  1: 5,
    3  4: -5,
    4  3: 6,
    5  7: -6,
    6  6: 3,
    7  8: -3
  3. Sort the Points: We then sort the keys of our dictionary d to get an ordered list of color change events. This list, s, becomes:

    1s = [(1, 5), (3, 6), (4, -5), (6, 3), (7, -6), (8, -3)]
  4. Accumulate Color Changes: We iterate through s and keep track of the cumulative color. We keep adding (or subtracting if negative) the values corresponding to the points:

    • After (1, 5), cumulative color is 5.
    • After (3, 6), cumulative color increases to 11 (5 + 6).
    • At (4, -5), it decreases to 6 (11 - 5).
    • At (6, 3), it goes back to 9 (6 + 3).
    • And so on, until we go through all points.
  5. Build Resulting Segments: When the cumulative color value changes from one non-zero value to another, we add a new segment to our output result. After processing the sorted list, the output might look like this:

    1painting = [[1, 3, 5], [3, 4, 11], [4, 6, 6], [6, 7, 9], [7, 8, 3]]

    We can see that each new segment in painting starts where the last one ended, representing the mixed colors appropriately.

  6. Return the Result: This painting now represents the simplified list of half-closed segments capturing the color mixing effect, which is exactly what the problem asks for.

By using this technique, we have efficiently compressed the original series of overlapping colored segments into a simplified and non-overlapping representation, accurately reflecting the mix of colors on the mural with the order being of no significance.

Solution Implementation

1from collections import defaultdict
3class Solution:
4    def splitPainting(self, segments):
5        # Create a dictionary to store the net color changes at each point
6        color_changes = defaultdict(int)
8        # Record the color change at the start and end of each segment
9        for start, end, color in segments:
10            color_changes[start] += color  # Color starts at this point
11            color_changes[end] -= color    # Color ends at this point
13        # Sort the color change points
14        sorted_points = sorted([[pos, change] for pos, change in color_changes.items()])
16        # Iterate through the sorted points to accumulate color values
17        for i in range(1, len(sorted_points)):
18            sorted_points[i][1] += sorted_points[i - 1][1]
20        # Generate the result with accumulated color segments
21        # Only include segments where the total color is non-zero
22        result = [
23            [sorted_points[i][0], sorted_points[i + 1][0], sorted_points[i][1]]
24            for i in range(len(sorted_points) - 1)
25            if sorted_points[i][1]
26        ]
28        return result
1import java.util.TreeMap;
2import java.util.ArrayList;
3import java.util.List;
4import java.util.Map;
5import java.util.Objects;
6import java.util.Arrays;
8class Solution {
9    public List<List<Long>> splitPainting(int[][] segments) {
10        // A TreeMap stores unique keys in sorted order, along with their corresponding values.
11        // Here, keys track the position on the canvas and values track paint color changes.
12        TreeMap<Integer, Long> deltaMap = new TreeMap<>();
14        // Process each paint segment and update the deltas for start and end points
15        for (int[] segment : segments) {
16            int start = segment[0], end = segment[1];
17            long color = segment[2];
18            // Increase color value at the start point
19            deltaMap.put(start, deltaMap.getOrDefault(start, 0L) + color);
20            // Decrease color value at the end point
21            deltaMap.put(end, deltaMap.getOrDefault(end, 0L) - color);
22        }
24        // Prepare a list to store the result segments
25        List<List<Long>> result = new ArrayList<>();
26        long previousPosition = 0, currentPosition = 0;
27        long currentColorSum = 0;
29        // Go through each entry in the map to create the painted segments
30        for (Map.Entry<Integer, Long> entry : deltaMap.entrySet()) {
31            // If it's the first key, initialize the previous position.
32            if (Objects.equals(entry.getKey(), deltaMap.firstKey())) {
33                previousPosition = entry.getKey();
34            } else {
35                currentPosition = entry.getKey();
36                // If the color sum is positive, add the segment to the result list.
37                if (currentColorSum > 0) {
38                    result.add(Arrays.asList(previousPosition, currentPosition, currentColorSum));
39                }
40                // Update the previous position for the next iteration
41                previousPosition = currentPosition;
42            }
43            // Update the color sum with the delta value
44            currentColorSum += entry.getValue();
45        }
46        return result;
47    }
1#include <vector>
2#include <map>
3using namespace std;
5class Solution {
7    vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
8        // Using `std::map` to track the color changes at each point.
9        map<int, long long> colorDelta;
11        // Process each segment, adding or subtracting color values at the start and end points.
12        for (const auto& segment : segments) {
13            int start = segment[0];
14            int end = segment[1];
15            long long color = segment[2];
16            colorDelta[start] += color;
17            colorDelta[end] -= color;
18        }
20        // Preparing the result as a vector of vectors to store the painted segments.
21        vector<vector<long long>> result;
22        // Variables to hold the start, current position, and current color value while iterating.
23        long long startPos, endPos, currentColor = 0;
25        // Iterate over the map to build the list of colored segments.
26        for (auto it = colorDelta.begin(); it != colorDelta.end(); ++it) {
27            if (it == colorDelta.begin()) {
28                // Mark the start position at the beginning
29                startPos = it->first;
30            } else {
31                // Set the end position for the current segment.
32                endPos = it->first;
34                // Add the segment to the result if it has a color.
35                if (currentColor > 0) {
36                    result.push_back({startPos, endPos, currentColor});
37                }
39                // Update the start position for the next segment.
40                startPos = endPos;
41            }
43            // Update the current color with the delta at this position.
44            currentColor += it->second;
45        }
47        // Return the list of colored segments.
48        return result;
49    }
1type Segment = [number, number, number]; // Using tuple for segments [start, end, color]
3// Map to track the color changes at each point
4let colorDelta: Map<number, number> = new Map();
6// Stores the painted segments as an array of tuples.
7let result: Segment[] = [];
9// Function to process the segments and return the painting
10function splitPainting(segments: Segment[]): Segment[] {
11    // Initialize or reset variables for each call
12    colorDelta.clear();
13    result = [];
15    // Process each segment, adding or subtracting the color values at the start and end points
16    segments.forEach(segment => {
17        const [start, end, color] = segment;
18        colorDelta.set(start, (colorDelta.get(start) || 0) + color);
19        colorDelta.set(end, (colorDelta.get(end) || 0) - color);
20    });
22    // Using null to signal unset values for TypeScript
23    let startPos: number | null = null;
24    let endPos: number;
25    let currentColor: number = 0;
27    // Sort the keys to iterate over the map in order
28    const sortedKeys = Array.from(colorDelta.keys()).sort((a, b) => a - b);
30    // Iterate over the map to build the list of colored segments
31    sortedKeys.forEach((position, index) => {
32        if(startPos === null) {
33            // Mark the start position at the beginning
34            startPos = position;
35        } else {
36            // Set the end position for the current segment
37            endPos = position;
39            // Add the segment to the result if it has a color
40            if (currentColor > 0) {
41                result.push([startPos, endPos, currentColor]);
42            }
44            // Update the start position for the next segment
45            startPos = endPos;
46        }
48        // Update the current color with the delta at this position
49        currentColor += colorDelta.get(position) || 0;
50    });
52    // Return the list of colored segments
53    return result;
Not Sure What to Study? Take the 2-min Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down into several parts:

  1. Iterating over segments: The input to the function is segments, a list of lists where each sublist has the format [l, r, c]. The code uses a for loop to iterate over these segments, applying operations that are constant time to each (updating the dictionary d). Therefore, this part has a time complexity of O(m), where m is the number of segments.

  2. Creating the sorted list s: The sorted function is then called on a list comprehension [k, v] for each key-value pair in the dictionary d. The sorted function has a time complexity of O(n log n), where n is the number of distinct keys in the dictionary d.

  3. Iterating over sorted list s: An in-place iteration to compute the cumulative sum of values is performed in a loop running from 1 to n. Since it's a simple accumulation of values, the time complexity is O(n) for this loop.

  4. List comprehension to construct the return list: Lastly, a list comprehension is used to create the final list of painting segments that should be returned. The list comprehension iterates n - 1 times to check the value of the cumulative color and make a list of the segments. This operation has a time complexity of O(n).

Combining all of these, the overall time complexity of the function is determined by the most time-consuming operation, which in this case is the sorting step. So, the overall time complexity of the code is O(n log n).

Space Complexity

For space complexity:

  1. Dictionary d: The space taken up by the dictionary is proportional to the number of distinct starting and ending points in the segments, which is O(n).

  2. Sorted list s: The list s has the same number of elements as the dictionary d, which is O(n).

  3. Return list: In the worst case, the return list will have as many segments as the input segments, because every segment might have a different color, which is O(m) space.

Overall, the space complexity combines the space for the dictionary d, the sorted list s, and the return list, which gives us O(n + m). Since m can be assumed to be less than or equal to 2n (each segment contributes two points at most), the space complexity can also be loosely represented as O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫