UTF-8 Validation

UTF-8 Validation is a bit manipulation question wearing a text costume. You are handed a list of numbers. Each number is one byte. You must decide if they form valid UTF-8. The interviewer wants to see if you can read the top bits of each byte and follow the encoding rules without getting lost.

🎯 The Problem

You get a list of integers. You must say whether the bytes form a valid UTF-8 sequence.

What you are given:

• A list of integers. Only the lowest eight bits of each one count.
• So each entry is really one byte, a group of eight bits.

How UTF-8 packs a character:

• A character uses one to four bytes.
• The first byte is the leading byte. It tells you how many bytes the character uses.
• The bytes after it are continuation bytes. Each one starts with 10.

The leading byte rules, read from its top bits:

• Starts with 0 means a one-byte character.
• Starts with 110 means a two-byte character.
• Starts with 1110 means a three-byte character.
• Starts with 11110 means a four-byte character.

Let us try the list [197, 130, 1]. In binary 197 is 11000101. It starts with 110, so it leads a two-byte character. The next byte must be a continuation. 130 is 10000010, which starts with 10. Good. That finishes the two-byte character. Then 1 is 00000001, which starts with 0, a valid one-byte character. So the whole list is valid.

Input:  data = [197, 130, 1]
Output: true

Explanation:
197 = 11000101  -> leads a 2-byte character
130 = 10000010  -> continuation byte
1   = 00000001  -> a 1-byte character

Here is the byte stream and what each byte means.

🐢 Approach 1: Binary Strings (Brute Force)

The idea in one line: turn each byte into an eight-character string of 0 and 1, then read it like text.

The idea:

• Format each number as eight bits, like "11000101".
• Count the leading 1 bits to learn how many bytes the character uses.
• Check that the next strings start with "10".

How it works:

• A leading 0 means a one-byte character.
• Two to four leading 1 bits set how many continuation strings must follow.
• Each continuation string must begin with "10".

Why it is weak:

• Building a string for every byte is slow.
• Strings cost extra memory the question does not need.
• The interviewer asked for bytes, so they want bit math, not text tricks.

Here is the binary-string code:

def valid_utf8(data):
    remaining = 0
    for value in data:
        bits = bin(value)[2:].zfill(8)
        if remaining == 0:
            if bits.startswith("0"):
                continue
            if bits.startswith("110"):
                remaining = 1
            elif bits.startswith("1110"):
                remaining = 2
            elif bits.startswith("11110"):
                remaining = 3
            else:
                return False
        else:
            if not bits.startswith("10"):
                return False
            remaining -= 1
    return remaining == 0

⚡ Approach 2: Counter With Bit Masks (Best)

The idea in one line: keep a counter of how many continuation bytes you still expect, and read the top bits of each byte with shifts.

The idea:

• A bit mask is a number you combine with another to look at chosen bits.
• Right shifting drops the low bits and leaves only the top ones to compare.
• Keep one counter for the continuation bytes still owed.

How it works:

• If the counter is zero, this byte is a leading byte. Read its top bits and set the counter.
• Top bit 0 keeps the counter at zero. 110 sets it to one. 1110 sets it to two. 11110 sets it to three.
• Any other leading pattern is invalid.
• If the counter is not zero, this byte must start with 10. If it does, lower the counter by one. If not, it is invalid.

Why it is fast:

• One pass over the list. A few shifts per byte.
• Only a small counter is kept, so the memory stays flat.
• At the end the counter must be zero, or a character was left unfinished.

Here is the decision flow for one byte.

Steps to Solve

1. Keep a counter for how many continuation bytes you still expect. Start it at zero.
2. For each byte, keep only its lowest eight bits.
3. If the counter is zero, read the leading pattern and set the counter to the number of following bytes.
4. If a leading pattern is invalid, return false.
5. If the counter is not zero, the byte must start with 10. If not, return false. Otherwise lower the counter.
6. After all bytes, the counter must be zero. If not, return false. Otherwise return true.

#include <stdio.h>
#include <stdbool.h>

bool validUtf8(int data[], int n) {
    int remaining = 0;  // continuation bytes still expected
    for (int i = 0; i < n; i++) {
        int byte = data[i] & 0xFF;     // keep only the low 8 bits
        if (remaining == 0) {
            if ((byte >> 7) == 0) remaining = 0;            // 0xxxxxxx
            else if ((byte >> 5) == 0b110) remaining = 1;   // 110xxxxx
            else if ((byte >> 4) == 0b1110) remaining = 2;  // 1110xxxx
            else if ((byte >> 3) == 0b11110) remaining = 3; // 11110xxx
            else return false;
        } else {
            if ((byte >> 6) != 0b10) return false;  // must be 10xxxxxx
            remaining--;
        }
    }
    return remaining == 0;
}

