326. UTF-8 Validation
You are given an integer array data, where each element represents one byte of a stream (only the 8 lowest bits of each integer matter, so every value is between 0 and 255). Decide whether the whole array is a valid UTF-8 byte sequence — that is, whether it can be split, left to right, into complete UTF-8 characters.
A UTF-8 character occupies 1 to 4 bytes, and its first byte announces the length:
| first byte | continuation bytes | total length |
|:--|:-:|:-:|
| 0xxxxxxx | none | 1 |
| 110xxxxx | 1 × 10xxxxxx | 2 |
| 1110xxxx | 2 × 10xxxxxx | 3 |
| 11110xxx | 3 × 10xxxxxx | 4 |
Every byte after a multi-byte leader must be a continuation byte — its top two bits must be 10. A byte whose top bits are 10 can never start a character, and a first byte with five or more leading ones is illegal.
Return true if data decomposes entirely into such characters (no leftover, truncated character at the end), and false otherwise. Only this structural bit-pattern rule is checked — ignore deeper Unicode rules like overlong encodings or surrogate ranges.
Example 1:
Input: data = [197, 130, 1]
Output: true
Explanation: 197 = 11000101 opens a 2-byte character, 130 = 10000010 is its continuation, and 1 = 00000001 is a standalone 1-byte character.
Example 2:
Input: data = [235, 140, 4]
Output: false
Explanation: 235 = 11101011 promises a 3-byte character, and 140 = 10001100 is a valid continuation — but 4 = 00000100 does not start with 10, so the character is broken.
Constraints:
- 1 ≤ data.length ≤ 2 * 10⁴
- 0 ≤ data[i] ≤ 255
- Only the structural bit rules in the statement are validated (no overlong/surrogate checks).
Hints:
Classify each byte by its top bits: 0 leading one → standalone; exactly one leading one (10...) → continuation; 2, 3, or 4 leading ones → the leader of a character that long; 5+ leading ones → invalid. Shifting right (b >> 5 == 0b110, etc.) compares just the prefix.
Keep one counter: how many continuation bytes the current character still owes. A leader sets the debt; every 10xxxxxx byte pays one unit; anything unexpected — a continuation with no debt, a leader while debt remains, or leftover debt at the end — makes the array invalid.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: data = [197, 130, 1]
Expected output: true