Run-Length Encoding

Run-Length Encoding


2 min read

Run-length encoding (RLE) an algorithm for lossless compression.

Its idea is very simple. Let's see an example.

Say we have a string aaaabbbccd, with RLE, we use a form of [frequency][character] to express this string. So we have 4's a, 3's b, 2'c, and 1'd, then we can express it as 4a3b2c1d. And That's it. You can see that, if the original data have a lot of repetive pattern, then it is very suitable to use RLE for compression.

Leetcode problem Decompress Run-Length Encoded List can be use to practise how to decode a RLE data.

function decompressRLElist(nums: number[]): number[] {
    let result: number[] = [];
    for (let i = 0; i < nums.length - 1; i += 2) {
        for (let j = 0; j < nums[i]; j++) {
            result.push(nums[i + 1]);
    return result;

As you can see, its very simple, just follow the algorithm, put repetive characters into result array.

Leetcode problem String Compression can be used to practise the encoding of RLE. Note that this problem requires that if the frequency is 1, then just fill in the character.

function compress(chars: string[]): number {
    let i = 0;
    let j = 0;
    while (i < chars.length) {
        let k = i;
        while (++k, k < chars.length, chars[k] === chars[i]);
        let length = (k - i).toString();
        chars[j++] = chars[i]; // fill in the character
        if (length !== "1") {
            [...length].forEach(char => {
                chars[j++] = char; // fill in the frequency
        i = k;
    return j;