int main(void) {
    int data[] = {197, 130, 1};
    printf("%s\n", validUtf8(data, 3) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
using namespace std;

bool validUtf8(vector<int>& data) {
    int remaining = 0;  // continuation bytes still expected
    for (int num : data) {
        int byte = num & 0xFF;     // keep only the low 8 bits
        if (remaining == 0) {
            if ((byte >> 7) == 0) remaining = 0;            // 0xxxxxxx
            else if ((byte >> 5) == 0b110) remaining = 1;   // 110xxxxx
            else if ((byte >> 4) == 0b1110) remaining = 2;  // 1110xxxx
            else if ((byte >> 3) == 0b11110) remaining = 3; // 11110xxx
            else return false;
        } else {
            if ((byte >> 6) != 0b10) return false;  // must be 10xxxxxx
            remaining--;
        }
    }
    return remaining == 0;
}

int main() {
    vector<int> data = {197, 130, 1};
    cout << (validUtf8(data) ? "true" : "false") << endl;
    return 0;
}

true

public class Utf8Validation {
    static boolean validUtf8(int[] data) {
        int remaining = 0;  // continuation bytes still expected
        for (int num : data) {
            int b = num & 0xFF;     // keep only the low 8 bits
            if (remaining == 0) {
                if ((b >> 7) == 0) remaining = 0;             // 0xxxxxxx
                else if ((b >> 5) == 0b110) remaining = 1;    // 110xxxxx
                else if ((b >> 4) == 0b1110) remaining = 2;   // 1110xxxx
                else if ((b >> 3) == 0b11110) remaining = 3;  // 11110xxx
                else return false;
            } else {
                if ((b >> 6) != 0b10) return false;  // must be 10xxxxxx
                remaining--;
            }
        }
        return remaining == 0;
    }

    public static void main(String[] args) {
        int[] data = {197, 130, 1};
        System.out.println(validUtf8(data) ? "true" : "false");
    }
}

true

def valid_utf8(data):
    remaining = 0  # continuation bytes still expected
    for num in data:
        byte = num & 0xFF        # keep only the low 8 bits
        if remaining == 0:
            if byte >> 7 == 0:
                remaining = 0            # 0xxxxxxx, one byte
            elif byte >> 5 == 0b110:
                remaining = 1            # 110xxxxx, two bytes
            elif byte >> 4 == 0b1110:
                remaining = 2            # 1110xxxx, three bytes
            elif byte >> 3 == 0b11110:
                remaining = 3            # 11110xxx, four bytes
            else:
                return False
        else:
            if byte >> 6 != 0b10:        # must be 10xxxxxx
                return False
            remaining -= 1
    return remaining == 0


data = [197, 130, 1]
print("true" if valid_utf8(data) else "false")

true

function validUtf8(data) {
  let remaining = 0; // continuation bytes still expected
  for (const num of data) {
    const byte = num & 0xff;        // keep only the low 8 bits
    if (remaining === 0) {
      if ((byte >> 7) === 0) remaining = 0;             // 0xxxxxxx
      else if ((byte >> 5) === 0b110) remaining = 1;    // 110xxxxx
      else if ((byte >> 4) === 0b1110) remaining = 2;   // 1110xxxx
      else if ((byte >> 3) === 0b11110) remaining = 3;  // 11110xxx
      else return false;
    } else {
      if ((byte >> 6) !== 0b10) return false;  // must be 10xxxxxx
      remaining--;
    }
  }
  return remaining === 0;
}

const data = [197, 130, 1];
console.log(validUtf8(data) ? "true" : "false");

true

Let us walk through the Python version line by line.

remaining = 0

This counter holds how many continuation bytes we still expect. It starts at zero because we begin ready to read a fresh leading byte.

byte = num & 0xFF

The & 0xFF keeps only the lowest eight bits. The 0xFF mask is eight ones. So anything above the low byte is cleared. This matches the rule that only the bottom byte counts.

if remaining == 0:
    if byte >> 7 == 0:
        remaining = 0
    elif byte >> 5 == 0b110:
        remaining = 1
    elif byte >> 4 == 0b1110:
        remaining = 2
    elif byte >> 3 == 0b11110:
        remaining = 3
    else:
        return False

When remaining is zero, this byte must be a leading byte. byte >> 7 shifts the byte right by seven places. So only the very top bit is left. If it is 0, the byte is a one-byte character. byte >> 5 keeps the top three bits. If they equal 110, this leads a two-byte character, so we expect one continuation. The same idea covers three and four byte characters. Any leading pattern that does not match is invalid, so we return false.

else:
    if byte >> 6 != 0b10:
        return False
    remaining -= 1

When remaining is not zero, this byte must be a continuation byte. byte >> 6 keeps the top two bits. They must equal 10. If not, the sequence breaks, so we return false. If they match, we lower the counter by one, because one expected continuation byte just arrived.

return remaining == 0

After every byte, the counter must be back to zero. If it is still positive, some character was promised more bytes than the list provided. So a leftover count means invalid.

⏱️ Time and Space Complexity

We look at each byte once and do a few bit operations on it. So the time is O(n) where n is the number of bytes. We keep only a small counter, so the space is O(1). The string approach is also O(n) in time but wastes memory and time building strings.

🧩 Key Takeaways

• ✅ Only the lowest eight bits of each number matter, so mask with 0xFF.
• ✅ A leading byte starts with 0, 110, 1110, or 11110 to mean one to four bytes.
• ✅ Every continuation byte must start with 10.
• ✅ Keep a counter of expected continuation bytes and lower it as they arrive.
• ✅ At the end the counter must be zero, or a character was left unfinished.

🚀 What’s Next?

• Reverse Integer
• Detect Squares