# Decompress Run-Length Encoded List
**Difficulty:** EASY
[External](https://leetcode.com/problems/decompress-run-length-encoded-list)
Canonical: https://scaleengineer.com/dsa/problems/decompress-run-length-encoded-list
**Data structures:** Array
---
## Problem
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
## Single-Pass with Dynamic List
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.
**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`.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

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);
            }
        }

        // Convert List<Integer> to int[]
        int[] resultArray = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            resultArray[i] = resultList.get(i);
        }
        return resultArray;
    }
}
```
### Algorithm
- 1. Create an empty `ArrayList` of integers, let's call it `resultList`.
- 2. Iterate through the input array `nums` with a step of 2, from index `i = 0` to `nums.length - 2`.
- 3. In each iteration, get the frequency `freq = nums[i]` and the value `val = nums[i+1]`.
- 4. Start a nested loop that runs `freq` times.
- 5. Inside the nested loop, add `val` to `resultList`.
- 6. After the outer loop finishes, create a new integer array `resultArray` with the same size as `resultList`.
- 7. Copy all elements from `resultList` to `resultArray`.
- 8. Return `resultArray`.

## Two-Pass with Pre-Sized Array
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int[] decompressRLElist(int[] nums) {
        // First pass: calculate the size of the decompressed list
        int size = 0;
        for (int i = 0; i < nums.length; i += 2) {
            size += nums[i];
        }

        // Create the result array with the calculated size
        int[] result = new int[size];
        int currentIndex = 0;

        // Second pass: fill the result array
        for (int i = 0; i < nums.length; i += 2) {
            int freq = nums[i];
            int val = nums[i+1];
            // Use Arrays.fill for potentially faster block assignment
            Arrays.fill(result, currentIndex, currentIndex + freq, val);
            currentIndex += freq;
        }
        return result;
    }
}
```
### Algorithm
- 1. Initialize a variable `totalSize = 0`.
- 2. **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`.
- 3. Create a new integer array `result` of size `totalSize`.
- 4. Initialize an index variable `currentIndex = 0` to keep track of the current position in the `result` array.
- 5. **Second Pass:** Iterate through `nums` again with a step of 2.
- 6. 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`.
- 7. Update `currentIndex` by adding `freq` to it.
- 8. After the loops complete, return the `result` array.

# Solutions
### Java

```java
class Solution {
public
  int[] decompressRLElist(int[] nums) {
    int n = 0;
    for (int i = 0; i < nums.length; i += 2) {
      n += nums[i];
    }
    int[] res = new int[n];
    for (int i = 1, k = 0; i < nums.length; i += 2) {
      for (int j = 0; j < nums[i - 1]; ++j) {
        res[k++] = nums[i];
      }
    }
    return res;
  }
}

```

### Python

```python
class Solution:
    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

```

### CPP

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

```