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.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation
- Asked at: Amazon, Google, Meta, Palantir
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 withkones then a zero, and each following byte starts with10.
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 <= 200000 <= data[i] <= 255
Hints for UTF-8 Validation
Hint 1
Only the low 8 bits matter — mask each entry with 255 before inspecting it.
Hint 2
The leading byte's high bits give the character length:
0xxxxxxxis 1,110xxxxxis 2,1110xxxxis 3,11110xxxis 4.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
- Mask the current byte with 255 and classify its high bits to get the character length, rejecting any other pattern.
- Reject if the declared length runs past the end of the array.
- Check that each of the following
len - 1bytes matches10xxxxxx. - Advance by
lenand 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
10xxxxxxis never a valid leader, so a stray continuation byte must be rejected.11111xxxdeclares 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 TrueJava
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