LeetCode Challenge #6: Decompress Run-Length Encoded List

Subscribe to my newsletter and never miss my upcoming articles

Writer's note: Found this draft sitting too long in Drafts. Lost the timing to publish in May so backdated it to May but published in July.

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.

Example 1:

Input: nums = [1,2,3,4]
Output: [2,4,4,4]
Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2].
The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4].
At the end the concatenation [2] + [4,4,4] is [2,4,4,4].

Example 2:

Input: nums = [1,1,2,3]
Output: [1,3,3]

Step-by-Step Solution

Identify Patterns After reading the problem and examples, we can observe 3 things:

  1. The problem output is an array.
  2. The length of the array will be the sum of the frequencies.
  3. The nums array is in the pattern [freq, val, freq, val, freq, val...].

Write the Pseudocode So let's try writing a solution for this problem without code:

  1. Initialize the frequency as 0.
  2. Loop through the array, and increase the index by 2 each time instead of 1 to count the total number of frequency.
  3. Initialize an output array and set the size to the sum of frequencies.
  4. Loop through the nums array again but this time, start at index = 1 then increase by 2 to get the values.
  5. Have an inner for loop to get the frequencies and add the value to the output array by the number of the frequency.

Let's get coding! Now, we can write the Java code as follows:

class Solution {
    public int[] decompressRLElist(int[] nums) {

        //Initialize frequency
        int freq = 0;
        for(int i=0; i<nums.length; i+=2){
            freq += nums[i];
        }

        int output[] = new int[freq]; //necessary size

        //now add the values into the array
        int currentIndex = 0;
        for(int i=1; i<nums.length; i+=2){ //get the value
            for(int j=0; j<nums[i-1]; j++){ // add it the number of times as the freq
                output[currentIndex]=nums[i];
                currentIndex++;
            }
        }

        return output;
    }
}

Conclusion

This question may be a little tricky if you did not observe to calculate the total sum of frequencies to initialize the output array. Arrays in Java are not resizeable so it is important to know what size it is when initializing it. Once you get to that step, everything else should be straightforward if you are used to the double looping. Also, don't forget currentIndex is used to track the current index of the output array to add a value to. This was a fun problem! Hope it is for you too!

P.S. This is the end of the LeetCode series in Java. I'll probably do JavaScript next.

No Comments Yet