Decompress Run-Length Encoded List

Easy
193.

Decompress Run-Length Encoded List

Decompress Run-Length Encoded List is an easy coding problem on arrays and simulation, asked in Amazon and Infosys interviews.

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 <= 40
  • nums.length is even.
  • 1 <= nums[i] <= 40
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var decompressRLElist = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 40
  • nums.length is even.
  • 1 <= nums[i] <= 40

Hints for Decompress Run-Length Encoded List

  1. Hint 1

    Step through the array two entries at a time.

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

  1. For i = 0, 2, 4, …, append nums[i] copies of nums[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 out

Java

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