Abstract / Summary

Check if a sequence of numbers follows valid UTF-8 byte patterns.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 46% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a validator for UTF-8 encoded data. The validUtf8 method receives a list of integers, each representing a byte, and determines whether the sequence conforms to the UTF-8 encoding rules. The algorithm walks through the byte list, interpreting each byte either as a single-byte ASCII character or as the leading byte of a multi-byte character, and then verifies the required continuation bytes.

Core Logic

The method begins by printing the binary representation of each byte, which can be useful for debugging but does not affect the validation outcome.

for d in data:
    print(bin(d))

A position index pos is initialized to zero and used to traverse the list. The outer loop extracts the current byte and advances the index.

pos = 0
while pos < len(data):
    current = data[pos]
    pos += 1

Detecting ASCII Bytes

An ASCII character in UTF-8 is represented by a single byte whose most significant bit is zero. The code checks this condition by comparing the byte against a mask that isolates the highest bit.

mask = 1 << 7          # 0b10000000
if current < mask:
    continue

If the condition holds, the loop proceeds to the next byte, treating the current one as a valid ASCII character.

Determining the Length of a Multi-Byte Sequence

When the most significant bit is set, the byte may be the start of a multi-byte character. The algorithm counts the number of leading 1 bits to infer how many bytes the character occupies. It builds a mask that expands rightward, checking whether the current byte is greater than or equal to the mask.

need = 0
mask |= mask >> 1      # becomes 0b11000000
while current >= mask:
    need += 1
    mask |= mask >> 1  # expands mask further
    if need > 3:
        return False

The loop increments need for each leading 1. If more than three leading 1s are encountered, the function returns False because UTF-8 permits at most four-byte characters (three continuation bytes).

A special guard ensures that a leading byte with no leading 1s (i.e., need == 0) is rejected, as this situation would have been caught by the ASCII branch earlier.

if need == 0:
    return False

Validating Continuation Bytes

Having determined that need continuation bytes must follow, the code iterates exactly that many times, checking each subsequent byte. It first verifies that the list has enough remaining bytes; reaching the end prematurely results in False.

for _ in range(need):
    if pos == len(data):
        return False
    current = data[pos]
    pos += 1

Each continuation byte must have the binary pattern 10xxxxxx. The condition checks that the byte lies between 0b10000000 (inclusive) and 0b11000000 (exclusive).

if not ((1 << 7) <= current < (3 << 6)):
    return False

If any continuation byte fails this test, the function aborts with False.

Successful Completion

If the loop processes all bytes without encountering an invalid pattern, the method returns True, indicating that the input conforms to UTF-8 encoding rules.

return True

Edge Cases Handled

The implementation explicitly addresses several boundary conditions:

• Empty Input - The while loop condition pos < len(data) fails immediately, leading to a True result, which aligns with the interpretation that an empty byte sequence is trivially valid.

• Single-Byte ASCII Values - Bytes less than 0b10000000 are accepted without further checks, covering the full range of standard ASCII characters (0-127).

• Overlong Leading Byte - If a leading byte contains more than three leading 1s, the early return False prevents acceptance of illegal five-byte or longer sequences.

• Missing Continuation Bytes - The check if pos == len(data) inside the continuation loop catches cases where the data ends before the required number of continuation bytes are present.

• Invalid Continuation Pattern - The range test for continuation bytes ensures that any byte not starting with 10 is rejected, covering values that start with 00, 01, or 11.

• Zero-Length Multi-Byte Indicator - The guard if need == 0 eliminates the scenario where a byte with the high bit set but no leading 1s would otherwise slip through, reinforcing the distinction between ASCII and multi-byte starts.

Performance Optimizations

The algorithm processes the input in a single pass, advancing the index pos only forward and never revisiting bytes. This linear traversal eliminates the need for auxiliary data structures, keeping memory usage minimal.

The use of bitwise operations (<<, >>, |, and comparison) provides constant-time checks for each byte, avoiding more expensive string conversions or arithmetic. The mask construction inside the leading-byte detection loop expands incrementally, reusing the previously computed mask rather than recomputing from scratch for each iteration.

Early exits (return False) are placed strategically after each validation step, allowing the function to terminate as soon as an invalid pattern is detected, which reduces unnecessary work on malformed inputs.

Overall, the combination of a single linear scan, in-place index management, and bitwise checks yields an efficient validation routine suitable for large byte streams.

Imagine there is a big pile of colorful building blocks that tell a story. Some blocks are very small and show just one simple letter, while other characters are hidden across a few blocks that must stay together in a specific order to make sense.

The code starts by looking at every block in the pile one by one. It checks the very first block to see how many extra blocks are attached to it. If the first block is a tiny one, it just moves on to the next character. If the first block is a bigger one, it counts how many extra blocks are hiding behind it to complete the message.

Once the code knows how many extra blocks are needed, it goes on a treasure hunt to find them. It carefully checks each extra block to make sure it looks exactly the way it should. If a block is missing or if it looks strange and does not fit the pattern, the code knows something went wrong. It keeps doing this until it reaches the end of the pile. Everything is meant to be part of a proper sequence, and the code ensures that every single block has a buddy to lean on when it is part of a bigger group.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python				Go		TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	Garvit244			Python
	halfrost							Go
	haoel	C++
	JoshCrozier				JS
	linouk23	C++
	lkwq007			Python
	lzl124631x	C++
	ruoru						Rust
	suxrobGM					C#
	varunu28		Java
	vli02								C
	vthwang		Java
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality