1313. Decompress Run-Length Encoded List

Description

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

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number[]}
 */
let decompressRLElist = function(nums) {
    let result = [];
    
    let ptr = 0;
    while(ptr < nums.length){
        let freq = nums[ptr];
        let val = nums[ptr+1];

        for(let x = 0; x < freq; x++){
            result.push(val);
        }

        ptr += 2;
    }
    
    return result;
};

Analysis

This is simple and straightforward. We keep a pointer to the current number we're looking at. This is the frequency freq. The number that follows it is the number to insert in the new array value. Then we simply insert that number value freq times with a loop. That's really all there is to it.

Let f be the largest frequency in nums and n be the number of values in nums. Note that n isn't the length of nums, that would actually be 2n. Anyway, let's consider the worst case scenario for this algorithm. That's when the frequency of every value is f. Then there will be n * f total insertions so the running time is simply O(fn).

I thought about using a hash map for this but it seemed like overkill. You are sacrificing space for speed. Plus, I imagine that compression/decompression on the same item isn't done constantly over and over so speed isn't much of a concern anyway.