1313. Decompress Run-Length Encoded List
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 85.4%
Problem Breakdown
The problem requires us to decompress a list that has been encoded using run-length encoding. The input is a list of integers nums where each pair of elements [freq, val] = [nums[2*i], nums[2*i+1]] represents freq occurrences of the value val. Our task is to generate and return the decompressed list by concatenating all such sublists.
Inputs:
- A list of integers
numswhere the length is even (i.e.,nums.length % 2 == 0).
Outputs:
- A decompressed list of integers.
Implicit Constraints or Tricky Edge Cases:
- The input list will always have an even number of elements.
- Each frequency (
freq) and value (val) pair is non-negative and within the range[1, 100]. - There are no negative numbers in the input list.
- The decompressed list could potentially be large if any
freqis high.
Intuition
A brute-force approach would involve iterating through the input list, checking each pair of elements, and appending the value to a result list according to its frequency. This approach is straightforward but may not be optimal in terms of space complexity since we are directly building the final decompressed list.
The key insight is that we can pre-calculate the size of the decompressed list by summing up all frequencies. This allows us to allocate the exact amount of memory needed for the result list upfront, which can improve performance and reduce overhead compared to dynamically resizing a list as elements are appended.
Approach
- Initialize an empty list
resultwith a size equal to the total frequency of all elements in the input list. - Iterate through the input list in steps of 2 (since each pair consists of
[freq, val]). - For each pair:
- Extract the frequency (
freq) and value (val). - Use a loop to fill the
resultlist withfreqoccurrences ofval.
- Extract the frequency (
- Return the decompressed list.
This approach ensures that we efficiently build the decompressed list without unnecessary memory reallocations.
Complexity Analysis
-
Time Complexity: (O(n)), where (n) is the length of the input list
nums. We iterate through the list once, and for each pair, we perform a constant number of operations. -
Space Complexity: (O(m)), where (m) is the total frequency of all elements in the input list. This is because we pre-allocate a list of size equal to the sum of all frequencies.
Solution
def decompressRLElist(nums):
# Calculate the total length of the decompressed list
total_length = sum(nums[::2])
# Initialize the result list with the calculated total length
result = [0] * total_length
# Index to keep track of where to insert the next value in the result list
index = 0
# Iterate through the nums list in steps of 2
for i in range(0, len(nums), 2):
freq = nums[i]
val = nums[i + 1]
# Fill the result list with 'freq' occurrences of 'val'
for _ in range(freq):
result[index] = val
index += 1
return result
# Example usage:
print(decompressRLElist([1,2,3,4])) # Output: [2,4,4,4]
print(decompressRLElist([1,1,2,3])) # Output: [1,3,3]
Edge Cases Handled
- Even Length Input: The code assumes the input list has an even length, as per the problem constraints.
- Single Pair Input: If the input list contains only one pair
[freq, val], the decompressed list will simply containfreqoccurrences ofval. - All Frequencies are 1: If all frequencies in the input list are 1, the decompressed list will be a simple concatenation of all values.
- High Frequencies: The code efficiently handles cases where some frequencies are high by pre-calculating the total length and using it to allocate the result list.