Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

The input is an array of characters. It must be compressed in place by replacing each maximal run of equal characters with the character followed by the run length—except that a run of length one keeps only the character. A count with multiple digits is written one digit at a time. For example, a, a, b, c, c, c becomes the meaningful prefix a, 2, b, c, 3, so the method returns 5.

Only the returned prefix matters; values beyond it may be ignored. The challenge is therefore not run-length encoding itself, but producing that encoding inside the original array with constant auxiliary space.

Deriving the optimal solution

The runs must appear in the same order as the input, which makes a single left-to-right scan natural. Two indices give the scan separate jobs:

  • A read index finds the end of the next run.
  • A write index marks where the next compressed character or count digit belongs.

Suppose the read index reaches the start of a run of 12 copies of x. Scan forward until the character changes, write x, then write 1 and 2 into the next two positions. The read index jumps to the next run, and the same process repeats.

It is safe to write into the input while it is still being read. A run of length one produces one character. A run of length two produces two characters. Every longer run produces fewer characters than it consumes. The compressed prefix can therefore reach the read boundary, but it can never pass it and overwrite unread input.

The code below also writes a count without calling str(run_length). It first determines how many decimal positions are needed, then fills those positions from right to left using remainders. This keeps the auxiliary-space bound strictly constant rather than allocating a temporary digit string.

Why the two-pointer scan is correct

Before each run is processed, the prefix ending at the write index is exactly the correct compression of every character before the read index. The inner scan finds the first position after the current maximal run, so its difference from the run’s start is the exact run length.

The algorithm then appends precisely the required representation: the run’s character, followed by its decimal count only when that count is greater than one. This extends the correct compressed prefix by one complete run and restores the invariant for the next iteration. Once the read index reaches the end, every run has been represented exactly once, so the write index is the required compressed length.

For n input characters, each character is inspected a constant number of times and each output position is written once. The time complexity is O(n). The indices and numeric counters use O(1) auxiliary space; the transformation happens inside chars.

Python solution

from __future__ import annotations


class InPlaceStringCompressor:
    """Run-length encode a character array without an auxiliary buffer."""

    @classmethod
    def compress(cls, characters: list[str]) -> int:
        """Compress characters in place and return the meaningful prefix length.

        Each item is expected to be one character, as required by the problem.
        An empty list is accepted defensively and has compressed length zero.
        """
        read_index = 0
        write_index = 0

        while read_index < len(characters):
            run_start = read_index
            run_character = characters[run_start]

            # Find the first character not belonging to this maximal run.
            while (
                read_index < len(characters)
                and characters[read_index] == run_character
            ):
                read_index += 1

            run_length = read_index - run_start
            characters[write_index] = run_character
            write_index += 1

            if run_length > 1:
                write_index = cls._write_positive_integer(
                    characters,
                    write_index,
                    run_length,
                )

        return write_index

    @staticmethod
    def _write_positive_integer(
        characters: list[str],
        write_index: int,
        value: int,
    ) -> int:
        """Write value's decimal digits in place and return the next free index."""
        digit_count = 0
        remaining_value = value
        while remaining_value > 0:
            digit_count += 1
            remaining_value //= 10

        next_write_index = write_index + digit_count
        digit_index = next_write_index - 1
        remaining_value = value

        # Remainders arrive from least to most significant, so fill backward.
        while remaining_value > 0:
            characters[digit_index] = chr(ord("0") + remaining_value % 10)
            remaining_value //= 10
            digit_index -= 1

        return next_write_index


class Solution:
    """LeetCode-compatible entry point."""

    def compress(self, chars: list[str]) -> int:
        return InPlaceStringCompressor.compress(chars)

Interview follow-ups

How would the solution change if modifying the input were forbidden?

The run-detection logic would stay the same, but the encoded characters would be appended to a separate output builder. In Python, a list is the appropriate builder because repeatedly concatenating immutable strings can copy the growing result and degrade to quadratic time. Joining the list once at the end gives O(n) time.

The extra storage is O(k), where k is the compressed output length. That is unavoidable when the original input cannot hold the result and the caller expects the entire encoding to be returned.

How can the compression be produced from a character stream?

Keep only the current run character and its count. Each incoming matching character increments the count. When a different character arrives, emit the completed run and start a new one; when the stream ends, flush the final run.

This uses O(1) working state and O(n) total processing time. The tradeoff is that emitted output generally cannot be changed, so the encoder must wait for a run to end before writing that run’s count. Backpressure and partial writes also become concerns in a production streaming interface.

Can the compressed representation always be decompressed unambiguously?

Not if literal input characters may themselves be digits. For example, an encoded sequence resembling a12 could mean twelve copies of a, or it could contain literal digit characters from singleton runs. The compression task asks only for encoding and does not supply the metadata needed to distinguish every such case.

For reversible compression, the format must be strengthened. Possible approaches include escaping literal digits, separating fields with delimiters, prefixing each field with its length, or restricting the input alphabet so characters and count digits cannot overlap. Once the format is unambiguous, a decoder can scan one token at a time and expand each run in time proportional to the decompressed output size.

What if the count must be written in another base?

The two-pointer structure does not change. The numeric helper would compute the number of base-b digits, repeatedly take value % b, and fill the reserved positions backward. Bases above ten also need a mapping from digit values to output symbols.

The scan remains O(n). Writing a run count takes O(log_b r) time for run length r, which is also the number of symbols that must be produced. A larger base shortens counts but may require a broader output alphabet or more complex serialization.

How would Unicode text affect the design?

The interviewer must first define “character.” Python strings iterate over Unicode code points, while users often perceive a grapheme cluster—such as a letter plus combining marks or a multi-code-point emoji—as one character. Compressing code points can therefore split a visible symbol.

For grapheme-aware behavior, segment the text with a Unicode grapheme-boundary implementation and run the same algorithm over those tokens. The run logic is unchanged, but tokenization adds library dependence, processing cost, and either stored boundaries or a streaming segmenter. Unicode normalization may also be needed if canonically equivalent spellings should compare as equal.

What data structure would support edits to an already compressed sequence?

A flat encoded array is efficient for one pass but poor for insertions and deletions near the front because later data may need to shift. Instead, store runs as nodes in a balanced sequence tree, with each node holding a character and count. An edit changes or splits a nearby run, after which adjacent equal-character runs are merged.

With subtree lengths, the tree can locate the run containing a logical character position in O(log r) time for r runs. Local updates also take O(log r), though the structure uses O(r) space and has much larger constants than the original linear scan. It is justified when many online edits matter more than minimal memory.