UTF-8 Validation

Medium
737.

UTF-8 Validation

UTF-8 Validation is a medium coding problem on arrays and bit manipulation, asked in Amazon, Google, Meta and Palantir interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} data
 * @return {boolean}
 */
var validUtf8 = function(data) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

UTF-8 Validation — Solution in Python, Java & C++

UTF-8 Validation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

UTF-8 Validation is a medium coding problem on arrays and bit manipulation, asked in Amazon, Google, Meta and Palantir interviews.

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

Hints for UTF-8 Validation

  1. Hint 1

    Only the low 8 bits matter — mask each entry with 255 before inspecting it.

  2. Hint 2

    The leading byte's high bits give the character length: 0xxxxxxx is 1, 110xxxxx is 2, 1110xxxx is 3, 11110xxx is 4.

  3. Hint 3

    Every continuation byte must match 10xxxxxx, which is (b & 0xC0) == 0x80.

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

Java

public static boolean validUtf8(int[] data) {
    int i = 0;
    while (i < data.length) {
        int b = data[i] & 255;
        int 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 (int j = 1; j < len; j++) {
            if (((data[i + j] & 255) & 192) != 128) return false;
        }
        i += len;
    }
    return true;
}

C++

bool validUtf8(vector<int>& data) {
    int i = 0;
    int n = (int) data.size();
    while (i < n) {
        int b = data[i] & 255;
        int 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 > n) return false;
        for (int j = 1; j < len; j++) {
            if (((data[i + j] & 255) & 192) != 128) return false;
        }
        i += len;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation