Describe the Painting - Practice Coding Problems

Describe the Painting - 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] = [start_i, end_i, color_i] represents the half-closed segment [start_i, end_i) with color_i 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] = [left_j, right_j, mix_j] describes a half-closed segment [left_j, right_j) with the mixed color sum of mix_j.

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.

Input & Output

Example 1 — Basic Overlapping

$ Input: segments = [[1,4,5],[4,7,7],[1,7,9]]

› Output: [[1,4,14],[4,7,16]]

💡 Note: Segment [1,4) has colors {5,9} with sum 14. Segment [4,7) has colors {7,9} with sum 16.

Example 2 — No Overlap

$ Input: segments = [[1,7,9],[6,10,15],[8,12,5]]

› Output: [[1,6,9],[6,7,24],[7,8,15],[8,10,20],[10,12,5]]

💡 Note: Multiple distinct segments with different color combinations at each interval.

Example 3 — Single Segment

$ Input: segments = [[1,4,5]]

› Output: [[1,4,5]]

💡 Note: Only one segment, so output is identical to input with no mixing.

Constraints

1 ≤ segments.length ≤ 2 × 10⁴
segments[i].length == 3
1 ≤ start_i < end_i ≤ 10⁵
1 ≤ color_i ≤ 10⁹
start_i < end_i

Visualization

Tap to expand

Understanding the Visualization

Input

Multiple colored segments on number line

Process

Find overlapping regions and sum colors

Output

Non-overlapping segments with mixed color sums

Key Takeaway

🎯 Key Insight: Use sweep line events to efficiently track when colors start and end, avoiding coordinate range limitations

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use an event-based sweep line algorithm to efficiently track color changes. Create start/end events for each segment, sort by position, then sweep through maintaining the active color sum. Best approach is Event-Based Sweep Line with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Event-Based Sweep Line	O(n log n)	O(n)	Use events to track color changes at boundary points
Brute Force - Check Every Point	O(n × r)	O(r)	Check each point to determine which colors are present

Event-Based Sweep Line — Algorithm Steps

Create events for segment starts (+color) and ends (-color)
Sort all events by position
Sweep through events, maintaining active color sum
Create output segments between position changes

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Events

Mark start (+color) and end (-color) positions

Sort & Sweep

Process events in order, tracking active colors

Build Segments

Create output segments between color changes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int pos;
    int color;
} Event;

int compareEvents(const void *a, const void *b) {
    Event *ea = (Event*)a;
    Event *eb = (Event*)b;
    return ea->pos - eb->pos;
}

int** solution(int** segments, int segmentsSize, int* segmentsColSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (segmentsSize == 0) return NULL;
    
    // Create events
    Event* events = (Event*)malloc(segmentsSize * 2 * sizeof(Event));
    int eventCount = 0;
    
    for (int i = 0; i < segmentsSize; i++) {
        events[eventCount++] = (Event){segments[i][0], segments[i][2]};   // Add color
        events[eventCount++] = (Event){segments[i][1], -segments[i][2]};  // Remove color
    }
    
    // Sort events by position
    qsort(events, eventCount, sizeof(Event), compareEvents);
    
    int** result = (int**)malloc(1000 * sizeof(int*));
    *returnColumnSizes = (int*)malloc(1000 * sizeof(int));
    
    int currentColorSum = 0;
    int prevPos = -1;
    int hasPrevPos = 0;
    
    int i = 0;
    while (i < eventCount) {
        int pos = events[i].pos;
        
        // Add previous segment if it exists and has color
        if (hasPrevPos && currentColorSum > 0 && prevPos < pos) {
            result[*returnSize] = (int*)malloc(3 * sizeof(int));
            result[*returnSize][0] = prevPos;
            result[*returnSize][1] = pos;
            result[*returnSize][2] = currentColorSum;
            (*returnColumnSizes)[*returnSize] = 3;
            (*returnSize)++;
        }
        
        // Process all events at this position
        while (i < eventCount && events[i].pos == pos) {
            currentColorSum += events[i].color;
            i++;
        }
        
        prevPos = pos;
        hasPrevPos = 1;
    }
    
    free(events);
    return result;
}

int main() {
    // Simplified parsing for demonstration
    int segments[][3] = {{1,4,5},{4,7,7},{1,7,9}};
    int* segmentPtrs[3];
    for (int i = 0; i < 3; i++) segmentPtrs[i] = segments[i];
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(segmentPtrs, 3, NULL, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d,%d]", result[i][0], result[i][1], result[i][2]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting n events dominates, sweep is O(n)

⚡ Linearithmic

Space Complexity

O(n)

Store events and result segments

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Event-Based Sweep Line — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler