UTF-8 Validation

Medium Bit Manipulation Basics Original on LeetCode

Reported atPalantirTesla

UTF-8 Validation is a medium bit manipulation problem solved with the basics pattern. The best approach, optimal (bit masks with a pending counter), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (binary strings) up.

Problem

You are given an array data where each integer is one byte (only its lowest 8 bits matter). Decide whether the bytes form a valid UTF-8 encoding.

A character is 1 to 4 bytes long:

  • 1 byte: 0xxxxxxx
  • 2 bytes: 110xxxxx 10xxxxxx
  • 3 bytes: 1110xxxx 10xxxxxx 10xxxxxx
  • 4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Every byte after the first one of a character must start with 10. Return true if the whole array splits into valid characters, otherwise false.

Examples

Example 1

Input
data = [65, 194, 169]
Output
true
Why
65 = 01000001 is a 1-byte character. 194 = 11000010 starts a 2-byte character and 169 = 10101001 is its continuation byte.

Example 2

Input
data = [240, 162, 138]
Output
false
Why
240 = 11110000 announces a 4-byte character, but only two continuation bytes follow.

Example 3

Input
data = [145]
Output
false
Why
145 = 10010001 is a continuation byte with no character before it.

Constraints

  • 1 <= data.length <= 2 * 10^4
  • 0 <= data[i] <= 255

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 17 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (binary strings)O(n)O(1)
Optimal (bit masks with a pending counter)O(n)O(1)

1Brute force (binary strings)

TimeO(n)Every byte is turned into a string of fixed length 8 and checked once, but with a large constant factor.
SpaceO(1)Only one 8-character string at a time.

Write each byte as an 8-character binary string and count its leading '1' characters. Use that count to decide how many continuation bytes must follow, then check that each of those strings starts with "10".

  1. For index i, build the 8-bit string of data[i] and count leading '1's as k.
  2. k == 0: move to i + 1. k == 1 or k > 4: return false.
  3. Otherwise the next k - 1 bytes must exist and each string must start with "10"; then move to i + k.
  4. Return true when all bytes are consumed.
class Solution {
    public boolean validUtf8(int[] data) {
        int i = 0, n = data.length;
        while (i < n) {
            String bits = toBits(data[i]);
            int k = 0;
            while (k < 8 && bits.charAt(k) == '1') k++;
            if (k == 0) { i++; continue; }
            if (k == 1 || k > 4 || i + k > n) return false;
            for (int j = i + 1; j < i + k; j++) {
                if (!toBits(data[j]).startsWith("10")) return false;
            }
            i += k;
        }
        return true;
    }

    private String toBits(int b) {
        String s = Integer.toBinaryString(b & 0xFF);
        while (s.length() < 8) s = "0" + s;
        return s;
    }
}

2Optimal (bit masks with a pending counter)

TimeO(n)One pass with a few bit operations per byte.
SpaceO(1)Only the counter.

Walk the bytes once, keeping need, the number of continuation bytes still expected. When need is 0, the byte is a header: classify it with masks. When need > 0, the byte must match 10xxxxxx. At the end nothing may still be pending.

  1. If need > 0: if (b & 0xC0) != 0x80 return false; else need--.
  2. Otherwise: (b & 0x80) == 0 means need = 0; (b & 0xE0) == 0xC0 means need = 1; (b & 0xF0) == 0xE0 means need = 2; (b & 0xF8) == 0xF0 means need = 3; anything else is invalid.
  3. Return need == 0 after the loop.
class Solution {
    public boolean validUtf8(int[] data) {
        int need = 0;
        for (int x : data) {
            int b = x & 0xFF;
            if (need > 0) {
                if ((b & 0xC0) != 0x80) return false;
                need--;
            } else if ((b & 0x80) == 0) {
                need = 0;
            } else if ((b & 0xE0) == 0xC0) {
                need = 1;
            } else if ((b & 0xF0) == 0xE0) {
                need = 2;
            } else if ((b & 0xF8) == 0xF0) {
                need = 3;
            } else {
                return false;
            }
        }
        return need == 0;
    }
}

Edge cases to test

  • A lone continuation byte (starts with 10)
  • A header byte with five or more leading 1s (like 11111000)
  • The data ends in the middle of a multi-byte character
  • All ASCII bytes (every byte below 128)

Hints

Hint 1

Count the leading 1 bits of a byte: 0 means a 1-byte character, 2 to 4 mean a character of that many bytes, 1 or more than 4 is invalid as a first byte.

Hint 2

Keep a counter of how many continuation bytes are still expected; each of them must look like 10xxxxxx.

Hint 3

Masks do the checks without strings: (b & 0b11000000) == 0b10000000 tests for a continuation byte.

FAQ

What is the best time complexity for UTF-8 Validation?

Optimal (bit masks with a pending counter) runs in O(n) time and O(1) extra space. One pass with a few bit operations per byte.

Which pattern does UTF-8 Validation use?

It is a bit manipulation problem that uses the basics pattern. Other problems with the same pattern: Decimal to binary, Convert Binary Number in a Linked List to Integer, K-th Bit is Set or Not.

Is there a brute force solution for UTF-8 Validation?

Yes. Brute force (binary strings) takes O(n) time and O(1) space. Write each byte as an 8-character binary string and count its leading '1' characters.

Which edge cases should I test for UTF-8 Validation?

A lone continuation byte (starts with 10); A header byte with five or more leading 1s (like 11111000); The data ends in the middle of a multi-byte character; All ASCII bytes (every byte below 128).