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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decompress Run-Length Encoded List

Number: 1241

Difficulty: Easy

Paid? No

Companies: Amazon, Google

Problem Description

Given an integer array representing a run-length encoded list where each pair of adjacent elements [freq, val] represents freq occurrences of val, decompress the list by expanding each pair into a sublist of repeated values and concatenating these sublists.

Key Insights

  • The input array always contains pairs, so iterate over it two elements at a time.
  • For each pair [freq, val], generate a sublist with freq copies of val.
  • Concatenate these sublists to form the final decompressed list.
  • The problem requires only simple iteration and replication.

Space and Time Complexity

Time Complexity: O(n) where n is the total number of elements in the decompressed list (i.e., the sum of all frequency values). Space Complexity: O(n) for storing the output list.

Solution

Use a single pass through the input array by iterating over its indices in steps of two. For each pair, use multiplication of an array (or equivalent in your language) to replicate the value freq times. Append or concatenate the resulting list of values to a results container. The approach leverages basic array operations without requiring additional complex data structures.

Code Solutions

# Function to decompress the run-length encoded list
def decompressRLElist(nums):
    # Initialize the result list
    result = []
    # Iterate through the list in steps of 2 (each step represents a pair [freq, val])
    for i in range(0, len(nums), 2):
        freq = nums[i]      # Frequency of the value
        val = nums[i+1]     # The value to be repeated
        # Extend the result list with freq copies of val
        result.extend([val] * freq)
    return result

# Example usage:
nums = [1, 2, 3, 4]
print(decompressRLElist(nums))  # Output: [2, 4, 4, 4]
← Back to All Questions