Problem Statement

UTF-8 Validation

A computer stores text as numbers, and each number is one byte. A byte is just 8 bits, and a bit is a single 0 or 1. UTF-8 is a set of rules for how those bytes group together to make one character. A character can use 1, 2, 3, or 4 bytes. The rules are about the leading bits, meaning the bits on the left end of the byte. A 1-byte character starts with a 0. A character that uses n bytes has a first byte that starts with n ones followed by a 0, and every byte after it is a continuation byte that starts with the bits 10. Given an array data where each number is one byte, we return true if the whole thing follows these rules and false if it does not. The trick we use here is bit manipulation, which just means looking at or moving the individual bits of a number instead of treating it as a whole value.

mediumBit ManipulationBit ManipulationTime: O(n) · Space: O(1)

Signals to notice

validate byte sequence encodingmulti-byte character rulesbit pattern checking

Brute force first

No simpler alternative — you must validate the encoding rules byte by byte. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Scan left to right. Check the leading bits of each byte to determine if it starts a 1, 2, 3, or 4-byte character. Then verify the next N-1 bytes start with '10'. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `data=[197,130,1] (197=11000101, 130=10000010, 1=00000001)`

init: remaining=0
byte=197: remaining==0; 197>>5=0b110 -> 2-byte start; remaining=1
byte=130: remaining=1>0; 130>>6=0b10 OK (continuation); remaining=0
byte=1: remaining==0; 1>>7=0 -> 1-byte char; remaining=0
end of data: remaining==0 -> return True

What must stay true

The first byte's leading bits determine how many continuation bytes follow. Each continuation byte must start with '10' (bits 7-6). Any violation means invalid encoding. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

remaining = 0
for byte in data:
  if remaining > 0:            # expecting continuation
    if byte >> 6 != 0b10: return False
    remaining -= 1
  else:                        # start of a new char
    set remaining from leading 1-bits (0/1/2/3) or return False
return remaining == 0

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not checking that continuation bytes actually start with '10' — a valid first byte followed by wrong continuation bytes is still invalid. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Bit Manipulation Pattern