LeetCode 2158 - Amount of New Area Painted Each Day

This problem describes a painting scenario represented as a one-dimensional number line. Each element in the input array paint[i] = [starti, endi] represents the section that needs to be painted on the ith day.

leetcodehardarraysegment-treeordered-set

LeetCode Problem 2158

Difficulty: 🔴 Hard
Topics: Array, Segment Tree, Ordered Set

Solution

Problem Understanding

This problem describes a painting scenario represented as a one-dimensional number line. Each element in the input array paint[i] = [starti, endi] represents the section that needs to be painted on the ith day. The goal is to calculate, for each day, how much new area is painted-i.e., the part of the segment that has not been painted on previous days. Painting the same area multiple times should be avoided.

The input is a list of intervals with constraints ensuring 0 <= starti < endi <= 50,000 and up to 100,000 days. The output is a list worklog where each entry corresponds to the new area painted that day.

Important considerations include overlapping segments, nested segments, and disjoint segments. Edge cases involve completely overlapping intervals, minimal intervals of size 1, and intervals touching at boundaries (starti = previous endi).

The challenge lies in efficiently tracking which parts of the painting are already covered without iterating over the entire range for each day, since a naive approach would be too slow given the constraints.

Approaches

Brute Force

The brute-force solution is straightforward: maintain a boolean array representing the painted status of each unit position on the number line. For each day's interval [start, end), iterate through each unit position and mark it as painted if it has not been painted before. Count the newly painted units for the worklog.

While this method is correct, its complexity is prohibitive. For the maximum input size of paint.length = 10^5 and endi up to 50,000, iterating through every unit position for every day would result in O(n * m) operations, where m is the number of positions in the number line. This is too slow for large inputs.

Optimal Approach

The key observation is that once a segment is painted, the next painting operation can skip over already painted sections. We can use a map or an array to track the next unpainted position for each starting point, effectively allowing us to jump over painted intervals. This is a form of the union-find or disjoint-set optimization applied to intervals.

Using this technique, for each interval [start, end), we check the current start position. If it has been painted, we jump to the next unpainted position and continue until we reach the end. This ensures each unit is only visited once, achieving linear time with respect to the total interval lengths rather than the naive nested iteration.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(m) Mark each unit individually, too slow for large m
Optimal O(n + total painted units) O(m) Skip painted segments using a map or array for fast jumps

Algorithm Walkthrough

  1. Initialize an array next_unpainted of size slightly larger than the maximum endpoint to track the next unpainted position for each index. Initially, each index points to itself.
  2. Define a helper function find_next(x) that recursively finds the next unpainted position starting from x using path compression.
  3. For each day’s interval [start, end), initialize current = start.
  4. While current < end, find next_pos = find_next(current).
  5. If next_pos >= end, break the loop.
  6. Increment the day’s new paint count by 1 and set next_unpainted[next_pos] = next_pos + 1 to mark it painted.
  7. Move current = next_pos + 1.
  8. Append the count of new units painted that day to worklog.
  9. Return worklog after processing all days.

Why it works: The invariant is that next_unpainted[x] always points to the first unpainted unit at or after position x. By updating this after painting, we ensure that no position is counted twice. Path compression guarantees fast lookups for subsequent intervals.

Python Solution

from typing import List

class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        max_pos = 50001
        next_unpainted = list(range(max_pos))
        worklog = []
        
        def find_next(x: int) -> int:
            if next_unpainted[x] != x:
                next_unpainted[x] = find_next(next_unpainted[x])
            return next_unpainted[x]
        
        for start, end in paint:
            new_area = 0
            current = start
            while current < end:
                current = find_next(current)
                if current >= end:
                    break
                new_area += 1
                next_unpainted[current] = current + 1
                current += 1
            worklog.append(new_area)
        
        return worklog

Explanation: We maintain next_unpainted to efficiently skip painted areas. The find_next function uses path compression to flatten the structure for faster future lookups. For each interval, we jump to the next unpainted unit and increment the count only for newly painted positions.

Go Solution

func amountPainted(paint [][]int) []int {
    maxPos := 50001
    nextUnpainted := make([]int, maxPos)
    for i := range nextUnpainted {
        nextUnpainted[i] = i
    }

    findNext := func(x int) int {
        if nextUnpainted[x] != x {
            nextUnpainted[x] = findNext(nextUnpainted[x])
        }
        return nextUnpainted[x]
    }

    worklog := make([]int, 0, len(paint))
    
    for _, p := range paint {
        start, end := p[0], p[1]
        newArea := 0
        current := start
        for current < end {
            current = findNext(current)
            if current >= end {
                break
            }
            newArea++
            nextUnpainted[current] = current + 1
            current++
        }
        worklog = append(worklog, newArea)
    }
    
    return worklog
}

Go-specific notes: Initialization uses make to allocate the array. The recursive closure findNext allows path compression. Slice append is used for building the result array efficiently.

Worked Examples

Example 1: paint = [[1,4],[4,7],[5,8]]

Day Interval Newly Painted next_unpainted updates
0 [1,4] 3 1→2, 2→3, 3→4
1 [4,7] 3 4→5, 5→6, 6→7
2 [5,8] 1 7→8

Output: [3,3,1]

Example 2: paint = [[1,5],[2,4]]

Day Interval Newly Painted next_unpainted updates
0 [1,5] 4 1→2, 2→3, 3→4, 4→5
1 [2,4] 0 none

Output: [4,0]

Complexity Analysis

Measure Complexity Explanation
Time O(n + total painted units) Each unit is visited at most once due to path compression
Space O(max endpoint) Array storing next unpainted positions

The algorithm is effectively linear with respect to the sum of all interval lengths rather than the naive product of intervals and unit positions.

Test Cases

sol = Solution()

# Provided examples
assert sol.amountPainted([[1,4],[4,7],[5,8]]) == [3,3,1]  # Overlapping intervals
assert sol.amountPainted([[1,4],[5,8],[4,7]]) == [3,3,1]  # Intervals out of order
assert sol.amountPainted([[1,5],[2,4]]) == [4,0]          # Nested interval

# Edge cases
assert sol.amountPainted([[0,1]]) == [1]                  # Minimal interval
assert sol.amountPainted([[0,50000]]) == [50000]          # Maximal interval
assert sol.amountPainted([[0,2],[1,3],[2,4]]) == [2,1,1] # Overlapping successive
assert sol.amountPainted([[1,2],[2,3],[3,4]]) == [1,1,1] # Consecutive touching
Test Why
[[1,4],[4,7],[5,8]] Overlapping segments, ensures skipping works
[[1,5],[2,4]] Nested intervals, ensures no double counting
[[0,1]] Minimal interval, edge of number line
[[0,50000]] Maximal interval, stress test large range
[[0,2],[1,3],[2,4]] Successive overlapping intervals
[[1,2],[2,3],[3,4]] Consecutive touching intervals

Edge Cases

1. Fully nested intervals: If one interval is completely contained within a previous interval, the new