UTF-8 validation

You are given an array of integers, each representing one byte (only the lowest 8 bits matter). Return whether the bytes are a valid UTF-8 encoding.

Before you code

Every character starts with a leading byte whose top bits say how many bytes it has: 0xxxxxxx (1), 110xxxxx (2), 1110xxxx (3) or 11110xxx (4). Each following byte must start with 10. The whole check is one pass with a counter of how many continuation bytes you still expect.

Hints

1. Count the leading 1 bits of a leading byte with masks: b >> 7 == 0, b >> 5 == 0b110, b >> 4 == 0b1110, b >> 3 == 0b11110.
2. A byte starting with 10 when you expect a leading byte is invalid, and so is a leading byte when you still expect continuations.
3. At the end, the counter must be 0: a character cut off at the end of the data is invalid.
4. Check the examples: 197 is 11000101 (2-byte start) and 130 is 10000010 (continuation).

Production & complexity notes

When solving UTF-8 validation on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Strings and encodings to reinforce the underlying pattern.

What it practices

Reading UTF-8's byte patterns, from Strings and encodings.