Scale Engineer

UTF-8 Validation

Med
#0380Time: O(N) - We iterate through the N integers in the input array. For each integer, converting to a string and checking its prefix are constant time operations.Space: O(1) - The space used for the binary string representation is constant (8 bits), and does not scale with the input size.
Patterns
Bit Manipulation
Data structures
Array

Prompt

Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

  1. For a 1-byte character, the first bit is a 0, followed by its Unicode code.
  2. For an n-bytes character, the first n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

  Number of Bytes   |        UTF-8 Octet Sequence
                    |              (binary)
--------------------+-----------------------------------------
         1          |   0xxxxxxx
         2          |   110xxxxx 10xxxxxx
         3          |   1110xxxx 10xxxxxx 10xxxxxx
         4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x denotes a bit in the binary form of a byte that may be either 0 or 1.

Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

 

Example 1:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

 

Constraints:

  • 1 <= data.length <= 2 * 104
  • 0 <= data[i] <= 255

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves converting each integer in the input array into its 8-bit binary string representation. We then iterate through these binary strings, checking if they match the valid UTF-8 patterns. We'll need to maintain a counter to track the number of expected continuation bytes for multi-byte characters.

Algorithm

  • Initialize a counter continuationBytes to 0.
  • Iterate through the data array from left to right.
  • For each integer num:
    • Convert num to its 8-bit binary string representation, padding with leading zeros if necessary. Let's call it binStr.
    • If continuationBytes is 0:
      • Check the prefix of binStr.
      • If it starts with '0', it's a 1-byte character. Continue to the next integer.
      • If it starts with '110', set continuationBytes = 1.
      • If it starts with '1110', set continuationBytes = 2.
      • If it starts with '11110', set continuationBytes = 3.
      • Otherwise, the sequence is invalid. Return false.
    • If continuationBytes > 0:
      • Check if binStr starts with '10'.
      • If it does, decrement continuationBytes.
      • If it doesn't, the sequence is invalid. Return false.
  • After the loop, if continuationBytes is 0, return true. Otherwise, it means the data ended with an incomplete character, so return false.

Walkthrough

We process the data array byte by byte. For each byte, we first convert it to an 8-bit binary string. A state variable, continuationBytes, keeps track of how many continuation bytes are expected.

  • If continuationBytes is 0, we are at the start of a new character. We check the prefix of the current binary string to determine the character's length:
    • Starts with '0': 1-byte character. We continue.
    • Starts with '110': 2-byte character. We set continuationBytes to 1.
    • Starts with '1110': 3-byte character. We set continuationBytes to 2.
    • Starts with '11110': 4-byte character. We set continuationBytes to 3.
    • Any other prefix (e.g., '10', '11111') is invalid, so we return false.
  • If continuationBytes is greater than 0, the current byte must be a continuation byte.
    • We check if its binary string starts with '10'. If yes, we decrement continuationBytes. If no, it's invalid.

After checking all bytes, if continuationBytes is 0, the encoding is valid. Otherwise, it's invalid.

class Solution {    public boolean validUtf8(int[] data) {        int continuationBytes = 0;        for (int num : data) {            String binStr = toBinary(num);            if (continuationBytes == 0) {                if (binStr.startsWith("0")) {                    continuationBytes = 0;                } else if (binStr.startsWith("110")) {                    continuationBytes = 1;                } else if (binStr.startsWith("1110")) {                    continuationBytes = 2;                } else if (binStr.startsWith("11110")) {                    continuationBytes = 3;                } else {                    return false;                }            } else {                if (binStr.startsWith("10")) {                    continuationBytes--;                } else {                    return false;                }            }        }        return continuationBytes == 0;    }     private String toBinary(int num) {        String bin = Integer.toBinaryString(num);        while (bin.length() < 8) {            bin = "0" + bin;        }        return bin;    }}

Complexity

Time

O(N) - We iterate through the N integers in the input array. For each integer, converting to a string and checking its prefix are constant time operations.

Space

O(1) - The space used for the binary string representation is constant (8 bits), and does not scale with the input size.

Trade-offs

Pros

  • Conceptually simple and easy to understand, as it directly mirrors the visual patterns of UTF-8 bytes.

  • Good for developers who are more comfortable with string operations than bitwise logic.

Cons

  • Less performant than bit manipulation due to the overhead of creating and processing strings.

  • Requires a helper function to correctly format the binary string, adding slight complexity.

Solutions

class Solution {public  boolean validUtf8(int[] data) {    int n = 0;    for (int v : data) {      if (n > 0) {        if (v >> 6 != 0b10) {          return false;        }        --n;      } else if (v >> 7 == 0) {        n = 0;      } else if (v >> 5 == 0b110) {        n = 1;      } else if (v >> 4 == 0b1110) {        n = 2;      } else if (v >> 3 == 0b11110) {        n = 3;      } else {        return false;      }    }    return n == 0;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem