1313. Decompress Run-Length Encoded List
Problem Description
The given problem presents a run-length encoded list, which is a common method for compressing data in which consecutive elements are replaced by just one value and the count of that value. The nums
list contains pairs where the first element of each pair represents how many times the next element should appear in the decompressed list.
For instance, if we have a compressed list [3, 4, 1, 2]
, it means we have 3 of 4
s and 1 of 2
in the decompressed list: [4, 4, 4, 2]
.
The challenge is to convert this run-length encoded list into a decompressed list where each pair [freq, val]
is expanded into freq
instances of val
.
Intuition
To solve this problem, we iterate over the given list nums
to process each [freq, val]
pair. Because freq
and val
are always adjacent, starting with freq
, we skip every other element by using a loop that begins at index 1 and moves in steps of 2. This allows us to directly access each val
while its corresponding freq
is just the previous element.
For each freq
and val
pair, we replicate val
, freq
times. The replication can be efficiently accomplished in Python with list multiplication ([val] * freq
). This creates a list of val
repeated freq
times. We then extend our result list with this new list.
The solution is achieved in a straightforward manner through this looping and extending, transforming the encoded list into the desired decompressed version in line with the problem requirements.
Solution Approach
The provided solution employs a simple yet efficient method that directly corresponds to the idea of run-length decoding. We use a basic for
loop to iterate over the input list nums
. The list data structure is the only structure used, which is apt for this task, as Python lists provide an efficient way to manage sequence data and support operations required for the solution.
Here's a step-by-step breakdown of the solution:
-
We initialize an empty list
res
which will hold our decompressed elements. -
The
for
loop starts at index 1 and iterates till the end of thenums
list with a step of 2. This step is important because ourfreq
is always the element just beforeval
(i.e., at indexi - 1
), andval
is at every second index starting from 1 (which isi
in this context). -
In each iteration, we create a list with
val
repeatedfreq
times. This is done by multiplying a single-element list containingval
byfreq
([nums[i]] * nums[i - 1]
). -
We then extend the
res
list with this repeated list. The.extend()
method is used because it adds elements of the list argument to the end of the current list, effectively concatenating them tores
. -
Once the loop has processed all the
[freq, val]
pairs, theres
list contains the fully decompressed list, which is then returned.
Through the use of list indexing, list multiplication, and the .extend()
method, the provided Python solution efficiently decompresses the run-length encoded list with minimal complexity and optimal use of Python's list capabilities.
Here is the code snippet embedded in markdown for clarity:
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
res = []
for i in range(1, len(nums), 2):
res.extend([nums[i]] * nums[i - 1])
return res
This approach is linear in time complexity (O(n)), where n is the number of elements in the input list nums
, as it requires a single pass through the list. The space complexity is also linear (O(n)), as it directly depends on the total number of elements that will be in the decompressed list.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach. Suppose we are given the following compressed list:
[2, 5, 3, 6]
This implies we should have 2 of ‘5’s and 3 of ‘6’s in our decompressed list.
Following the steps of the solution:
-
Initialize an empty list
res
. This will store the final decompressed list. -
Begin a loop starting at index 1 (
i = 1
), since it's the position of the first value to be repeated. We will increment the index by 2 every iteration to jump to the next value to be repeated. -
At index
i = 1
, the element is5
, and the frequency (freq
) is the previous element (nums[i - 1]
), which is2
. We create a list with5
repeated2
times:[5, 5]
. -
Extend the
res
list with this new list:res
now becomes[5, 5]
. -
Move to the next value in the list that needs to be repeated, which is at index
i = 3
(the element is6
). The frequency for6
is3
(nums[i - 1]
). -
Repeat the value
6
,3
times to get[6, 6, 6]
. -
Extend the
res
list with this new list:res
becomes[5, 5, 6, 6, 6]
.
After the loop has finished, the res
list contains the decompressed list that we need, and we return it:
[5, 5, 6, 6, 6]
This approach directly transforms the encoded list [2, 5, 3, 6]
into the desired decompressed version [5, 5, 6, 6, 6]
.
The given Python code, when executed with our example nums
, would return [5, 5, 6, 6, 6]
as expected:
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
res = []
for i in range(1, len(nums), 2):
res.extend([nums[i]] * nums[i - 1])
return res
The provided example demonstrates how the solution method applies to a specific instance, reflecting the simplicity and effectiveness of the approach for decompressing a run-length encoded list.
Solution Implementation
1from typing import List
2
3class Solution:
4 def decompressRLElist(self, nums: List[int]) -> List[int]:
5 # Initialize the resulting decompressed list
6 decompressed_list = []
7
8 # Iterate over the list 'nums' step by 2, starting from the second item
9 for i in range(1, len(nums), 2):
10 # For each pair, extend the decompressed list with 'freq' times of 'val'
11 # where 'freq' is the frequency (previous element) and 'val' is the value (current element)
12 freq = nums[i - 1] # Frequency of the current element
13 val = nums[i] # The value to be repeated
14 decompressed_list.extend([val] * freq)
15
16 # Return the decompressed list after processing all pairs
17 return decompressed_list
18
1class Solution {
2 // The decompressRLElist method takes in an array of integers as input where consecutive pair elements
3 // represent (frequency, value) and decompresses the list based on these.
4 public int[] decompressRLElist(int[] nums) {
5 // Initialize variable to track the size of the decompressed list.
6 int decompressedLength = 0;
7
8 // Calculate the length of the decompressed list.
9 for (int i = 0; i < nums.length; i += 2) {
10 decompressedLength += nums[i];
11 }
12
13 // Initialize the result array with the calculated length.
14 int[] decompressedArray = new int[decompressedLength];
15
16 // Index for inserting elements into the decompressedArray.
17 int insertPosition = 0;
18
19 // Loop through the nums array in steps of 2 to decompress.
20 for (int i = 1; i < nums.length; i += 2) {
21 // Decompress the current pair.
22 // nums[i - 1] is the frequency and nums[i] is the value to be repeated.
23 for (int j = 0; j < nums[i - 1]; ++j) {
24 // Insert the value into decompressedArray and increment the insert position.
25 decompressedArray[insertPosition++] = nums[i];
26 }
27 }
28
29 // Return the decompressed array.
30 return decompressedArray;
31 }
32}
33
1#include <vector> // Include the vector header for std::vector
2
3// Class name 'Solution' with a single public member function.
4class Solution {
5public:
6 // Function to decompress a run-length encoded list.
7 // Takes a reference to a vector of integers as an argument,
8 // and returns a vector of integers.
9 vector<int> decompressRLElist(vector<int>& nums) {
10 vector<int> decompressedList; // Create a vector to store decompressed elements
11
12 // Iterate over the input vector, stepping by 2, since the list is in (freq, val) pairs
13 for (int i = 1; i < nums.size(); i += 2) {
14 // For each pair, replicate the value 'nums[i]' according to the frequency 'nums[i - 1]'
15 for (int freq = 0; freq < nums[i - 1]; ++freq) {
16 decompressedList.push_back(nums[i]); // Add the value to the decompressed list
17 }
18 }
19
20 return decompressedList; // Finally, return the decompressed vector
21 }
22};
23
1function decompressRLElist(nums: number[]): number[] {
2 // 'halfLength' calculates half the length of the input array.
3 // It is used because each pair (freq, val) takes two places in the array.
4 let halfLength = nums.length >> 1;
5 let decompressedList = [];
6
7 // Loop through the input array in steps of two to process the pairs
8 for (let i = 0; i < halfLength; i++) {
9 // Get the frequency and value out of the 'nums' array
10 let frequency = nums[2 * i],
11 value = nums[2 * i + 1];
12
13 // Create an array with 'frequency' number of 'value' elements and concatenate it to 'decompressedList'
14 decompressedList.push(...new Array(frequency).fill(value));
15 }
16
17 // Return the decompressed result as an array
18 return decompressedList;
19}
20
Time and Space Complexity
Time Complexity
The time complexity is O(n)
, where n
is the total number of elements in the input list nums
. This is because the loop iterates through every other element of nums
, performing a constant amount of work for each pair of freq-value (since the .extend()
method is called once per pair), and the number of pairs is n/2
.
Space Complexity
The space complexity is also O(n)
, but here n
represents the total number of elements in the decompressed list res
. Although the input list size is halved due to the pairs, the decompression may lead to a larger output. In the worst case, all the freq-values are large, causing the output list size to be significantly larger than the size of the input list.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!