Decompress Run-Length Encoded List — Problem & Solution
Decompress Run-Length Encoded List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Decompress Run-Length Encoded List is an easy coding problem on arrays and simulation, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays, Simulation
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a run-length encoded list nums of even length. Consider each adjacent pair [freq, val] = [nums[2i], nums[2i + 1]]; each pair describes freq copies of val.
Concatenate all the decoded runs, in order, and return the resulting list.
Example 1
Input: nums = [1,2,3,4]
Output: [2,4,4,4]
Explanation: [1,2] gives one 2 and [3,4] gives three 4s.
Example 2
Input: nums = [1,1,2,3]
Output: [1,3,3]
Example 3
Input: nums = [2,9]
Output: [9,9]
Constraints
2 <= nums.length <= 40nums.length is even.1 <= nums[i] <= 40
Hints for Decompress Run-Length Encoded List
Hint 1
Step through the array two entries at a time.
Hint 2
The first entry of the pair is the repeat count, the second is the value to repeat.
How to solve Decompress Run-Length Encoded List
Walk the input two entries at a time; the first is a repeat count, the second the value to repeat.
Approach
- For
i = 0, 2, 4, …, appendnums[i]copies ofnums[i + 1].
Why it works
Run-length encoding is a sequence of (freq, val) pairs, and decoding is just expanding each pair in order.
Complexity
- Time —
O(total output length) - Space —
O(total output length)
Pitfalls
- Swapping the roles of the pair (value, then count) is the common slip.
Reference solution
Python
def decompressRLElist(nums):
out = []
for i in range(0, len(nums), 2):
out.extend([nums[i + 1]] * nums[i])
return outJava
public static int[] decompressRLElist(int[] nums) {
int total = 0;
for (int i = 0; i < nums.length; i += 2) total += nums[i];
int[] out = new int[total];
int pos = 0;
for (int i = 0; i < nums.length; i += 2) {
for (int k = 0; k < nums[i]; k++) out[pos++] = nums[i + 1];
}
return out;
}C++
vector<int> decompressRLElist(vector<int>& nums) {
vector<int> out;
for (size_t i = 0; i < nums.size(); i += 2) {
for (int k = 0; k < nums[i]; k++) out.push_back(nums[i + 1]);
}
return out;
}JavaScript
var decompressRLElist = function(nums) {
const out = [];
for (let i = 0; i < nums.length; i += 2) {
for (let k = 0; k < nums[i]; k++) out.push(nums[i + 1]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays