Skip to main content
Talentd

Decompress Run-Length Encoded List - Solution & Explanation

EasyArray12 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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 <= 100
  • nums.length % 2 == 0
  • 1 <= 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.

This C solution calculates the total length of the resulting decompressed list first. It then iteratively populates this list according to the frequency and value pairs found in the nums array. Memory allocation is done dynamically to ensure the list can grow as needed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is half the length of nums, since we process each pair once.
Space Complexity: O(m), where m is the size of the decompressed list.

Try this approach in the editor →

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.

This Java solution uses the functional programming features of Java Streams. It creates a nested stream over frequency and value pairs and flattens them into a single list.

Code

JavaPythonJavaScript

Java

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(n), where n is half the length of nums, since we process each pair once.
Space Complexity: O(m), where m is the size of the decompressed list.

Functional Approach

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.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative ExpansionO(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.

Video Solution

Leetcode 1313: Decompress Run-Length Encoded List • Algorithms Casts • 2,889 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Decompress Run-Length Encoded List with our built-in code editor and test cases.

Practice on FleetCode
Previous

String Compression