Decompress Run-Length Encoded List

Difficulty: Easy | Acceptance: 86.20% | Paid: No Topics: Array

We are given a list nums of integers representing a list run-length encoded.

Consider each adjacent pair of elements [freq, val] = [nums[2i], nums[2i+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.

• Examples
• Constraints
• Iterative Approach
• Functional Approach
• Two Pointer Approach

Examples

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 [2].
The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4].
At the end we concatenate [2] + [4,4,4] = [2,4,4,4].

Example 2:

Input: nums = [1,1,2,3]
Output: [1,3,3]

Constraints

2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

Iterative Approach

Intuition Iterate through the array in steps of 2, treating each adjacent pair as (frequency, value), and extend the result list with the value repeated frequency times.

Steps

• Initialize an empty result list
• Loop through nums with step size of 2
• For each pair (freq, val), extend result with val repeated freq times
• Return the result list

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        result = []
        for i in range(0, len(nums), 2):
            freq = nums[i]
            val = nums[i + 1]
            result.extend([val] * freq)
        return result

Complexity

• Time: O(n) where n is the total length of the decompressed list
• Space: O(n) for storing the result
• Notes: Simple and straightforward approach with clear logic

Functional Approach

Intuition Use language-specific functional constructs like list comprehensions, Array.fill, or vector insert to build the result more concisely.

Steps

• Initialize an empty result list
• For each pair (freq, val), use functional methods to add val repeated freq times
• Return the result list

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        return [val for i in range(0, len(nums), 2) for val in [nums[i + 1]] * nums[i]]

Complexity

• Time: O(n) where n is the total length of the decompressed list
• Space: O(n) for storing the result
• Notes: More concise code using built-in methods; Python list comprehension is particularly elegant

Two Pointer Approach

Intuition Use two pointers - one to track position in the input array and another to track position in the result array, processing pairs sequentially.

Steps

• Initialize result list and set input pointer to 0
• While input pointer is within bounds, read freq and val
• Add val to result freq times, incrementing result pointer
• Move input pointer by 2 to next pair
• Return result

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        result = []
        n = len(nums)
        i = 0
        while i < n:
            freq = nums[i]
            val = nums[i + 1]
            result.extend([val] * freq)
            i += 2
        return result

Complexity

• Time: O(n) where n is the total length of the decompressed list
• Space: O(n) for storing the result
• Notes: Similar to iterative approach but uses while loop with explicit pointer management