Decompress Run-Length Encoded List

LeetCode 1241 | Difficulty: Easy

Easy

Problem Description

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 1 `

Topics: Array

---

Approach

Direct Approach

This problem can typically be solved with straightforward iteration or simple data structure usage. Focus on correctness first, then optimize.

When to use

Basic problems that test fundamental programming skills.

---

Solutions

Solution 1: C# (Best: 136 ms)

Metric	Value
Runtime	136 ms
Memory	43 MB
Date	2022-01-14

Solution

public class Solution {
    public int[] DecompressRLElist(int[] nums) {
        int n = nums.Length;
    int total = 0;
    for (int i = 0; i < n; i=i+2)
    {
        total += nums[i];
    }
    int[] result = new int[total];
    int index = 0;
    for (int i = 0; i < n; i=i+2)
    {
        int freq = nums[i];
        int val = nums[i+1];
        for (int j = 0; j < freq; j++)
        {
            result[index++] = val;
        }
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Decompress the given array by repeating nums[2*i+1] a number of times equal to nums[2*i].