Decompress Run-Length Encoded List
LeetCode 1313, Decompress Run-Length Encoded List, gives you an even-length integer array nums where every consecutive pair (nums[2*i], nums[2*i+1]) represents a frequency and a value. Your job is to build the decompressed list by appending each value the specified number of times. For example, given [1, 2, 3, 4], the first pair says "append 2 once" and the second says "append 4 three times", producing [2, 4, 4, 4].
Why this problem matters
Run-length encoding is one of the simplest compression schemes. Instead of storing every element, you store (count, value) pairs. This pattern shows up in image encoding (think bitmap compression), text compression, and data serialization. Understanding how to decode it is the foundation for working with any RLE-based format.
Even though this problem is tagged easy, it reinforces a fundamental skill: iterating through an array in fixed-size chunks. You will use this same stepping pattern in problems involving pairs, triples, or any grouped structure.
The key insight
Process the array two elements at a time. At every even index 2*i, nums[2*i] is the frequency and nums[2*i+1] is the value. Append the value to your result list exactly freq times. That is it. No sorting, no searching, no clever tricks. Just a clean linear pass through the input.
The solution
def decompressRLElist(nums):
result = []
for i in range(0, len(nums), 2):
freq = nums[i]
val = nums[i + 1]
result.extend([val] * freq)
return result
The loop steps through nums by 2, grabbing each (freq, val) pair. Python's list multiplication [val] * freq creates a list of freq copies of val, and extend appends them all to the result in one call.
Python's [val] * freq is a compact way to create a list of repeated values. It avoids a nested loop and reads more naturally. In other languages, you would use a simple inner loop or a fill function.
Visual walkthrough
Step 1: Process pair (1, 2)
Pair 1: freq = 1, val = 2 ... append [2]
freq = 1, val = 2. Append 2 exactly once. Result: [2].
Step 2: Process pair (3, 4)
Pair 2: freq = 3, val = 4 ... append [4, 4, 4]
freq = 3, val = 4. Append 4 three times. Result: [2, 4, 4, 4].
Step 3: All pairs processed
Pair 2: freq = 0, val = 0 ... append []
No more pairs to process. Final decompressed list: [2, 4, 4, 4].
Notice that the output array can be much larger than the input. A single pair like (1000, 7) produces 1000 elements from just two input values. The output size depends entirely on the frequency values, not just the input length.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n + total output size) | O(output size) |
Here, n is the length of the input array. You iterate through all n elements once, but the real work is in building the output. If the frequencies sum to S, you produce S output elements. In the worst case, S can be much larger than n. The space usage is proportional to the output size since that is what you are constructing and returning.
The building blocks
1. Pair-wise iteration
for i in range(0, len(nums), 2):
freq = nums[i]
val = nums[i + 1]
The range(0, len(nums), 2) pattern steps by 2 through the array. This is the standard way to process elements in pairs. You will see this same pattern in problems that deal with coordinate pairs, key-value sequences, or any data encoded in fixed-size groups.
2. List repetition
result.extend([val] * freq)
Python's * operator on lists creates a new list with the element repeated. [4] * 3 gives [4, 4, 4]. Combined with extend, this is an efficient one-liner for appending multiple copies of a value. The alternative would be a loop calling append one element at a time, which works but is more verbose.
Edge cases
- Single pair. If
nums = [5, 8], the result is[8, 8, 8, 8, 8]. Only one pair to process, but the output can still be large. - Frequency of 1. Each value appears exactly once. The output is the same length as half the input.
- Large frequencies. The constraints allow frequencies up to 100, so the output array can be up to 50 times the number of pairs. Make sure your solution handles this without special cases.
- Many pairs. With up to 50 pairs (100 elements in
nums), the algorithm remains fast. The bottleneck is always the output size, not the number of pairs.
From understanding to recall
This problem feels almost too simple when you read through it here. Grab pairs, repeat values, done. But simplicity can be deceptive in an interview setting. Under pressure, you might second-guess whether to step by 1 or by 2, fumble the index math for freq vs val, or forget to use extend instead of append.
Spaced repetition locks in these micro-decisions. After a few reps, the range(0, len(nums), 2) stepping pattern becomes automatic. You do not need to rederive it. You recognize it, apply it, and move on to the next problem. That is the difference between understanding a pattern and being able to produce it under time pressure.
Related posts
- String Compression - The reverse operation: encoding runs in a string
- RLE Iterator - A more advanced take on run-length encoding
- Decode String - Another decoding problem with nested patterns
This is one of those problems where the code almost writes itself once you see the pair structure. Build that recognition through practice, and you will breeze through similar array decoding questions.