Mediumdifference-array
Describe the Painting
Problem (restated)
Half-open segments [start, end) with color. Overlaps mix colors (sum). Return non-overlapping mixed segments [left, right, colorSum] where color is constant and nonzero.
Intuition
Events at endpoints: +color at start, -color at end. Sweep sorted positions; between consecutive events emit if sum ≠ 0.
Approaches
Sweep line / sparse difference
Tested onlyTime O(n log n)Space O(n)
Idea. Map position → delta. Sort keys; running sum is mixed color on [prev, cur).
Walkthrough. [[1,4,5],[4,7,7],[1,7,9]] → [[1,4,14],[4,7,16]].
Trade-offs. Dense array fails when coordinates are large; sparse map is required.
Solution
export function splitPainting(segments: number[][]): number[][] {
const diff = new Map<number, number>();
for (const s of segments) {
diff.set(s[0]!, (diff.get(s[0]!) ?? 0) + s[2]!);
diff.set(s[1]!, (diff.get(s[1]!) ?? 0) - s[2]!);
}
const keys = [...diff.keys()].sort((a, b) => a - b);
const res: number[][] = [];
let cur = 0;
let prev = -1;
for (const x of keys) {
if (prev !== -1 && cur !== 0) res.push([prev, x, cur]);
cur += diff.get(x)!;
prev = x;
}
return res;
}
export function splitPainting(segments: number[][]): number[][] {
const diff = new Map<number, number>();
for (const s of segments) {
diff.set(s[0]!, (diff.get(s[0]!) ?? 0) + s[2]!);
diff.set(s[1]!, (diff.get(s[1]!) ?? 0) - s[2]!);
}
const keys = [...diff.keys()].sort((a, b) => a - b);
const res: number[][] = [];
let cur = 0;
let prev = -1;
for (const x of keys) {
if (prev !== -1 && cur !== 0) res.push([prev, x, cur]);
cur += diff.get(x)!;
prev = x;
}
return res;
}
Template connection
Difference array / sweep-line events.
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?