UTF-8 Validation - Practice Coding Problems

UTF-8 Validation - Problem

Given an integer array data representing the data, return whether it is a valid UTF-8 encoding.

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

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

UTF-8 Encoding Rules:

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

Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data.

Input & Output

Example 1 — Valid UTF-8 Sequence

$ Input: data = [197,130,1]

› Output: true

💡 Note: 197 (11000101) is a 2-byte start, 130 (10000010) is valid continuation, 1 (00000001) is valid 1-byte character

Example 2 — Invalid Continuation

$ Input: data = [235,140,4]

› Output: false

💡 Note: 235 (11101011) starts a 3-byte character but only has one continuation byte 140, missing second continuation

Example 3 — Single Bytes Only

$ Input: data = [1,2,3,4]

› Output: true

💡 Note: All bytes have pattern 0xxxxxxx, which are valid 1-byte UTF-8 characters

Constraints

1 ≤ data.length ≤ 2 × 10⁴
0 ≤ data[i] ≤ 255

Visualization

Tap to expand

Understanding the Visualization

Input Data

Array of integers representing bytes

UTF-8 Patterns

Identify start bytes and continuation bytes

Validation

Check if sequence forms valid UTF-8 characters

Key Takeaway

🎯 Key Insight: UTF-8 validation requires state tracking to ensure continuation bytes follow start bytes in correct sequences

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Facebook 12

The key insight is to use a state machine that tracks how many continuation bytes are expected after each UTF-8 start byte. Best approach uses bit manipulation to identify byte types and maintain a counter for proper sequence validation. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Bit Checking	O(n)	O(1)	Check each byte's bit pattern individually without state tracking
State Machine with Bit Manipulation	O(n)	O(1)	Track remaining continuation bytes while validating bit patterns

Brute Force Bit Checking — Algorithm Steps

Step 1: Check each byte against all possible UTF-8 patterns
Step 2: Try to match without tracking continuation bytes

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Byte

Examine bit patterns individually

Pattern Match

Try to match against UTF-8 patterns

False Logic

Missing multi-byte sequence validation

Code -

solution.c — C

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

bool solution(int* data, int size) {
    // Brute force: check each byte individually (incorrect approach)
    for (int i = 0; i < size; i++) {
        int byte = data[i] & 0xFF;
        
        // Check if it's a valid single pattern (flawed logic)
        if ((byte >> 7) == 0) {  // 1-byte: 0xxxxxxx
            continue;
        } else if ((byte >> 5) == 0b110) {  // 2-byte start: 110xxxxx
            continue;
        } else if ((byte >> 4) == 0b1110) {  // 3-byte start: 1110xxxx
            continue;
        } else if ((byte >> 3) == 0b11110) {  // 4-byte start: 11110xxx
            continue;
        } else if ((byte >> 6) == 0b10) {  // continuation: 10xxxxxx
            continue;
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int data[100];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && size < 100) {
            data[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    bool result = solution(data, size);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array but incorrect logic

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Bit Checking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler