UTF-8 Validation — Medium Problem & Solution

Problem statement

Each entry of data holds one byte in its low 8 bits. A UTF-8 character is 1 to 4 bytes long:

• one byte starts with 0;
• a k-byte character starts with k ones then a zero, and each following byte starts with 10.

Return true if data is a valid UTF-8 encoding.

Example 1

Input: data = [197,130,1]
Output: true
Explanation: 11000101 10000010 is a two-byte character, then 00000001 is a one-byte character.

Example 2

Input: data = [235,140,4]
Output: false
Explanation: 11101011 announces three bytes, but the third starts with 00.

Example 3

Input: data = [240,162,138,147]
Output: true
Explanation: A four-byte character.

Constraints

• 1 <= data.length <= 20000
• 0 <= data[i] <= 255

How to solve UTF-8 Validation

Walk the bytes as a sequence of characters. Each leading byte declares how many continuation bytes follow, and the format of those is fixed, so validation is a scan with a small state machine.

Approach

1. Mask the current byte with 255 and classify its high bits to get the character length, rejecting any other pattern.
2. Reject if the declared length runs past the end of the array.
3. Check that each of the following len - 1 bytes matches 10xxxxxx.
4. Advance by len and repeat until the array is consumed.

Why it works

The encoding is self-delimiting: the leading byte alone determines the character's length, so a greedy left-to-right scan never has to backtrack. Any byte that is neither a valid leader nor consumed as a continuation makes the whole sequence invalid.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• 10xxxxxx is never a valid leader, so a stray continuation byte must be rejected.
• 11111xxx declares five or more bytes and is invalid — the length classification must fall through to a rejection.
• Forgetting to mask with 255 lets higher bits of the integer interfere in languages where the value is stored wider.

Reference solution

Python

from typing import List

def validUtf8(data: List[int]) -> bool:
    i = 0
    while i < len(data):
        b = data[i] & 255
        if b & 128 == 0:
            length = 1
        elif b & 224 == 192:
            length = 2
        elif b & 240 == 224:
            length = 3
        elif b & 248 == 240:
            length = 4
        else:
            return False
        if i + length > len(data):
            return False
        for j in range(1, length):
            if (data[i + j] & 255) & 192 != 128:
                return False
        i += length
    return True

JavaScript

var validUtf8 = function(data) {
    var i = 0;
    while (i < data.length) {
        var b = data[i] & 255;
        var len;
        if ((b & 128) === 0) len = 1;
        else if ((b & 224) === 192) len = 2;
        else if ((b & 240) === 224) len = 3;
        else if ((b & 248) === 240) len = 4;
        else return false;
        if (i + len > data.length) return false;
        for (var j = 1; j < len; j++) {
            if (((data[i + j] & 255) & 192) !== 128) return false;
        }
        i += len;
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Work Sessions to Finish the Tasks Medium
• Remove All Ones With Row and Column Flips Medium
• Minimum Impossible OR Medium
• Maximum OR Medium
• Minimum Array End Medium
• Number of Wonderful Substrings Medium