Watch 10 video solutions for Decompress Run-Length Encoded List, a easy level problem involving Array. This walkthrough by Algorithms Casts has 2,878 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
We are given a list nums of integers representing a list compressed with run-length encoding.
Consider each adjacent pair of elements [freq, val] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.
Return the decompressed list.
Example 1:
Input: nums = [1,2,3,4] Output: [2,4,4,4] Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2]. The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4]. At the end the concatenation [2] + [4,4,4] is [2,4,4,4].
Example 2:
Input: nums = [1,1,2,3] Output: [1,3,3]
Constraints:
2 <= nums.length <= 100nums.length % 2 == 01 <= nums[i] <= 100Problem Overview: You receive an array where every two elements represent a run-length encoded pair [freq, val]. For each pair, append val to the result array freq times. The goal is to reconstruct the fully decompressed list.
Approach 1: Iterative Expansion (O(n + m) time, O(m) space)
The direct solution iterates through the input array two elements at a time. The first value represents the frequency and the second represents the number that should be repeated. For each pair, append val to a result array exactly freq times using a loop or built‑in array expansion. This approach works because the encoding format guarantees that every pair describes a contiguous block in the final output. The total runtime is O(n + m), where n is the length of the encoded array and m is the size of the decompressed output. Space complexity is O(m) since the final array must be stored.
This method relies purely on sequential iteration, making it a straightforward application of array traversal. The algorithm is easy to implement in any language and avoids unnecessary data structures.
Approach 2: Functional Expansion (O(n + m) time, O(m) space)
A functional style solution treats each encoded pair as a small transformation that produces a repeated sequence. Instead of manually pushing values in nested loops, you generate a temporary array of size freq filled with val, then flatten these arrays into a single result using operations like flatMap, list comprehensions, or stream pipelines. Each pair is mapped to its decompressed segment, and the segments are concatenated in order.
The core work remains the same: each output element must be written exactly once, so the time complexity stays O(n + m). Space complexity is also O(m) because the result list stores the entire decompressed sequence. Functional approaches are common in modern Java, Python, and JavaScript when working with declarative transformations over arrays.
Recommended for interviews: The iterative expansion approach is what most interviewers expect. It demonstrates clear understanding of run‑length encoding and basic array iteration without unnecessary abstractions. Functional solutions are clean and concise in production code, but the explicit iterative version communicates the logic more clearly during interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Expansion | O(n + m) | O(m) | Best general solution. Clear logic using simple loops and array appends. |
| Functional Expansion (map/flatMap) | O(n + m) | O(m) | When using modern language features like streams, list comprehensions, or functional pipelines. |