Skip to content
Katabench
Try free

Release the Buffered Packets

Easy About 15 min Free, no account needed

Report how far an ordered stream can advance as packets arrive late, out of order, or more than once.

The brief

A receiver must deliver packets in order, starting with packet 1. It can hold packets that arrive early, and the sender may retry a packet that has already arrived.

Given the arrival order packets, return an array of the same length. After each arrival, report the largest packet number r for which every packet from 1 through r has arrived at least once. Report 0 while packet 1 is missing. The answer is the cumulative delivery frontier, not the number of packets released by that arrival.

For packets = [3, 1, 2, 2, 5, 4], return [0, 1, 3, 3, 3, 5]:

Arrival Delivery frontier Reason
3 0 Packet 1 is still missing.
1 1 Packet 2 is still missing.
2 3 Packets 1, 2, and 3 have all arrived.
2 3 Receiving a duplicate changes nothing.
5 3 Packet 4 is still missing.
4 5 The gap before packet 5 has closed.

Contract

Implement int[] Solve(int[] packets).

  • 0 <= packets.Length <= 300_000.
  • Each packet number is between 1 and 2_147_483_647. Numbers need not fit inside an array indexed by the number of arrivals.
  • Packet numbers may repeat. The stream may end with gaps still open.
  • An empty input returns an empty array. Do not change packets.

Performance

The hidden tests include long streams that advance after every arrival. Checking the entire delivered prefix again each time takes too long. Aim for expected O(n) total time and O(n) space, where n is the number of arrivals.

Starter code

C#
using System;

public class Solution
{
    public int[] Solve(int[] packets)
    {
        throw new 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

Hash maps and sets
Trade memory for constant-time lookups, membership tests and frequency counts.

Related katas