1943. Describe the Painting LeetCode Solution

Last updated: February 25, 2025

In this guide, you will get 1943. Describe the Painting LeetCode Solution with the best time and space complexity. The solution to Describe the Painting problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Describe the Painting solution in C++
Describe the Painting solution in Java
Describe the Painting solution in Python
Additional Resources

1943. Describe the Painting LeetCode Solution image

Problem Statement of Describe the Painting

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.

Complexity Analysis

Time Complexity: O(\texttt{sort} + n\log n)
Space Complexity: O(n)

1943. Describe the Painting LeetCode Solution in C++

class Solution {
 public:
  vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
    vector<vector<long long>> ans;
    int prevIndex = 0;
    long runningMix = 0;
    map<int, long> timeline;

    for (const vector<int>& segment : segments) {
      const int start = segment[0];
      const int end = segment[1];
      const int color = segment[2];
      timeline[start] += color;
      timeline[end] -= color;
    }

    for (const auto& [i, mix] : timeline) {
      if (runningMix > 0)
        ans.push_back({prevIndex, i, runningMix});
      runningMix += mix;
      prevIndex = i;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1943. Describe the Painting LeetCode Solution in Java

class Solution {
  public List<List<Long>> splitPainting(int[][] segments) {
    List<List<Long>> ans = new ArrayList<>();
    int prevIndex = 0;
    long runningMix = 0;
    TreeMap<Integer, Long> timeline = new TreeMap<>();

    for (int[] segment : segments) {
      final int start = segment[0];
      final int end = segment[1];
      final int color = segment[2];
      timeline.merge(start, (long) color, Long::sum);
      timeline.merge(end, (long) -color, Long::sum);
    }

    for (final int i : timeline.keySet()) {
      final long mix = timeline.get(i);
      if (runningMix > 0)
        ans.add(List.of((long) prevIndex, (long) i, runningMix));
      runningMix += mix;
      prevIndex = i;
    }

    return ans;
  }
}
// code provided by PROGIEZ

1943. Describe the Painting LeetCode Solution in Python

from sortedcontainers import SortedDict


class Solution:
  def splitPainting(self, segments: list[list[int]]) -> list[list[int]]:
    ans = []
    prevIndex = 0
    runningMix = 0
    timeline = SortedDict()

    for start, end, color in segments:
      timeline[start] = timeline.get(start, 0) + color
      timeline[end] = timeline.get(end, 0) - color

    for i, mix in timeline.items():
      if runningMix > 0:
        ans.append([prevIndex, i, runningMix])
      runningMix += mix
      prevIndex = i

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents