Published by Dimitris Kougioumtzis · Updated
Expand letter/count runs into their original text.
Expand each validated symbol/count pair, doing work proportional to the decoded output rather than the number of pairs.
When to use Run-length decoding
Restoring run-encoded data and round-trip tests.
Choosing an alternative
Encoding discovers runs; decoding expands a specified representation.
Worked example: input and state changes
Example input
A4B3C2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [], "active": [] }Step 3: Expand A; 3 characters decoded.
State at this checkpoint
{ "values": [ "A", "A", "A" ], "active": [ 2 ] }Step 5: Expand B; 5 characters decoded.
State at this checkpoint
{ "values": [ "A", "A", "A", "A", "B" ], "active": [ 4 ] }Step 8: Expand C; 8 characters decoded.
State at this checkpoint
{ "values": [ "A", "A", "A", "A", "B", "B", "B", "C" ], "active": [ 7 ] }Step 10: Decoded text = AAAABBBCC.
State at this checkpoint
{ "values": [ "A", "A", "A", "A", "B", "B", "B", "C", "C" ], "active": [], "result": "AAAABBBCC" }
Expected final state
Decoded text = AAAABBBCC.
Complexity and input bounds
Family: Strings. Time complexity: O(decoded length).
Space complexity: O(decoded length) output; O(1) expansion state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Letter/count runs such as A4B3C2; each count 1–40 and total output at most 80 letters.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Validate total decoded length before writing a buffer: a small input can request large output.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 | // Validated packed [ASCII-letter-code,count] pairs; n is even, counts 1–40, total decoded length ≤ 80. Writes decoded codes and returns count. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, output) { let count = 0; for (let i = 0; i < n; i += 2) { for (let repeat = 0; repeat < a[i + 1]; repeat++) { output[count++] = a[i]; } } return count; } |
Source
The RFC documents a byte-run instruction as an authoritative format example. It is not the original RLE publication, and the playground uses its own character/count representation.
- The VCDIFF Generic Differencing and Compression Data Format, RFC 3284
D. Korn; J. MacDonald; J. Mogul; K. Vo (2002). Format specification (RUN instruction).