Decompress Run-Length Encoded List solution and explanation
Google
9 more videos on this problem
Leetcode 1313: Decompress Run-Length Encoded ListAlgorithms Casts · 11:21 · 2K views
LeetCode 1313. Decompress Run-Length Encoded List Solution Explained - JavaAlgorithms and Data Structures Course · 8:46 · 1K views
Leetcode 1313. Decompress Run-Length Encoded List PythonTechZoo · 2:38 · 1K views
1313 Decompress Run Length Encoded List Javacstutorials · 7:13 · 790 views
Leetcode 1313 | Decompress Run-Length Encoded List | EasyThe Humble Coder · 4:56 · 707 views
LeetCode 1313 | Decompress Run-Length Encoded List | Array | JavaSleepy Cracker · 5:02 · 496 views
leetcode - 1313 Decompress Run-Length Encoded List JavaScript SolutionlitCode · 7:48 · 449 views
LEETCODE SOLUTION 1313 | Decompress Run-Length Encoded List | LEETCODE CONTEST | EASY | Javascript |CodingForBeginners · 6:11 · 448 views
LeetCode 1313 : Decompress Run-Length Encoded List | Solution in JAVAAmit Manjarly · 7:51 · 425 views
How to Solve "1313 Decompress Run-Length Encoded List" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 4:49 · 380 views
The problem
We are given a list nums of integers representing a list compressed with run-length encoding.
Consider each adjacent pair of elements [freq, val] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.
Return the decompressed list.
Example 1:
Input: nums = [1,2,3,4] Output: [2,4,4,4] Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2]. The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4]. At the end the concatenation [2] + [4,4,4] is [2,4,4,4].
Example 2:
Input: nums = [1,1,2,3] Output: [1,3,3]
Constraints:
2 <= nums.length <= 100nums.length % 2 == 01 <= nums[i] <= 100
Approach overview
Problem Overview: You receive an array where every two elements represent a run-length encoded pair [freq, val]. For each pair, append val to the result array freq times. The goal is to reconstruct the fully decompressed list.
Approach 1: Iterative Expansion (O(n + m) time, O(m) space)
The direct solution iterates through the input array two elements at a time. The first value represents the frequency and the second represents the number that should be repeated. For each pair, append val to a result array exactly freq times using a loop or built‑in array expansion. This approach works because the encoding format guarantees that every pair describes a contiguous block in the final output. The total runtime is O(n + m), where n is the length of the encoded array and m is the size of the decompressed output. Space complexity is O(m) since the final array must be stored.
This method relies purely on sequential iteration, making it a straightforward application of array traversal. The algorithm is easy to implement in any language and avoids unnecessary data structures.
Approach 2: Functional Expansion (O(n + m) time, O(m) space)
A functional style solution treats each encoded pair as a small transformation that produces a repeated sequence. Instead of manually pushing values in nested loops, you generate a temporary array of size freq filled with val, then flatten these arrays into a single result using operations like flatMap, list comprehensions, or stream pipelines. Each pair is mapped to its decompressed segment, and the segments are concatenated in order.
The core work remains the same: each output element must be written exactly once, so the time complexity stays O(n + m). Space complexity is also O(m) because the result list stores the entire decompressed sequence. Functional approaches are common in modern Java, Python, and JavaScript when working with declarative transformations over arrays.
Recommended for interviews: The iterative expansion approach is what most interviewers expect. It demonstrates clear understanding of run‑length encoding and basic array iteration without unnecessary abstractions. Functional solutions are clean and concise in production code, but the explicit iterative version communicates the logic more clearly during interviews.
Approach 1: Iterative Approach
The iterative approach involves traversing the list in a linear manner, taking each pair of numbers as a frequency-value pair, and directly constructing the decompressed list by appending the value-frequency times.
def decompressRLElist(nums):
result = []
for i in range(0, len(nums), 2):
result.extend([nums[i+1]] * nums[i])
return result
# Example use case
nums = [1, 2, 3, 4]
decompressed = decompressRLElist(nums)
print(decompressed)import java.util.ArrayList;
import java.util.List;
public class DecompressRLEList {
public static List<Integer> decompressRLElist(int[] nums) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i += 2) {
for (int j = 0; j < nums[i]; j++) {
result.add(nums[i + 1]);
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
List<Integer> decompressed = decompressRLElist(nums);
System.out.println(decompressed);
}
}#include <vector>
std::vector<int> decompressRLElist(std::vector<int>& nums) {
std::vector<int> result;
for (size_t i = 0; i < nums.size(); i += 2) {
result.insert(result.end(), nums[i], nums[i+1]);
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4};
std::vector<int> decompressed = decompressRLElist(nums);
for (int val : decompressed) {
std::cout << val << " ";
}
return 0;
}function decompressRLElist(nums) {
const result = [];
for (let i = 0; i < nums.length; i += 2) {
result.push(...Array(nums[i]).fill(nums[i + 1]));
}
return result;
}
// Example use case
const nums = [1, 2, 3, 4];
const decompressed = decompressRLElist(nums);
console.log(decompressed);#include <stdio.h>
#include <stdlib.h>
int* decompressRLElist(int* nums, int numsSize, int* returnSize) {
int totalLength = 0;
// Calculate the length of the decompressed list
for (int i = 0; i < numsSize; i += 2) {
totalLength += nums[i];
}
int* result = (int*)malloc(totalLength * sizeof(int));
*returnSize = totalLength;
int index = 0;
// Fill the decompressed list
for (int i = 0; i < numsSize; i += 2) {
int freq = nums[i];
int val = nums[i+1];
for (int j = 0; j < freq; j++) {
result[index++] = val;
}
}
return result;
}
int main() {
int nums[] = {1, 2, 3, 4};
int returnSize;
int* decompressed = decompressRLElist(nums, 4, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", decompressed[i]);
}
free(decompressed);
return 0;
}using System;
using System.Collections.Generic;
public class DecompressRLEList {
public static List<int> DecompressRLEList(int[] nums) {
List<int> result = new List<int>();
for (int i = 0; i < nums.Length; i += 2) {
for (int j = 0; j < nums[i]; j++) {
result.Add(nums[i + 1]);
}
}
return result;
}
public static void Main() {
int[] nums = {1, 2, 3, 4};
List<int> decompressed = DecompressRLEList(nums);
Console.WriteLine(string.Join(" ", decompressed));
}
}The Python solution employs list comprehension for simplicity. It appends copies of the values to result by unpacking the compressed value list with the frequency using the * operator in the list context.
Time Complexity: O(n*m), where n is half the length of nums, and m is the average frequency.
Space Complexity: O(m), where m is the size of the decompressed list.
Approach 2: Functional Approach
The functional approach leverages higher-order functions like map and reduce or similar constructs available in various languages to iterate through and build the decompressed list. This approach reduces the boilerplate code by focusing on function composition.
from itertools import chain
def decompressRLElist(nums):
return list(chain.from_iterable([nums[i+1]] * nums[i] for i in range(0, len(nums), 2)))
# Example use case
nums = [1, 2, 3, 4]
decompressed = decompressRLElist(nums)
print(decompressed)import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.List;
import java.util.stream.IntStream;
public class DecompressRLEListFunctional {
public static List<Integer> decompressRLElist(int[] nums) {
return IntStream.range(0, nums.length / 2)
.mapToObj(i -> IntStream.range(0, nums[2 * i])
.mapToObj(j -> nums[2 * i + 1])
.collect(Collectors.toList()))
.flatMap(List::stream)
.collect(Collectors.toList());
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
List<Integer> decompressed = decompressRLElist(nums);
System.out.println(decompressed);
}
}function decompressRLElist(nums) {
return nums.reduce((acc, _, i) => {
if (i % 2 === 0) acc.push(...Array(nums[i]).fill(nums[i + 1]));
return acc;
}, []);
}
// Example use case
const nums = [1, 2, 3, 4];
const decompressed = decompressRLElist(nums);
console.log(decompressed);This Python solution takes advantage of the itertools.chain to flatten the list comprehension, producing a single list from a generator expression.
Time Complexity: O(n*m), where n is half the length of nums, and m is the average frequency.
Space Complexity: O(m), where m is the size of the decompressed list.
Approach 3: Simulation
We can directly simulate the process described in the problem. Traverse the array nums from left to right, each time taking out two numbers freq and val, then repeat val freq times, and add these freq vals to the answer array.
The time complexity is O(n), where n is the length of the array nums. We only need to traverse the array nums once. Ignoring the space consumption of the answer array, the space complexity is O(1).
function decompressRLElist(nums: number[]): number[] {
const ans: number[] = [];
for (let i = 0; i < nums.length; i += 2) {
for (let j = 0; j < nums[i]; j++) {
ans.push(nums[i + 1]);
}
}
return ans;
}func decompressRLElist(nums []int) (ans []int) {
for i := 1; i < len(nums); i += 2 {
for j := 0; j < nums[i-1]; j++ {
ans = append(ans, nums[i])
}
}
return
}impl Solution {
pub fn decompress_rl_elist(nums: Vec<i32>) -> Vec<i32> {
let mut ans = Vec::new();
let n = nums.len();
let mut i = 0;
while i < n {
let freq = nums[i];
let val = nums[i + 1];
for _ in 0..freq {
ans.push(val);
}
i += 2;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n*m), where n is half the length of |
| Functional Approach | Time Complexity: O(n*m), where n is half the length of |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Expansion | O(n + m) | O(m) | Best general solution. Clear logic using simple loops and array appends. |
| Functional Expansion (map/flatMap) | O(n + m) | O(m) | When using modern language features like streams, list comprehensions, or functional pipelines. |
Frequently asked questions
Is Decompress Run-Length Encoded List easy or hard?
The problem is classified as Easy. It focuses on understanding run-length encoding format and performing controlled array expansion. Most solutions require only simple iteration and list operations.
Decompress Run-Length Encoded List Python/Java solution
In Python, iterate through the array in steps of two and extend the result list using [val] * freq. In Java, loop through pairs and append val to an ArrayList freq times. Both implementations follow the same O(n + m) time and O(m) space complexity.
How to solve Decompress Run-Length Encoded List in O(n)?
The optimal solution iterates through the encoded array in steps of two. For each pair [freq, val], append val to the result freq times. Since every output element is generated once, the runtime becomes O(n + m), which is optimal for problems that must explicitly build the decompressed list.
What is the best approach for Decompress Run-Length Encoded List?
The iterative expansion approach is the most practical solution. Traverse the array two elements at a time, treat the first value as frequency and the second as the value to repeat, and append it to the result list. This runs in O(n + m) time where m is the decompressed output size, with O(m) space for the result array.
Is Decompress Run-Length Encoded List asked at Google/Amazon/Meta?
Run-length encoding and array expansion problems appear in interviews at large tech companies, especially for entry-level or screening rounds. The problem itself is categorized as Easy on LeetCode but tests understanding of arrays, iteration, and basic data processing.
What data structure is used in Decompress Run-Length Encoded List?
The primary data structure is a dynamic array or list used to store the decompressed output. The algorithm simply iterates over the encoded input array and pushes repeated values into the result array.
What is the time complexity of Decompress Run-Length Encoded List?
The time complexity is O(n + m). n represents the size of the encoded input array, while m is the length of the decompressed output. Each encoded pair is processed once and each output element is written exactly once.