algoadvance

Leetcode 1313. Decompress Run

Problem Statement

1. Decompress Run-Length Encoded List

We are given a run-length encoded list nums. 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

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

Constraints

• 2 <= nums.length <= 100
• nums.length % 2 == 0
• 1 <= nums[i] <= 100

Clarifying Questions

1. Input type:
   • Are nums always positive integers?
     • Yes, based on the constraints 1 <= nums[i] <= 100.
2. Output type:
   • Should the output be a list of integers?
     • Yes, it should be a list of integers, where each integer appears its respective frequency number of times.

Strategy

1. Iterate over the list nums:
   • The length of nums is always even, and we will iterate through pairs of elements.
2. Decompose each pair:
   • For each pair [freq, val], generate a sublist containing freq instances of val.
3. Concatenate all sublists:
   • Collect all these generated lists into a single result list.

Code

Here is the Java implementation for the problem:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] decompressRLElist(int[] nums) {
        List<Integer> result = new ArrayList<>();
        
        // Iterate over the pairs in the input array
        for (int i = 0; i < nums.length; i += 2) {
            int freq = nums[i];
            int val = nums[i+1];
            
            // Add 'val' to the result 'freq' times
            for (int j = 0; j < freq; j++) {
                result.add(val);
            }
        }
        
        // Convert the list to an array
        int[] decompressedList = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            decompressedList[i] = result.get(i);
        }
        
        return decompressedList;
    }
}

Time Complexity

• Time Complexity: O(n)
  • We iterate over the input array nums of length n once.
  • For each pair, we generate exactly freq number of elements, ensuring linear traversal of the list input.
• Space Complexity: O(m)
  • The space complexity is proportional to the output list size m, which is the total number of elements generated from the run-length encoded list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?