# Describe the Painting
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/describe-the-painting)
Canonical: https://scaleengineer.com/dsa/problems/describe-the-painting
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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:**

![](https://assets.glich.co/dsa/describe-the-painting/image0.png) 

**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:**

![](https://assets.glich.co/dsa/describe-the-painting/image1.png) 

**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:**

![](https://assets.glich.co/dsa/describe-the-painting/image2.png) 

**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
## Brute Force with Coordinate Array
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Sweep-line Algorithm
This approach treats the start and end points of segments as events along the number line. By processing these events in sorted order of their position, we can efficiently calculate the mixed color sum for the intervals between consecutive event points.
**Time:** O(N log N), where N is the number of segments. Populating the `TreeMap` takes `O(N log K)` where `K` is the number of unique endpoints (`K <= 2N`), so it's effectively `O(N log N)`. Iterating through the map takes `O(K)` or `O(N)`. · **Space:** O(N), where N is the number of segments. This space is used to store the events in the `TreeMap`.
**Pros:** Much more efficient than brute force when coordinates are sparse or the range is large.; Space usage depends only on the number of segments, not the coordinate range.
**Cons:** The `log N` factor from sorting or using a tree-based map makes it slightly slower than the difference array approach for the given constraints where `M` is not excessively larger than `N`.
### Explanation
The core idea is that the mixed color sum only changes at the start or end points of the input segments. These points are our 'event points'. We can represent each segment `[start, end, color]` as two events: a color addition `+color` at `start`, and a color subtraction `-color` at `end`. We use a data structure that keeps these events sorted by coordinate, like a `TreeMap` in Java, where keys are coordinates and values are the net color change at that coordinate. After populating the map, we iterate through its entries, which are already sorted by coordinate. We maintain a `current_color_sum` and the `last_pos`. Between two consecutive event points `last_pos` and `current_pos`, the color sum is constant. If this sum is positive, we form a segment `[last_pos, current_pos, current_color_sum]`. We also handle merging adjacent segments that happen to have the same mixed color sum to ensure the output is minimal.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

class Solution {
    public List<List<Long>> splitPainting(int[][] segments) {
        Map<Integer, Long> map = new TreeMap<>();
        for (int[] s : segments) {
            map.put(s[0], map.getOrDefault(s[0], 0L) + s[2]);
            map.put(s[1], map.getOrDefault(s[1], 0L) - s[2]);
        }

        List<List<Long>> result = new ArrayList<>();
        long currentSum = 0;
        int lastPos = -1;

        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            int pos = entry.getKey();
            long change = entry.getValue();

            if (lastPos != -1 && pos > lastPos) {
                if (currentSum > 0) {
                    if (!result.isEmpty() && result.get(result.size() - 1).get(1) == (long)lastPos && result.get(result.size() - 1).get(2) == currentSum) {
                        result.get(result.size() - 1).set(1, (long)pos);
                    } else {
                        result.add(Arrays.asList((long)lastPos, (long)pos, currentSum));
                    }
                }
            }
            
            currentSum += change;
            lastPos = pos;
        }

        return result;
    }
}
```
### Algorithm
- Create a `TreeMap<Integer, Long>` to store color changes at each coordinate. The map will automatically keep coordinates sorted.
- For each segment `[start, end, color]`:
    - Add `color` to the value at key `start`.
    - Subtract `color` from the value at key `end`.
- Initialize an empty list `painting`, a `long current_sum = 0`, and an `int last_pos`.
- Iterate through the `(pos, change)` entries of the `TreeMap`:
    - If `last_pos` is valid and the `current_sum` is positive, it means the interval `[last_pos, pos)` was painted. Create a segment `[last_pos, pos, current_sum]`.
    - Before adding, check if it can be merged with the last segment in `painting`. Merging is possible if the new segment starts exactly where the last one ended and they have the same color sum.
    - If mergeable, update the end of the last segment. Otherwise, add the new segment.
    - Update `current_sum` by adding `change`.
    - Update `last_pos` to `pos`.
- Return the `painting` list.

## Difference Array with Prefix Sum
This approach is an optimization over the brute-force method. Instead of updating every point in a segment, we only mark the changes at the start and end points in a 'difference array'. Then, a single pass to compute prefix sums gives the final color sum for each point. This is highly efficient when the maximum coordinate is not excessively large.
**Time:** O(N + M), where N is the number of segments and M is the maximum coordinate. It takes `O(N)` to find `maxCoord` and populate the difference array, `O(M)` to compute prefix sums, and `O(M)` to build the final segments. · **Space:** O(M), where M is the maximum coordinate. This is for the difference array and the final color sum array.
**Pros:** Very fast for the given constraints.; Linear time complexity with respect to the number of segments and the maximum coordinate.
**Cons:** Requires space proportional to the maximum coordinate, which can be an issue if coordinates are not bounded reasonably.
### Explanation
This method avoids the `O(N*M)` complexity of the naive approach by being smarter about updates. First, we find the maximum coordinate `max_coord`. We create a difference array `diff` of size `max_coord + 2`. For each segment `[start, end, color]`, we perform two operations: `diff[start] += color` and `diff[end] -= color`. This marks that from `start` onwards, the color sum increases by `color`, and from `end` onwards, this contribution is removed. After processing all segments, we can determine the actual color sum at each point `i` by calculating the prefix sum of the `diff` array. We can build the final `colorSums` array and then scan it to form the segments, similar to the brute-force approach's final step. This combines the efficiency of the difference array with a simple segmentation logic.

```java
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[] s : segments) {
            maxCoord = Math.max(maxCoord, s[1]);
        }
        
        long[] diff = new long[maxCoord + 2];
        for (int[] s : segments) {
            diff[s[0]] += s[2];
            diff[s[1]] -= s[2];
        }
        
        // First, create the final color sum array from the difference array
        long[] colorSums = new long[maxCoord + 1];
        long currentSum = 0;
        for (int i = 1; i <= maxCoord; i++) {
            currentSum += diff[i];
            colorSums[i] = currentSum;
        }
        
        // Second, build segments from the color sum array
        List<List<Long>> painting = new ArrayList<>();
        int i = 1;
        while (i <= maxCoord) {
            if (colorSums[i] == 0) {
                i++;
                continue;
            }
            long sum = colorSums[i];
            int j = i;
            while (j <= maxCoord && colorSums[j] == sum) {
                j++;
            }
            painting.add(Arrays.asList((long)i, (long)j, sum));
            i = j;
        }
        return painting;
    }
}
```
### Algorithm
- Find the maximum end coordinate `max_coord`.
- Create a `long` array `diff` of size `max_coord + 2`.
- For each segment `[s, e, c]`, perform `diff[s] += c` and `diff[e] -= c`.
- Create a `long` array `colorSums` of size `max_coord + 1`.
- Compute the prefix sums of `diff` to populate `colorSums`: `colorSums[i] = colorSums[i-1] + diff[i]` (conceptually, though `diff` is used directly in the code).
- Scan the `colorSums` array to build the final `painting` list by grouping adjacent points with the same non-zero color sum into segments.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<long long>> splitPainting(vector<vector<int>> &segments) {
    map<int, long long> d;
    for (auto &e : segments) {
      int l = e[0], r = e[1], c = e[2];
      d[l] += c;
      d[r] -= c;
    }
    vector<vector<long long>> ans;
    long long i, j, cur = 0;
    for (auto &it : d) {
      if (it == *d.begin())
        i = it.first;
      else {
        j = it.first;
        if (cur > 0)
          ans.push_back({i, j, cur});
        i = j;
      }
      cur += it.second;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]: d = defaultdict(int) for l, r, c in segments: d[l] += c d[r] -= c s = sorted([[k, v] for k, v in d . items()]) n = len(s) for i in range(1, n): s[i][1] += s[i - 1][1] return [[s[i][0], s[i + 1][0], s[i][1]] for i in range(n - 1) if s[i][1]]

```