Hybrid run-length and bit-packing codec

Design an encoder and a decoder for a list of non-negative integers. The encoder compresses the list into a list of human-readable run strings. The decoder restores the original list exactly.

There are two kinds of run:

• Run-length run: "RLE[value, count]" means value repeated count times (count >= 1).
• Bit-packed run: "BP[width, v1, v2, ...]" stores one or more literal values. width is the number of bits needed for the largest value in the run (at least 1, so a run of zeros has width 1). Every value must fit in width bits.

Implement:

• encode(nums: List[int], min_run: int = 3) -> List[str]: scan the input as maximal runs of equal values. A run at least min_run long becomes an RLE run. Shorter runs are collected, in order, into a single BP run that ends just before the next RLE run or at the end of the input.
• decode(runs: List[str]) -> List[int]: concatenate the runs. Raise ValueError on malformed input (unknown prefix, count <= 0, an empty BP run, or a value wider than its declared width).

decode(encode(nums)) == nums must hold for every valid input.

Constraints

• 0 <= len(nums) <= 10^5
• 0 <= nums[i] < 2^31
• Both operations should run in linear time.

Example 1

nums   = [4, 4, 4, 4, 6, 1, 2, 2, 8, 8, 8]
encode -> ["RLE[4, 4]", "BP[3, 6, 1, 2, 2]", "RLE[8, 3]"]

The runs of 4 and 8 are long enough for RLE. The values 6, 1, 2, 2 are packed together. The largest of them is 6, which needs 3 bits.

Example 2

runs   = ["BP[1, 0, 1]", "RLE[3, 2]"]
decode -> [0, 1, 3, 3]

Be ready for follow-ups: write the runs as real packed bits, choose the split by encoded size instead of a fixed threshold, stream values in and out with bounded memory, and support signed 32-bit integers.

Reconstructed from the reported question; details may differ from what interviewers ask.