Decompress Run-Length Encoded List

EASY

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

Approaches

Checkout 2 different approaches to solve Decompress Run-Length Encoded List. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: O(S), where S is the size of the decompressed list. This space is required to store the `resultList`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Decompress Run-Length Encoded List. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Decompress Run-Length Encoded List

Data Structures:

Array