algoadvance

Leetcode 1313. Decompress Run

Problem Statement

Given a list nums of integers, where nums[i] for all i is part of a run-length encoded list. For example, consider the list [freq1, val1, freq2, val2, ...] where each pair (frequencyn, valuen) means that val appears freq times. Construct and return the decompressed list.

Clarifying Questions

1. Input Constraints: Is the length of nums guaranteed to be even?
   • Yes, the length of nums is guaranteed to be even.
2. Value Constraints: Can the values in nums be negative or zero?
   • The frequencies (freq) will always be positive integers, but the values (val) can be any integers.

Strategy

1. Initialize an empty result list.
2. Loop through the nums list in steps of 2, treating each pair of elements as (freq, val).
3. For each pair, append val to the result list freq times.
4. Return the result list.

Code

#include <iostream>
#include <vector>

std::vector<int> decompressRLElist(std::vector<int>& nums) {
    std::vector<int> result;
    for (size_t i = 0; i < nums.size(); i += 2) {
        int freq = nums[i];
        int val = nums[i + 1];
        for (int j = 0; j < freq; ++j) {
            result.push_back(val);
        }
    }
    return result;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4};
    std::vector<int> decompressedList = decompressRLElist(nums);

    for (int num : decompressedList) {
        std::cout << num << " ";
    }

    return 0;
}

Time Complexity

• Time Complexity: The time complexity is O(n * f), where n is the number of pairs (i.e., nums.size() / 2), and f is the average frequency of the values. The worst case occurs when the frequencies are large, causing many insertions into the result list.
• Space Complexity: The space complexity is O(m), where m is the total number of elements in the decompressed list. This includes the space required for the result 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?