This is our solution and implementation to problem #1313: Decompress Run-Length Encoded List on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Decompress Run-Length Encoded List on LeetCode.
Problem Analysis
Each input list nums has an even number of elements. Each even index (starting from 0) and the index to its right form a pair. We need to return an output list, and each pair describes a number and the amount of consecutive occurences of that number in the output. We need to fill in the output list with those numbers with the correct counts.
Implementation Strategy
We will iterate over nums once to calculate the size of the output. Then, we will initialize the output list with that size and iterate over nums again. For each pair, fill in the portion of the array as described by that pair.
Space and Time Complexity
The time complexity is O(n) as we iterate over the list exactly twice. The space complexity is O(n) because the size of the output is proportional to the size of the input.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.