We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Decompress Run-Length Encoded List

Difficulty: Easy

Problem Description

We are given a list nums of integers representing a list compressed with run-length encoding. For each adjacent pair of elements [freq, val] = [nums[2*i], nums[2*i+1]], we need to generate a sublist of freq elements, each with the value val. The task is to concatenate all these sublists from left to right to generate the decompressed list and return it.

Key Insights

  • The input list nums contains pairs of integers where the first integer is the frequency and the second is the corresponding value.
  • The output list is created by repeating each value according to its frequency.
  • The total length of the output list is determined by the sum of all frequencies.
  • We can use a simple loop to process each pair of elements in the input list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of pairs in the input list (i.e., nums.length / 2). Space Complexity: O(m), where m is the length of the decompressed output list.

Solution

To solve the problem, we will iterate through the input list nums in steps of two, extracting the frequency and value from each pair. We will use a dynamic array (or list) to store the decompressed elements. For each pair, we will append the value to the output list the number of times specified by the frequency. Finally, we will return the constructed list.

Code Solutions

def decompressRLElist(nums):
    result = []  # Initialize an empty list to store the result
    for i in range(0, len(nums), 2):  # Iterate over the list in steps of 2
        freq = nums[i]  # First element of the pair is the frequency
        val = nums[i + 1]  # Second element is the value
        result.extend([val] * freq)  # Append 'val' freq times to the result list
    return result  # Return the decompressed list
← Back to All Questions