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:
[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
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.
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
- Partition Labels Medium Free Cut a string into the most pieces so no letter spans two pieces.
- Reconnect the Stations Medium Free Find the first connection event that reunites every station without rebuilding reachability after each cable.
- Toggle Inspection Ranges Medium Free Count the slots left on after overlapping range toggles when the board is too large to visit slot by slot.
- Match Two Money Streams Hard Pro Allocate ordered payments across ordered invoices by intersecting their cumulative monetary spans.