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.
The iterative approach involves traversing the list in a linear manner, taking each pair of numbers as a frequency-value pair, and directly constructing the decompressed list by appending the value-frequency times.
This C solution calculates the total length of the resulting decompressed list first. It then iteratively populates this list according to the frequency and value pairs found in the nums array. Memory allocation is done dynamically to ensure the list can grow as needed.
Time Complexity: O(n), where n is half the length of nums, since we process each pair once.
Space Complexity: O(m), where m is the size of the decompressed list.
The functional approach leverages higher-order functions like map and reduce or similar constructs available in various languages to iterate through and build the decompressed list. This approach reduces the boilerplate code by focusing on function composition.
This Java solution uses the functional programming features of Java Streams. It creates a nested stream over frequency and value pairs and flattens them into a single list.
Java
Python
JavaScript
Time Complexity: O(n*m), where n is half the length of nums, and m is the average frequency.
Space Complexity: O(m), where m is the size of the decompressed list.
We can directly simulate the process described in the problem. Traverse the array nums from left to right, each time taking out two numbers freq and val, then repeat val freq times, and add these freq vals to the answer array.
The time complexity is O(n), where n is the length of the array nums. We only need to traverse the array nums once. Ignoring the space consumption of the answer array, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n), where n is half the length of |
| Functional Approach | Time Complexity: O(n*m), where n is half the length of |
| Simulation | — |
| 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. |
Leetcode 1313: Decompress Run-Length Encoded List • Algorithms Casts • 2,878 views views
Watch 9 more video solutions →Practice Decompress Run-Length Encoded List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor