Leetcode 1313. Decompress Run-Length Encoded List

Problem Explanation

The problem given requires us to use run-length encoding, a simple form of data compression where run of data are stored as a single data value and count, to decompress a list of integers.

The provided list is formatted such that every two elements represent the occurrence and value of an element in the decompressed list. Specifically, this means that for every pair of integers (a, b) at index i and i+1, b is the integer that should occur a times in the output list.

Using this, we need to return the decompressed list.


Let's break it down with an example:

3Input: nums = [1,2,3,4]
4Output: [2,4,4,4]

In the above example, the pair of elements (1,2) tells us that the integer 2 appears once, while the pair (3,4) tells us that the integer 4 appears thrice.

Solution Approach

A straightforward way to solve the problem is to iterate over the input list in steps of two (since the integers we are concerned with come in pairs). For each pair, we insert the second integer into the answer list the number of times specified by the first integer.

Solution in Python

3class Solution:
4    def decompressRLElist(self, nums):
5        ans = []
6        for i in range(0, len(nums), 2):
7            ans.extend([nums[i+1]] * nums[i])
8        return ans

Solution in Java

3class Solution {
4    public List decompressRLElist(int[] nums) {
5        List<Integer> ans = new ArrayList<>();
6        for (int i = 0; i < nums.length; i+=2) {
7            for(int j = 0; j < nums[i]; j++) {
8                ans.add(nums[i+1]);
9            }
10        }
11        return ans;
12    }

Solution in JavaScript

3class Solution {
4    decompressRLElist(nums) {
5        let ans = [];
6        for(let i = 0; i < nums.length; i += 2){
7            for(let j = 0; j < nums[i]; j++){
8                ans.push(nums[i+1]);
9            }
10        }
11        return ans;
12    }

Solution in C++

3class Solution {
5    vector<int> decompressRLElist(vector<int>& nums) {
6        vector<int> ans;
7        for (int i = 0; i < nums.size(); i += 2){
8            ans.insert(ans.end(), nums[i], nums[i+1]);
9        }
10        return ans;
11    }

Solution in C#

3public class Solution {
4    public int[] DecompressRLElist(int[] nums) {
5        List<int> ans = new List<int>();
6        for (int i = 0; i < nums.Length; i+=2){
7            for(int j = 0; j < nums[i]; j++){
8                ans.Add(nums[i+1]);
9            }
10        }
11        return ans.ToArray();
12    }

Each of the solutions do basically the same thing in different languages. They iterate over the given run-length encoded list in pairs (using a step of 2 in the loop), and then append the second element of the pair the number of times specified by the first element of the pair to the result list. The "for" loop nested inside the main one ensures the correct number of repetitions for each integer. After iterating through the given list, the constructed result list (or array for C#) is returned.# Solution in R

3decompressRLElist <- function(nums) {
4  ans <- c()
5  for (i in seq(1, length(nums), by = 2)){
6    ans <- c(ans, rep(nums[i+1], nums[i]))
7  }
8  return(ans)

Solution in Ruby

3def decompress_rlelist(nums)
4  ans = []
5  for i in (0...nums.length).step(2) do
6    ans.concat([nums[i+1]] * nums[i])
7  end
8  ans

Solution in Swift

3func decompressRLElist(_ nums: [Int]) -> [Int] {
4    var ans = [Int]()
5    for i in stride(from: 0, to: nums.count, by: 2){
6        for _ in 0..<nums[i]{
7            ans.append(nums[i+1])
8        }
9    }
10    return ans

Solution in GO

3func decompressRLElist(nums []int) []int {
4    ans := []int{}
5    for i := 0; i < len(nums); i += 2 {
6        for j := 0; j < nums[i]; j++ {
7            ans = append(ans, nums[i+1])
8        }
9    }
10    return ans

The solutions in R, Ruby, Swift, and GO also exploit primarily the same logic. In the case of the R solution, it must concatenate the list of repeated values to the resultant list using the c() function. This iteration is done using the rep() function to repeat the second element of each pair the number of times specified by the first element.

In the case of Ruby solution, it use the concat() function to append the repeated value to the result array.

In the Swift solution, the for loop in Swift is designed in such a way that a variable that does not change during the iteration can be created using an underscore (_), which cleans up the code somewhat. The stride() function is used to generate a sequence of values, which in this case is used to access each pair in the list.

Finally, in the case of the Go solution, the append() function is used to append the repeated value to the result slice. This mostly uses the same logic as the solutions in the other languages while taking advantage of Go's slice functionality, but of course is adapted for Go's syntax and conventions.

All these solutions have a time complexity of O(n) and a space complexity of O(1) excluding the output space. Here, n refers to the size of the given list. These complexity aspects makes these solutions quite efficient.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