LeetCode Problem 1313

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 1313, Decompress Run-Length Encoded List

Problem Understanding

This problem asks us to reconstruct an array that was compressed using a simple run-length encoding format.

The input array nums always contains an even number of elements. Every two consecutive elements form a pair:

• The first value represents a frequency, called freq
• The second value represents a number, called val

For every pair [freq, val], we must create a subarray containing freq copies of val. After generating all subarrays, we concatenate them together in the same order to produce the final decompressed list.

For example, if we see the pair [3, 4], it means we should generate:

[4, 4, 4]

If the entire input is:

[1,2,3,4]

then:

• [1,2] becomes [2]
• [3,4] becomes [4,4,4]

Combining them gives:

[2,4,4,4]

The constraints are very small:

• nums.length <= 100
• Every value is between 1 and 100

This tells us that efficiency is not a major concern. Even a straightforward simulation approach will easily fit within time limits.

The problem also guarantees:

• The array length is even
• Every frequency is positive
• Every value is positive

Because of these guarantees, we do not need to handle malformed input such as missing pairs or zero frequencies.

There are still several edge cases worth considering:

• A frequency of 1, which means only one copy should be added
• Multiple consecutive pairs with the same value
• The smallest possible input size of two elements
• Very large frequencies relative to the constraints, which could expose incorrect loop logic or indexing mistakes

Approaches

Brute Force Approach

The brute-force approach directly follows the problem statement.

We iterate through the array two elements at a time. For every pair:

[freq, val]

we repeatedly append val into the result array exactly freq times.

This approach is correct because it literally performs the decompression exactly as described in the problem.

Although this method uses nested loops, the constraints are small enough that performance is completely acceptable. The total number of appended elements is bounded by the final decompressed array size.

Optimal Approach

The optimal approach is conceptually similar, but instead of appending one value at a time inside an inner loop, we can use list or slice expansion operations to append multiple copies at once.

The key observation is that each pair independently contributes a contiguous block of repeated values. Since the final answer is simply the concatenation of these blocks, we can efficiently generate each block and append it directly.

In Python, we can use:

[val] * freq

to create repeated values efficiently.

In Go, we typically use a loop because slices do not support direct multiplication like Python lists.

Even though the asymptotic complexity remains the same, the implementation becomes cleaner and easier to understand.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + k)	O(k)	Appends one value at a time using nested loops
Optimal	O(n + k)	O(k)	Builds repeated blocks directly and concatenates them

Here:

• n is the length of nums
• k is the size of the decompressed output array

Algorithm Walkthrough

1. Initialize an empty result array that will store the decompressed values.
2. Traverse the input array in steps of two because every pair of elements represents one encoded block.
3. For each iteration:

• Read freq = nums[i]
• Read val = nums[i + 1]

4. Generate freq copies of val.

• In Python, this can be done with:

[val] * freq

• In Go, we append val repeatedly inside a loop.

5. Append the generated values to the result array.
6. Continue processing until all pairs have been handled.
7. Return the final decompressed array.

Why it works

Each adjacent pair in the input uniquely defines one contiguous segment of the decompressed array. The algorithm processes pairs in left-to-right order and appends exactly freq copies of val for every pair. Because every segment is generated correctly and concatenated in the original order, the final array exactly matches the required decompressed output.

Python Solution

from typing import List

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        result = []

        for i in range(0, len(nums), 2):
            freq = nums[i]
            val = nums[i + 1]

            result.extend([val] * freq)

        return result

The implementation begins by creating an empty list called result, which will store the decompressed numbers.

The loop iterates through nums with a step size of 2 because every pair of elements forms one encoded unit. At each iteration:

• freq stores how many times the value should appear
• val stores the actual number to repeat

The expression:

[val] * freq

creates a temporary list containing freq copies of val.

The extend() method appends all of these values into the result list at once. After processing all pairs, the completed decompressed list is returned.

Go Solution

