Amount of New Area Painted Each Day - Practice Coding Problems

Amount of New Area Painted Each Day - Problem

There is a long and thin painting that can be represented by a number line. You are given a 0-indexed 2D integer array paint of length n, where paint[i] = [start_i, end_i].

This means that on the i-th day you need to paint the area between start_i and end_i. Painting the same area multiple times will create an uneven painting so you only want to paint each area of the painting at most once.

Return an integer array worklog of length n, where worklog[i] is the amount of new area that you painted on the i-th day.

Input & Output

Example 1 — Basic Overlapping

$ Input: paint = [[1,4],[4,7],[5,8]]

› Output: [3,3,1]

💡 Note: Day 1: paint [1,4) → 3 new units. Day 2: paint [4,7) → 3 new units. Day 3: paint [5,8) → only position 7 is new (positions 5,6 already painted) → 1 new unit.

Example 2 — Complete Overlap

$ Input: paint = [[1,4],[2,3],[4,6]]

› Output: [3,0,2]

💡 Note: Day 1: paint [1,4) → 3 new units. Day 2: paint [2,3) → completely inside [1,4), 0 new units. Day 3: paint [4,6) → 2 new units.

Example 3 — No Overlap

$ Input: paint = [[1,2],[3,4],[5,6]]

› Output: [1,1,1]

💡 Note: All intervals are disjoint, each day paints exactly 1 new unit.

Constraints

1 ≤ paint.length ≤ 2 × 10⁴
paint[i].length == 2
0 ≤ start_i < end_i ≤ 5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of [start,end) painting intervals for each day

Process

Track painted areas, count only new unpainted regions

Output

Array of new areas painted each day

Key Takeaway

🎯 Key Insight: Only count unpainted areas when painting new intervals - avoid double painting!

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is tracking painted areas efficiently to avoid redundant painting. The brute force approach uses a set to track every painted position. The optimized approach maintains intervals and merges overlaps. Best approach depends on range size vs. number of intervals. Time: O(n × r) brute force, O(n²) interval merging. Space: O(r) or O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Interval Merging Approach	O(n²)	O(n)	Maintain sorted list of painted intervals and merge overlaps
Brute Force with Set Tracking	O(n × r)	O(r)	Track every painted position using a set

Interval Merging Approach — Algorithm Steps

Maintain sorted list of painted intervals
For each new interval, find all overlapping intervals
Merge overlapping intervals and calculate new area
Update the interval list

Visualization

Tap to expand

Step-by-Step Walkthrough

Day 1

Paint [1,4) - no existing intervals, add new area 3

Day 2

Paint [3,6) - overlaps with [1,4) at position 3, merge intervals

Result

New merged interval [1,6), only 2 new units painted

Code -

solution.c — C

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

typedef struct {
    int start, end;
} Interval;

int* solution(int** paint, int paintSize, int* returnSize) {
    Interval intervals[1000];
    int intervalCount = 0;
    int* worklog = (int*)malloc(paintSize * sizeof(int));
    *returnSize = paintSize;
    
    for (int i = 0; i < paintSize; i++) {
        int start = paint[i][0];
        int end = paint[i][1];
        int newArea = end - start;
        
        int toRemove[1000];
        int removeCount = 0;
        int mergedStart = start;
        int mergedEnd = end;
        
        for (int j = 0; j < intervalCount; j++) {
            if (intervals[j].end <= start || intervals[j].start >= end) {
                continue;
            }
            
            int overlapStart = (start > intervals[j].start) ? start : intervals[j].start;
            int overlapEnd = (end < intervals[j].end) ? end : intervals[j].end;
            newArea -= (overlapEnd - overlapStart);
            
            mergedStart = (mergedStart < intervals[j].start) ? mergedStart : intervals[j].start;
            mergedEnd = (mergedEnd > intervals[j].end) ? mergedEnd : intervals[j].end;
            toRemove[removeCount++] = j;
        }
        
        for (int j = removeCount - 1; j >= 0; j--) {
            int idx = toRemove[j];
            for (int k = idx; k < intervalCount - 1; k++) {
                intervals[k] = intervals[k + 1];
            }
            intervalCount--;
        }
        
        intervals[intervalCount].start = mergedStart;
        intervals[intervalCount].end = mergedEnd;
        intervalCount++;
        
        worklog[i] = newArea;
    }
    
    return worklog;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** paint = (int**)malloc(1000 * sizeof(int*));
    int paintSize = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            if (paintSize % 2 == 0) {
                paint[paintSize / 2] = (int*)malloc(2 * sizeof(int));
                paint[paintSize / 2][0] = atoi(token);
            } else {
                paint[paintSize / 2][1] = atoi(token);
            }
            paintSize++;
        }
        token = strtok(NULL, "[],\n");
    }
    paintSize /= 2;
    
    int returnSize;
    int* result = solution(paint, paintSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each day, we may need to scan and merge up to n existing intervals

⚠ Quadratic Growth

Space Complexity

O(n)

Store up to n non-overlapping intervals

⚡ Linearithmic Space

34.5K Views

Medium Frequency

~35 min Avg. Time

892 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

Interval Merging Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler