Scale Engineer

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.

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

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.

Solutions

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 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 →

Next problem