String Compression In Place: Run-Length Encoding With Two Cursors

"Compress aaabbbbc to a3b4c" sounds like a warm-up, and written with a second string it is one. The interview version adds a constraint that changes the problem: do it in place, in the same character array, with constant extra space, and return the new length. That turns a string exercise into a two-cursor argument, and the part worth practising is not the loop but the proof that the loop never overwrites something it still needs to read.

The problem it solves

Run-length encoding replaces a run of identical characters with the character followed by the run's length. The usual rules:

• A run of one is written bare: abc stays abc, because a1b1c1 would be longer.
• A count above nine takes several slots: twelve x characters become x, 1, 2.
• The result is written into the input array, and the function returns how many slots it used. Whatever sits after that is ignored.

Run-length coding is one of the oldest compression schemes. It shrinks data with long runs, such as flat regions of an image or sparse bitmaps, and applied naively it makes varied data bigger, which is why runs of one are written bare.

The intuition

Two cursors walk the same array. Read measures runs: note the character under it, advance until the character changes, and count the steps. Write lays down the output behind it: the character, then the count's digits if the run was longer than one.

Why is it safe to write into the array being read? Because a run of L characters produces at most L output characters. A run of one writes one, a run of two writes two, a run of ten writes three. Output never outgrows input, run by run, so write can never pass read, and each run is measured completely before any of its slots are overwritten. Measure first, then write: that ordering is the whole correctness argument.

The function returns a length rather than a string because the array keeps its old tail. The slots after write still hold characters from the input; they are garbage, and the caller is told where the real data ends.

Watch it run

The animation compresses aaabbbbc, eight slots. A run of identical characters becomes the character and its count, written into the same buffer. First a runs for three characters: measure the whole run before writing anything. Then write a and the count 3; two slots consumed a run of three. Next b runs for four, so b and 4 go down, again two slots for a run of four. Then c runs for one character, and a run of one is written bare, since a count of 1 would only make the output longer. The last frame counts up: five slots used out of eight, and the write cursor never once overtook the read cursor. The tail is left as it was; the length is the answer.

The code

The in-place version. Printing the whole buffer afterwards shows the tail the algorithm leaves behind, which is why the length is the return value:

def compress(chars):
    write = read = 0
    while read < len(chars):
        c, run = chars[read], 0
        while read < len(chars) and chars[read] == c:
            read += 1                      # measure the whole run first
            run += 1
        chars[write] = c
        write += 1
        if run > 1:                        # a run of one stays bare
            for digit in str(run):         # 12 is written as '1', '2'
                chars[write] = digit
                write += 1
    return write

buf = list("aaabbbbc")
n = compress(buf)
print(n, "".join(buf[:n]), "".join(buf))   # 5 a3b4c a3b4cbbc

for s in ("abc", "x" * 12, "aabbccc", "z"):
    b = list(s)
    print(s, "->", "".join(b[:compress(b)]))
# abc -> abc
# xxxxxxxxxxxx -> x12
# aabbccc -> a2b2c3
# z -> z

A decoder has to read multi-digit counts, and it exposes the trap: if the input may contain digits, two different strings can compress to the same output, and the encoding cannot be reversed:

def decode(s):
    out, i = [], 0
    while i < len(s):
        c, i = s[i], i + 1
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1                         # a count may span several digits
        out.append(c * (int(s[i:j]) if j > i else 1))
        i = j
    return "".join(out)

print(decode("a3b4c"), decode("x12"))      # aaabbbbc xxxxxxxxxxxx

def compressed(s):
    b = list(s)
    return "".join(b[:compress(b)])

print(compressed("aa"), compressed("a2"))  # a2 a2

The safety argument, checked instead of trusted. This instrumented copy records the gap between the cursors at every single write, and 3,000 seeded random strings with long runs are compared against itertools.groupby as the reference, then decoded back:

import random
from itertools import groupby

def compress_checked(chars):
    """Same algorithm; returns the length and the smallest read - write gap seen."""
    write = read = 0
    gap = len(chars)
    while read < len(chars):
        c, run = chars[read], 0
        while read < len(chars) and chars[read] == c:
            read += 1
            run += 1
        for out in [c] + (list(str(run)) if run > 1 else []):
            gap = min(gap, read - write)   # write must still be behind read
            chars[write] = out
            write += 1
    return write, gap

def by_groupby(s):
    parts = []
    for ch, grp in groupby(s):
        run = len(list(grp))
        parts.append(ch + (str(run) if run > 1 else ""))
    return "".join(parts)

random.seed(26)
ok, smallest_gap = True, None
for _ in range(3_000):
    s = "".join(random.choice("abc") * random.choice([1, 1, 2, 3, 9, 10, 11, 25])
                for _ in range(random.randint(0, 12)))
    buf = list(s)
    n, gap = compress_checked(buf)
    ok &= "".join(buf[:n]) == by_groupby(s) == compressed(s)
    ok &= decode(by_groupby(s)) == s       # letters only, so it round-trips
    if s:
        smallest_gap = gap if smallest_gap is None else min(smallest_gap, gap)
print(ok, smallest_gap)                    # True 1

A smallest gap of 1 means that at the tightest moment, write was one slot behind read, never level with it and never past it.

The complexity

• Time: O(n). Read advances once per character; write advances at most once per character.
• Extra space: O(1). Only the two cursors and the current run length. str(run) builds at most a handful of digits, since a count has O(log n) of them.
• Output size: from 1 + digits(n) for one run covering the whole input, up to n when no run is longer than two.

Where it goes wrong

• Writing before measuring. The count only exists once the run has ended. Measure first, then write the character and its digits, and the at-most-L argument covers every write.
• Writing the count as one slot. A count of 12 is two characters, '1' and '2', not the number 12 in one slot.
• Writing 1 for single characters. The usual rule keeps them bare; check which rule the interviewer wants.
• Forgetting the last run. Loops that write when the character changes need a final flush after the loop. Measuring runs inside the loop, as above, avoids that bug entirely.
• Assuming it is reversible. With digits in the input, aa and a2 both encode to a2. Real formats escape digits or store counts in fixed-width fields.
• Returning the buffer. The tail still holds old characters; return the length, or slice.

When it shows up in interviews

The in-place array version is a common medium, and a looser variant asks you to return the compressed string only if it is shorter than the original. It belongs to the same family as move zeroes and removing duplicates from a sorted array: a slow write cursor trails a fast read cursor through one buffer, which is the "move items in place" signal on the patterns cheat sheet. Follow-ups include decoding, handling digits in the input, and why the in-place version is safe at all. Encode and decode strings is the natural next question when the interviewer turns to reversible formats.

How to say it in an interview

"I keep two indices into the same array. Read finds the end of the current run and counts it; only then does write lay down the character and, if the run is longer than one, the count's digits. A run of length L writes at most L characters, so write never passes read and I never overwrite anything I still need. It is one pass, O(n) time and O(1) extra space, and I return the new length because the tail of the array is stale. If the input can contain digits, I would point out that this format is not reversible."