{x}
blog image

Decompress Run-Length Encoded List

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 <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100

Solution Explanation: Decompress Run-Length Encoded List

This problem involves decompressing a list encoded using run-length encoding. The input nums is an array of integers where pairs represent (frequency, value). The goal is to create a new list where each value is repeated its corresponding frequency.

Approach

The most straightforward approach is to iterate through the input list in steps of 2, extracting the frequency and value from each pair. Then, we repeat the value the specified number of times and append it to the result list.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the length of the input list nums. This is because we iterate through the input list once, and the number of appends to the output list is proportional to the sum of frequencies, which is at most N.

  • Space Complexity: O(M), where M is the length of the decompressed list. In the worst case, this could be significantly larger than N. The space used also includes the space for the output list. If we ignore the space used by the output list, the space complexity would be considered O(1).

Code Implementation in Multiple Languages

The following code examples demonstrate the solution in several popular programming languages:

Python:

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)  # Efficiently extends the list
        return result

Java:

class Solution {
    public int[] decompressRLElist(int[] nums) {
        List<Integer> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length; i += 2) {
            int freq = nums[i];
            int val = nums[i + 1];
            for (int j = 0; j < freq; j++) {
                resultList.add(val);
            }
        }
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}

C++:

class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums) {
        vector<int> result;
        for (int i = 0; i < nums.size(); i += 2) {
            int freq = nums[i];
            int val = nums[i + 1];
            for (int j = 0; j < freq; ++j) {
                result.push_back(val);
            }
        }
        return result;
    }
};

JavaScript:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var decompressRLElist = function(nums) {
    let result = [];
    for (let i = 0; i < nums.length; i += 2) {
        let freq = nums[i];
        let val = nums[i+1];
        result.push(...Array(freq).fill(val)); // Efficiently adds multiple elements
    }
    return result;
};

Go:

func decompressRLElist(nums []int) []int {
    result := []int{}
    for i := 0; i < len(nums); i += 2 {
        freq := nums[i]
        val := nums[i+1]
        for j := 0; j < freq; j++ {
            result = append(result, val)
        }
    }
    return result
}

These examples all follow the same basic approach, showcasing how the algorithm can be implemented effectively in various languages. The Python and JavaScript solutions utilize more efficient list/array manipulation methods to improve performance slightly. The core algorithm remains consistent across all implementations.