func decompressRLElist(nums []int) []int {
    result := []int{}

    for i := 0; i < len(nums); i += 2 {
        freq := nums[i]
        val := nums[i+1]

        for j := 0; j < freq; j++ {
            result = append(result, val)
        }
    }

    return result
}

The Go implementation follows the same logic as the Python version. Since Go slices do not support multiplication like Python lists, we append the value repeatedly using an inner loop.

Go slices automatically resize as needed during append, making them a natural fit for this problem.

There are no integer overflow concerns because all values are very small according to the constraints.

Worked Examples

Example 1

Input:

nums = [1,2,3,4]

Initial state:

result = []

Iteration	freq	val	Values Added	result
i = 0	1	2	[2]	[2]
i = 2	3	4	[4,4,4]	[2,4,4,4]

Final output:

[2,4,4,4]

Example 2

Input:

nums = [1,1,2,3]

Initial state:

result = []

Iteration	freq	val	Values Added	result
i = 0	1	1	[1]	[1]
i = 2	2	3	[3,3]	[1,3,3]

Final output:

[1,3,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + k)	We scan the input once and append each decompressed element once
Space	O(k)	The output array stores all decompressed elements

Here:

• n is the size of the compressed input array
• k is the size of the decompressed output array

The algorithm must produce all decompressed elements, so O(k) work and space are unavoidable.

Test Cases

from typing import List

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        result = []

        for i in range(0, len(nums), 2):
            freq = nums[i]
            val = nums[i + 1]
            result.extend([val] * freq)

        return result

sol = Solution()

assert sol.decompressRLElist([1,2,3,4]) == [2,4,4,4]  # basic example
assert sol.decompressRLElist([1,1,2,3]) == [1,3,3]  # second provided example

assert sol.decompressRLElist([1,5]) == [5]  # minimum input size
assert sol.decompressRLElist([2,7]) == [7,7]  # single pair with repetition

assert sol.decompressRLElist([3,1,2,2]) == [1,1,1,2,2]  # multiple groups
assert sol.decompressRLElist([4,9,1,8]) == [9,9,9,9,8]  # large first frequency

assert sol.decompressRLElist([1,3,1,3,1,3]) == [3,3,3]  # repeated identical values
assert sol.decompressRLElist([5,10]) == [10,10,10,10,10]  # larger frequency

assert sol.decompressRLElist([2,1,3,2,1,3]) == [1,1,2,2,2,3]  # mixed frequencies

Test	Why
[1,2,3,4]	Validates the main example
[1,1,2,3]	Confirms multiple groups concatenate correctly
[1,5]	Tests smallest valid input
[2,7]	Tests repetition within one pair
[3,1,2,2]	Verifies multiple decompressed segments
[4,9,1,8]	Tests uneven frequencies
[1,3,1,3,1,3]	Confirms repeated values across pairs
[5,10]	Tests larger repetition counts
[2,1,3,2,1,3]	Verifies several mixed groups

Edge Cases

One important edge case is the minimum input size, such as:

[1,5]

This case contains only one frequency-value pair. Some implementations accidentally assume multiple pairs exist or incorrectly handle loop boundaries. Our implementation safely iterates in steps of two and correctly processes even a single pair.

Another important edge case is when the frequency equals 1. For example:

[1,9]

This can expose off-by-one errors in loops. If the loop runs zero times or two times by mistake, the output becomes incorrect immediately. Our implementation uses either list multiplication or a loop that executes exactly freq times, guaranteeing one copy is added.

A third important edge case is repeated values across different pairs, such as:

[2,3,1,3]

The decompressed output should become:

[3,3,3]

A buggy implementation might accidentally merge frequencies incorrectly or overwrite earlier values. Our algorithm processes each pair independently and appends results sequentially, preserving the correct order and count.

Another subtle edge case involves larger frequencies near the constraint limit, such as:

[100,1]

This tests whether the implementation correctly handles many repeated insertions. Since the constraints are small and the algorithm appends values directly into the result list, it handles these cases without issue.