Skip to main content

393 - UTF-8 Validation

Difficulty: Medium | Pattern: Bit Manipulation | Company tags: Google, Facebook, Amazon

Problem Statement​

Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (of any number of characters).

UTF-8 encoding rules:

  • 1-byte: 0xxxxxxx (starts with 0)
  • 2-byte: 110xxxxx 10xxxxxx
  • 3-byte: 1110xxxx 10xxxxxx 10xxxxxx
  • 4-byte: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Each integer in data represents one byte (only the last 8 bits matter).

Example 1:

Input: data = [197,130,1]
Output: true  (2-byte then 1-byte)

Example 2:

Input: data = [235,140,4]
Output: false  (3-byte but 3rd byte is 00000100, not 10xxxxxx)

Algorithm Flow​

Solution — O(n), O(1)​

def validUtf8(data: list[int]) -> bool:
    num_bytes = 0  # continuation bytes expected
    
    for byte in data:
        byte = byte & 0xFF  # only care about last 8 bits
        
        if num_bytes == 0:
            if byte >> 7 == 0:       # 0xxxxxxx
                num_bytes = 0
            elif byte >> 5 == 0b110: # 110xxxxx
                num_bytes = 1
            elif byte >> 4 == 0b1110: # 1110xxxx
                num_bytes = 2
            elif byte >> 3 == 0b11110: # 11110xxx
                num_bytes = 3
            else:
                return False
        else:
            if byte >> 6 != 0b10:   # must be 10xxxxxx
                return False
            num_bytes -= 1
    
    return num_bytes == 0

Dry Run​

data = [197, 130, 1]

  • 197 = 0b11000101 → 197>>5 = 6 = 0b110 → 2-byte, expect 1 continuation
  • 130 = 0b10000010 → 130>>6 = 2 = 0b10 → continuation ✓, num_bytes=0
  • 1 = 0b00000001 → 1>>7 = 0 → 1-byte ✓

Return num_bytes == 0 → True ✓

Edge Cases​

  • Trailing continuation byte after sequence → num_bytes=0 and byte starts with 10 → invalid
  • Incomplete multi-byte sequence → num_bytes != 0 at end → invalid
  • 5-byte or longer sequences → pattern doesn't match any valid prefix → return False

Complexity​

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

Key Terms​

TermDefinition
Continuation byteA byte matching 10xxxxxx, valid only as a follow-up byte in a multi-byte sequence.
Leading byteThe first byte of a UTF-8 sequence; its high bits encode how many continuation bytes follow.
Bit maskingUsing &, >> to isolate specific bits (e.g. byte & 0xFF, byte >> 5) to check a prefix pattern.
State counternum_bytes, tracking how many continuation bytes are still expected before the next leading byte.

FAQ​

Q: Why mask each value with 0xFF before checking bits? A: Input integers may have more than 8 bits set (per the problem, only the last 8 bits matter), so masking discards any extra high-order bits before pattern matching.

Q: What happens if a leading byte's prefix doesn't match any valid pattern (0, 110, 1110, 11110)? A: The function returns False immediately — no encoding starting with 10xxxxxx or 11111xxx is valid as a leading byte.

Q: Can the array end in the middle of a multi-byte sequence? A: No — if num_bytes != 0 after processing all bytes, the sequence is incomplete and the answer is False.

Q: How would this change for UTF-16 or a variable byte order? A: The bit-pattern checks would change to match UTF-16's surrogate-pair rules, but the core state-machine approach (leading byte determines expected continuation count) still applies.

Q: Is recursion or a stack needed here? A: No — a single counter (num_bytes) is sufficient because UTF-8 sequences don't nest; it is a flat state machine.

Quick Revision​

  • Problem: validate whether an integer array represents valid UTF-8 encoded bytes.
  • Each byte only uses its last 8 bits — always mask with 0xFF.
  • Leading byte prefixes: 0 → 1-byte, 110 → 2-byte, 1110 → 3-byte, 11110 → 4-byte.
  • Continuation bytes must match 10xxxxxx.
  • Track num_bytes = continuation bytes still expected; decrement on each valid continuation byte.
  • Any prefix that doesn't match a known pattern → return False immediately.
  • At the end, valid only if num_bytes == 0 (no incomplete sequence).
  • Runs in O(n) time and O(1) space — single pass, no extra storage.
  • Shares the bit-manipulation/prefix-matching pattern with 191 - Number Of 1 Bits and 342 - Power Of Four.
  • Also related in spirit to other "validate against a bit-pattern state machine" problems such as checking binary string codes.