Scale Engineer

Describe the Painting

Med
#1772Time: O(N * M), where N is the number of segments and M is the maximum coordinate. Populating the `colorSums` array dominates the runtime, as for each segment, we might iterate up to M times.Space: O(M), where M is the maximum coordinate value. This is for storing the `colorSums` array.
Patterns
Prefix Sum
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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, and 6 are 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 by painting = [[1,4,12],[4,7,7]] because:
    • [1,4) is colored {5,7} (with a sum of 12) 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 * 104
  • segments[i].length == 3
  • 1 <= starti < endi <= 105
  • 1 <= colori <= 109
  • Each colori is distinct.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach simulates the painting process directly on a number line represented by an array. It iterates through every point for every segment, accumulating the color values. This is straightforward but highly inefficient for large coordinates.

Algorithm

  • Find the maximum coordinate max_coord from all segments.
  • Create a long array color_sums of size max_coord + 1.
  • For each segment [start, end, color]:
    • For i from start to end - 1, color_sums[i] += color.
  • Initialize an empty list painting for the results.
  • Iterate from i = 1 to max_coord:
    • If the current point i has a color sum of 0, skip it.
    • Identify the start of a new colored segment: start = i.
    • Find the end of this segment by advancing a pointer j as long as color_sums[j] equals color_sums[start].
    • Add the new segment [start, j, color_sums[start]] to the painting list.
    • Continue the main loop from i = j.
  • Return the painting list.

Walkthrough

We first determine the maximum coordinate max_coord present in the input segments. An array, let's call it color_sums, of size max_coord + 1 is created to store the final mixed color sum for each point on the number line. We then iterate through each segment [start, end, color]. For each segment, we loop from start to end - 1 and add the color to the corresponding index in the color_sums array. After processing all segments, the color_sums array holds the final mixed color sum for every point. The final step is to scan this color_sums array to consolidate adjacent points with the same color sum into single segments. We iterate through the array, and whenever we find a contiguous block of points with the same non-zero color sum, we form a new segment.

import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution {    public List<List<Long>> splitPainting(int[][] segments) {        int maxCoord = 0;        for (int[] segment : segments) {            maxCoord = Math.max(maxCoord, segment[1]);        }         long[] colorSums = new long[maxCoord + 1];        for (int[] segment : segments) {            int start = segment[0];            int end = segment[1];            int color = segment[2];            for (int i = start; i < end; i++) {                colorSums[i] += color;            }        }         List<List<Long>> result = new ArrayList<>();        int i = 1;        while (i <= maxCoord) {            if (colorSums[i] == 0) {                i++;                continue;            }            long currentSum = colorSums[i];            int start = i;            int j = i;            while (j <= maxCoord && colorSums[j] == currentSum) {                j++;            }            result.add(Arrays.asList((long)start, (long)j, currentSum));            i = j;        }        return result;    }}

Complexity

Time

O(N * M), where N is the number of segments and M is the maximum coordinate. Populating the `colorSums` array dominates the runtime, as for each segment, we might iterate up to M times.

Space

O(M), where M is the maximum coordinate value. This is for storing the `colorSums` array.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Very inefficient in terms of time and space if the coordinate range is large.

  • Leads to Time Limit Exceeded on most platforms for the given constraints.

Solutions

class Solution {public  List<List<Long>> splitPainting(int[][] segments) {    TreeMap<Integer, Long> d = new TreeMap<>();    for (int[] e : segments) {      int l = e[0], r = e[1], c = e[2];      d.put(l, d.getOrDefault(l, 0L) + c);      d.put(r, d.getOrDefault(r, 0L) - c);    }    List<List<Long>> ans = new ArrayList<>();    long i = 0, j = 0;    long cur = 0;    for (Map.Entry<Integer, Long> e : d.entrySet()) {      if (Objects.equals(e.getKey(), d.firstKey())) {        i = e.getKey();      } else {        j = e.getKey();        if (cur > 0) {          ans.add(Arrays.asList(i, j, cur));        }        i = j;      }      cur += e.getValue();    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem