🏭 Warehouse Inventory Expansion

A large warehouse receives shipment manifests from suppliers around the world. To reduce the size of transmitted data, suppliers do not list every individual item in a shipment. Instead, they use a compact encoding where each pair of numbers represents:

• Quantity – the number of identical items in the shipment.
• Item ID – the unique identifier of the product.

For example, the encoded manifest:

[3, 101, 2, 205, 1, 450] represents:

• 3 units of item 101
• 2 units of item 205
• 1 unit of item 450

Before the warehouse's picking robots can begin processing an order, the compact shipment manifest must be expanded into a list containing one entry for every individual item.

Given an array manifest of even length, where every pair of elements is of the form:

[quantity, itemId]

return the fully expanded inventory list.

Example

Input

manifest = [3, 101, 2, 205, 1, 450]

Output

[101, 101, 101, 205, 205, 450]

---

🔧 Solution

This problem introduces a common data compression technique known as Run-Length Encoding (RLE), which appears frequently in data storage, telemetry systems, log compression, and networking.

The key is to recognize that every two consecutive elements in the input describe one batch of identical items.

---

The most straightforward way to think about the problem is:

• Read one (quantity, itemId) pair.
• Insert itemId into the answer exactly quantity times.
• Move to the next pair.
• Continue until the manifest is exhausted.

Since every item must appear in the final output, there is no way to avoid writing each one.

</> Python Implementation

    def decompressRLElist(self, manifest: List[int]) -> List[int]:
        result = []

        for i in range(0, len(manifest), 2):
            quantity = manifest[i]
            item = manifest[i + 1]

            result.extend([item] * quantity)

        return result

Ω Complexity Analyis

Let $N$ be the total number of items in the expanded inventory.

Time Complexity $O(N)$

Although we iterate through the compressed array, the dominant work is writing each expanded item exactly once.