Welcome Reader!
In the last blog, we discussed the problem of Running Sum From An Array. In this article, we will discuss the next problem based on “Arrays,” i.e., “Decompress Run-Length Encoded List” Before you move any further, it is advised that you give this problem a fair try. Let’s understand the problem.
Important Link: Problem Link
Problem Statement
We are given a list nums
of integers representing a list compressed with run-length encoding. Consider each adjacent pair of elements [freq, val] = [nums[2*i], nums[2*i+1]]
(with i >= 0
). For each such pair, there are freq
elements with value val
concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.
Return the decompressed list.
Constraints:
2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100
For example:
Input: nums = [1,2,3,4]
Output: [2,4,4,4]
Explanation
nums=[1,2,3,4]
Initially, ans array is empty.
ans = [ ]
First Iteration:
freq = nums[2*0] i.e nums[0]
val = nums[2*0+1] i.e nums[1]
nums = [1 , 2 , 3 , 4]
// while freq - -
// add val = 2 to ans array
ans array after first iteraton :
ans=[ 2 ]
Second iteration:
freq = nums[2*1] i.e nums[2]
val = nums[2*1+1] i.e nums[3]
nums = [1 , 2 , 3 , 4]
// while freq - -
// add val = 4 to ans array
ans array after second iteration :
ans = [ 2 , 4 , 4 ,4 ]
Therefore we notice that we are processing an array in a block size of 2. Every time changing values for freq and val.
Then for every block, we insert the val into our answer array until we exhaust freq.
After we finish processing our entire array, we return the result.
Solution
Edge Case Analysis :
The constraints mention that 2 <= nums.length <= 100 and nums.length % 2 == 0. It means there will be at least 2 elements in nums, and the length of nums is even therefore, we can always form a block of 2 and increment the outer loop by 2.
Complexities:
Time Complexity: O(N^2)
outer loop incrementing by constant +=2, therefore O(N).
Inside we are performing operations O(N) times.
therefore O(N) *O(N)
Space Complexity: O(1) + O(N)
We only created an array for storing our answer therefore O(N). And our algorithm takes O(1) space.
Congratulations, we just solved one more interesting problem.
We hope that this article was helpful. You can contact us via our website. Doubts, suggestions, and feedback are always welcomed. You are also advised to follow the sequence of modules and questions on our website. Keep practicing more and more problems daily. Meditate enough on each step of each problem.
Regards,
The Daily Code Team