Decompress Run-Length Encoded List

Decompress Run-Length Encoded List

What is this problem about?

The Decompress Run-Length Encoded List interview question is a straightforward array manipulation task. You are given an array nums where elements come in pairs: [freq, val]. For every pair, you need to generate freq occurrences of the value val and concatenate them into a single result array. This Decompress Run-Length Encoded List coding problem is a test of basic loop control and list building.

Why is this asked in interviews?

Google and Amazon use this "Easy" level question to check for basic programming literacy. It evaluates if a candidate can handle simple indexing (iterating in steps of 2) and if they know how to efficiently extend or append to a dynamic array in their language of choice. It’s a common "warm-up" task to get the candidate comfortable.

Algorithmic pattern used

This follows the Array interview pattern.

1. Iterate through the array with a step of 2 (i = 0, 2, 4...).
2. Identify freq = nums[i] and val = nums[i+1].
3. Use a nested loop (or a library function like Collections.nCopies) to add the value to your result list multiple times.

Example explanation

Input: [1, 2, 3, 4]

1. Pair 1: freq = 1, val = 2. Result: [2].
2. Pair 2: freq = 3, val = 4. Result: [2, 4, 4, 4]. Final Result: [2, 4, 4, 4].

Common mistakes candidates make

• Step Size: Forgetting to increment the loop counter by 2, leading to incorrect frequency/value pairs.
• In-place allocation: Not realizing that the final size of the array is known (sum of all nums[even_indices]). In languages like Java or C++, pre-allocating the array can be a slight performance win.
• Logic swap: Accidentally using the value as the frequency and the frequency as the value.

Interview preparation tip

Even for simple problems, mention performance. For example, explain that while list.add() is fine, pre-calculating the final array size avoids redundant memory reallocations as the list grows.