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.

Example

Let's break it down with an example:

1
2
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

1
2python
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

1
2java
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    }
13}

Solution in JavaScript

1
2javascript
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    }
13}

Solution in C++

1
2c++
3class Solution {
4public:
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    }
12};

Solution in C#

1
2csharp
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    }
13}

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

1
2R
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)
9}

Solution in Ruby

1
2ruby
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
9end

Solution in Swift

1
2swift
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
11}

Solution in GO

1
2go
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
11}

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.