1133MediumArrayBit Manipulation

Checking a Packed Octet Stream

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A stream stream holds whole numbers, and only the lowest eight bits of each one count: those bits make up one octet of data.

Characters are packed into one to four octets by this scheme:

A one-octet character has a top bit of 0, so the octet reads 0xxxxxxx.
A character of n octets, with n between 2 and 4, opens with an octet whose top n bits are all 1 followed by a 0, and every octet after that reads 10xxxxxx.

So two octets read 110xxxxx 10xxxxxx, three read 1110xxxx 10xxxxxx 10xxxxxx, and four read 11110xxx followed by three octets of 10xxxxxx.

Return true when the whole stream is packed correctly under that scheme.

Examples

Example 1

Input: stream = [224, 160, 128]
Output: true

The first octet opens with 1110, promising three octets, and the two after it both open with 10.

Example 2

Input: stream = [197]
Output: false

The octet opens with 110 and so promises a second octet, but the stream ends there.

Example 3

Input: stream = [128]
Output: false

The octet opens with 10, which can only follow a leading octet, so it cannot start a character at all.

Constraints

1 <= stream.length <= 2 * 10^4
0 <= stream[i] <= 255

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def valid_utf8(stream: list[int]) -> bool:

Java

public boolean validUtf8(int[] stream)

The intended approach

Time O(n) over the stream, since each octet is looked at once.Space O(1).

The leading octet of a character says how many octets the character takes, so the stream can be walked character by character with no guessing. Read the leading octet, work out the width from its top bits, then check that exactly that many octets follow the promised shape and jump past them all. The widths come straight off the top bits: a top bit of `0` means one octet, top bits of `110` mean two, `1110` mean three and `11110` mean four. Any other opening, including an octet whose top bits read `10`, cannot start a character, so the stream fails there. Two failures are easy to miss. A stream that ends before a promised character is complete is invalid, so the width has to be checked against what is left. And every octet after the leading one must read `10` at the top, not merely be something other than a leading octet.

Pythonentry point: valid_utf8

def valid_utf8(stream):
    n = len(stream)
    at = 0
    while at < n:
        head = stream[at] & 255
        if head >> 7 == 0:
            width = 1
        elif head >> 5 == 6:
            width = 2
        elif head >> 4 == 14:
            width = 3
        elif head >> 3 == 30:
            width = 4
        else:
            return False
        if at + width > n:
            return False
        for i in range(at + 1, at + width):
            if (stream[i] & 255) >> 6 != 2:
                return False
        at += width
    return True

The obvious version

Write every octet out as eight characters of `0` and `1`, then walk the stream reading the widths off the openings of those strings and checking that the octets which follow open with `10`. Costs building a string per octet rather than testing bits directly.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_valid_utf8(stream):
    bits = []
    for value in stream:
        rest = value & 255
        text = ""
        for place in range(7, -1, -1):
            text += "1" if (rest >> place) & 1 else "0"
        bits.append(text)
    n = len(bits)
    at = 0
    while at < n:
        head = bits[at]
        if head[0] == "0":
            width = 1
        elif head.startswith("110"):
            width = 2
        elif head.startswith("1110"):
            width = 3
        elif head.startswith("11110"):
            width = 4
        else:
            return False
        if at + width > n:
            return False
        for i in range(at + 1, at + width):
            if not bits[i].startswith("10"):
                return False
        at += width
    return True

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in