Decompress Run-Length Encoded List

Easy

#1222Time: O(S), where S is the total number of elements in the decompressed list. We iterate through all pairs in `nums` and for each pair `[freq, val]`, we perform `freq` additions. The sum of all `freq` values is `S`. Converting the list to an array also takes O(S) time.Space: O(S), where S is the size of the decompressed list. This space is required to store the `resultList`.

Data structures

Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through the input array once. For each frequency-value pair, we add the value to a dynamic list (like Java's ArrayList) the specified number of times. This is straightforward but may incur overhead from the list's dynamic resizing.

Algorithm

1. Create an empty ArrayList of integers, let's call it resultList.
1. Iterate through the input array nums with a step of 2, from index i = 0 to nums.length - 2.
1. In each iteration, get the frequency freq = nums[i] and the value val = nums[i+1].
1. Start a nested loop that runs freq times.
1. Inside the nested loop, add val to resultList.
1. After the outer loop finishes, create a new integer array resultArray with the same size as resultList.
1. Copy all elements from resultList to resultArray.
1. Return resultArray.

Walkthrough

We initialize an ArrayList to store the decompressed numbers. We then loop through the nums array, taking elements in pairs. The loop iterates from i = 0 to nums.length with a step of 2. For each pair [freq, val], where freq = nums[i] and val = nums[i+1], we run a nested loop freq times. Inside the nested loop, we add val to our ArrayList. After the loops complete, the ArrayList contains the full decompressed list. We then convert this list into an integer array to match the required return type.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[] decompressRLElist(int[] nums) {6        List<Integer> resultList = new ArrayList<>();7        for (int i = 0; i < nums.length; i += 2) {8            int freq = nums[i];9            int val = nums[i+1];10            for (int j = 0; j < freq; j++) {11                resultList.add(val);12            }13        }14 15        // Convert List<Integer> to int[]16        int[] resultArray = new int[resultList.size()];17        for (int i = 0; i < resultList.size(); i++) {18            resultArray[i] = resultList.get(i);19        }20        return resultArray;21    }22}

Complexity

Time

O(S), where S is the total number of elements in the decompressed list. We iterate through all pairs in `nums` and for each pair `[freq, val]`, we perform `freq` additions. The sum of all `freq` values is `S`. Converting the list to an array also takes O(S) time.

Space

O(S), where S is the size of the decompressed list. This space is required to store the `resultList`.

Trade-offs

Pros

Simple and intuitive to implement.
Requires only a single pass over the input data to generate the list.

Cons

Using a dynamic list like ArrayList can lead to performance overhead due to internal array resizing when the capacity is exceeded.
Requires an extra step to convert the final List<Integer> to an int[], which involves another O(S) iteration and memory allocation.

This approach improves upon the dynamic list method by first calculating the exact size of the final decompressed list. It then allocates an array of that specific size and fills it in a second pass. This avoids the overhead of dynamic resizing and is generally more performant.

Algorithm

1. Initialize a variable totalSize = 0.
1. First Pass: Iterate through nums with a step of 2 (at indices 0, 2, 4, ...). In each step, add the frequency nums[i] to totalSize.
1. Create a new integer array result of size totalSize.
1. Initialize an index variable currentIndex = 0 to keep track of the current position in the result array.
1. Second Pass: Iterate through nums again with a step of 2.
1. For each pair [freq, val], where freq = nums[i] and val = nums[i+1], fill the result array with val for freq times starting from currentIndex.
1. Update currentIndex by adding freq to it.
1. After the loops complete, return the result array.

Walkthrough

This method consists of two main passes over the input nums array.

First Pass: The goal is to determine the total length of the decompressed list. We initialize a variable size to 0. We iterate through nums at every even index (i = 0, 2, 4, ...) and add the frequency nums[i] to size.

Array Allocation: After the first pass, size holds the exact number of elements in the final list. We create a new integer array, result, of this length: new int[size].

Second Pass: We fill the newly created result array. We initialize a pointer or index, currentIndex, to 0. We iterate through nums again in pairs ([freq, val]). For each pair, we add val to the result array freq times. This can be done efficiently using java.util.Arrays.fill(). After filling the segment for the current pair, we advance currentIndex by freq.

Finally, we return the populated result array.

1import java.util.Arrays;2 3class Solution {4    public int[] decompressRLElist(int[] nums) {5        // First pass: calculate the size of the decompressed list6        int size = 0;7        for (int i = 0; i < nums.length; i += 2) {8            size += nums[i];9        }10 11        // Create the result array with the calculated size12        int[] result = new int[size];13        int currentIndex = 0;14 15        // Second pass: fill the result array16        for (int i = 0; i < nums.length; i += 2) {17            int freq = nums[i];18            int val = nums[i+1];19            // Use Arrays.fill for potentially faster block assignment20            Arrays.fill(result, currentIndex, currentIndex + freq, val);21            currentIndex += freq;22        }23        return result;24    }25}

Complexity

Time

O(N + S), where N is the length of the input `nums` array and S is the total number of elements in the decompressed list. The first pass takes O(N) time. The second pass takes O(S) time to fill the array. Thus, the total time complexity is O(N + S).

Space

O(S), for storing the final `result` array. The auxiliary space is O(1) as we only use a few extra variables.

Trade-offs

Pros

More memory-efficient and often faster in practice than the dynamic list approach because it avoids resizing overhead.
Direct array manipulation, especially with Arrays.fill, can be faster than repeated ArrayList.add() method calls.

Cons

Requires two passes over the input array, which might be considered less elegant than a single-pass solution.
The code is slightly more complex due to the need to manage the index for the result array manually.

Solutions

Solution

1class Solution {2public3  int[] decompressRLElist(int[] nums) {4    int n = 0;5    for (int i = 0; i < nums.length; i += 2) {6      n += nums[i];7    }8    int[] res = new int[n];9    for (int i = 1, k = 0; i < nums.length; i += 2) {10      for (int j = 0; j < nums[i - 1]; ++j) {11        res[k++] = nums[i];12      }13    }14    return res;15  }16}

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

1class Solution {2public:3  vector<int> decompressRLElist(vector<int> &nums) {4    vector<int> res;5    for (int i = 1; i < nums.size(); i += 2) {6      for (int j = 0; j < nums[i - 1]; ++j) {7        res.push_back(nums[i]);8      }9    }10    return res;11  }12};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem