Skip to content
Katabench
Try free

Last Patch Wins

Hard About 45 min Free, no account needed

Recover the final contents of a strip after a long log of overlapping range assignments.

The brief

A display strip starts with length cells, all set to zero. Its update log assigns a value to a consecutive range of cells. Later updates overwrite earlier ones wherever their ranges overlap.

You only need the final display. Implement int[] Solve(int[] patches, int length) and return its values from left to right.

patches contains triples in chronological order: [left, right, value, left, right, value, ...]. Each triple writes value into every position i with left <= i < right. The right endpoint is excluded. A value of zero is an ordinary write and erases any earlier value in that range.

For Solve([0, 5, 7, 1, 4, 2, 2, 3, 0], 5), return [7, 2, 0, 2, 7]. The three updates produce:

Text
[7, 7, 7, 7, 7]
[7, 2, 2, 2, 7]
[7, 2, 0, 2, 7]

For Solve([1, 3, -4, 2, 2, 99], 4), return [0, -4, -4, 0]. The second update covers an empty range, so it changes nothing.

There are at most 200,000 triples and 0 <= length <= 100,000. Every update satisfies 0 <= left <= right <= length, and values may be any signed 32-bit integer. With no updates, return an array of zeros; with length zero, return an empty array. Do not modify patches. The log can repeatedly overwrite almost the entire strip.

Starter code

C#
public class Solution
{
    public int[] Solve(int[] patches, int length)
    {
        // Each triple is [inclusive left, exclusive right, assigned value].
        throw new System.NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Union-find
Merge sets and answer connectivity questions in near-constant time.
Intervals and sweep lines
Sort or sweep interval boundaries, including difference arrays for range updates.

Related katas