1868. Product of Two Run-Length Encoded Arrays

MediumArrayTwo Pointers
Leetcode Link

Problem Description

The problem provides us with a compression technique called "run-length encoding". This technique compresses an array of integers by representing segments of consecutive repeated numbers as a 2D array. Each entry in the encoded array has two elements: the value being repeated and the frequency of that value.

For example, nums = [1,1,1,2,2,2,2,2] is encoded as encoded = [[1,3],[2,5]], meaning that the number 1 is repeated 3 times followed by number 2 which is repeated 5 times.

The task is to calculate the product of two run-length encoded arrays, encoded1 and encoded2. To find the product, we need to:

  1. Expand encoded1 and encoded2 back into the original full arrays (nums1 and nums2).
  2. Multiply the corresponding elements of nums1 and nums2 to form a new array prodNums.
  3. Compress prodNums back into run-length encoded format.

We need to ensure that the final encoded product array is as short as possible.

Intuition

The intuition behind the solution is to simulate the product of the two arrays without fully expanding them. This is important for efficiency, especially when the encoded arrays represent very long sequences.

By iterating through the segments of the first array, we:

  • Keep track of how many times we have used the value in the current segment.
  • Determine the product with the corresponding part of the second encoded array.
  • Update the result by either adding a new segment or extending the last segment if the product value is the same.
  • Keep track of the portion of the segment of the second array that has been consumed and move to the next segment once we have used it up.

We use the minimum frequency from the current segments of encoded1 and encoded2 to decide how to extend or create the new segments in the resulting array. This way, we simulate the expansion and multiplication steps by directly compressing the product. We avoid unnecessary computation and achieve the efficient calculation of the run-length encoded product.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The implementation of the solution is straightforward in logic but requires careful handling of the indices and frequencies from the encoded arrays. Here's a step-by-step breakdown of how the solution works:

  1. Initialize an empty list ans, which will store our result in run-length encoded format.
  2. Initialize a variable j to keep track of our position in encoded2 while we iterate through encoded1.
  3. Loop through each segment [val_i, freq_i] of encoded1. For each segment, we do the following:
    • While freq_i is greater than zero:
      • We take the minimum of freq_i and the frequency of the current segment in encoded2 (i.e., encoded2[j][1]). This decides how much of the segment we can use in this step of the product.
      • Calculate the product v of val_i and the value of the current segment in encoded2 (i.e., encoded2[j][0]).
      • Check if the last segment in ans has the same value as v. If so, increase the frequency of that segment by the frequency we are currently using f. This step ensures we are compressing the result as we go.
      • If the last segment in ans has a different value, append a new segment [v, f] to ans.
      • Decrease freq_i by f to keep track of the remaining frequency that needs to be accounted for from the current segment in encoded1.
      • Decrease the frequency of the current segment in encoded2 by f as we have used up f frequency of it.
      • If the current segment in encoded2 is fully used (frequency becomes zero), move to the next segment in encoded2 by incrementing j.

By following these steps, the while loop effectively takes care of creating the product without ever needing to fully expand the encoded arrays. Once we've finished processing all segments in encoded1, we're left with ans which contains our compressed product.

This approach uses a single pass and keeps space complexity low, as we never create the fully expanded arrays. It combines elements of two-pointers technique—i iterating over encoded1 and j keeping track of our place in encoded2—with a merge-like operation where we merge contributions from corresponding segments.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have two run-length encoded arrays:

encoded1 = [[2,3],[3,2]] and encoded2 = [[6,1],[3,3],[9,1]]

The first array encoded1 can be expanded to [2,2,2,3,3] and the second array encoded2 to [6,3,3,3,9]. We are to find the product of these two arrays and then compress it back to run-length encoding format. Let's follow the steps in the solution approach.

  1. Initialize ans = [], an empty list to hold the result.

  2. Initialize j = 0, a variable to keep track of our position in encoded2.

  3. Begin looping over encoded1. Our first segment is [2,3] indicating three 2s.

    • While freq_i (3 for the first segment of encoded1) is greater than zero:
      • The first segment of encoded2 has only one element left, so we take the minimum of freq_i and encoded2[j][1], which is min(3, 1) = 1.
      • The product v of values 2 (val_i) and 6 (encoded2[j][0]) is 12.
      • ans = [] is currently empty, so we append [12, 1] to ans.
      • We decrease freq_i by 1, now freq_i is 2.
      • We also decrease encoded2[j][1] by 1, and since it would now be 0, we move to the next segment by incrementing j (now j=1 and segment [3,3] of encoded2 is the current).

  4. We continue the while loop because freq_i is still greater than zero:

    • Now we have freq_i = 2 and the frequency of the current segment in encoded2[j][1] is 3.
    • We take the minimum, which is 2.
    • The next product v of values 2 and 3 is 6.
    • ans = [[12, 1]], and as 6 is different from 12, we append [6, 2] to ans.
    • Both freq_i and encoded2[j][1] are decreased by 2, resulting in freq_i = 0 and encoded2[j][1] = 1.

  5. Since freq_i is zero, we move to the next segment of encoded1.

  6. The next segment is [3,2]. We repeat a similar process here:

    • We have freq_i = 2 and encoded2[j][1] is 1 (from the remaining part of the previous segment [3,1]).
    • We take the minimum, which is 1.
    • The product of values 3 and 3 is 9.
    • Since the last value in ans is 6, we add a new segment [9, 1] to ans.
    • Decrease freq_i to 1 and since encoded2[j][1] is now 0, we increase j to 2 (next segment [9,1] of encoded2).

  7. We continue in the loop with the remaining freq_i = 1 for value 3 in encoded1:

    • We have freq_i = 1 and encoded2[j][1] is also 1.
    • The product of values 3 and 9 is 27.
    • As 27 is different from the last value in ans, we add another segment [27, 1] to ans.
    • Both freq_i and encoded2[j][1] are decreased to 0.

Finally, we're finished processing all segments in encoded1 and encoded2, resulting in ans = [[12, 1], [6, 2], [9, 1], [27, 1]] which is the run-length encoded product of nums1 and nums2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findRLEArray(
5        self, encoded1: List[List[int]], encoded2: List[List[int]]
6    ) -> List[List[int]]:
7        # Initialize an empty list to store the resulting encoded RLE array
8        result = []
9      
10        # Initialize an index to track the position in encoded2
11        index_encoded2 = 0
12      
13        # Iterate through each pair (value, frequency) in the first encoded array
14        for value1, frequency1 in encoded1:
15          
16            # Process the current range until its frequency becomes zero
17            while frequency1:
18                # Determine the minimum frequency to merge from both arrays
19                min_frequency = min(frequency1, encoded2[index_encoded2][1])
20              
21                # Compute the product of the values
22                product_value = value1 * encoded2[index_encoded2][0]
23              
24                # If the last pair in the result has the same value, merge them by adding the frequencies
25                if result and result[-1][0] == product_value:
26                    result[-1][1] += min_frequency
27                else:
28                    # Otherwise, append a new pair of product value and frequency
29                    result.append([product_value, min_frequency])
30              
31                # Update the frequencies in both arrays
32                frequency1 -= min_frequency
33                encoded2[index_encoded2][1] -= min_frequency
34              
35                # If the current range in encoded2 is exhausted, move to the next one
36                if encoded2[index_encoded2][1] == 0:
37                    index_encoded2 += 1
38      
39        # Once done processing, return the resulting array
40        return result
41
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6
7    public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
8        // Initialize the answer list to hold the product RLE
9        List<List<Integer>> result = new ArrayList<>();
10        // Index for tracking the current position in encoded2
11        int currentIndex = 0;
12
13        // Iterate over each pair in encoded1
14        for (int[] pairEncoded1 : encoded1) {
15            // Grab the value and frequency from the current pair in encoded1
16            int value1 = pairEncoded1[0];
17            int frequency1 = pairEncoded1[1];
18
19            // Continue until we have processed all of this value
20            while (frequency1 > 0) {
21                // Find the frequency to be processed which is the minimum of the
22                // remaining frequency from encoded1 and the current frequency from encoded2
23                int minFrequency = Math.min(frequency1, encoded2[currentIndex][1]);
24                // Multiply the values from encoded1 and encoded2
25                int product = value1 * encoded2[currentIndex][0];
26              
27                // Check if the last element in the result list has the same value
28                int resultSize = result.size();
29                if (resultSize > 0 && result.get(resultSize - 1).get(0) == product) {
30                    // If yes, add the minFrequency to the frequency of the last element
31                    int currentFreq = result.get(resultSize - 1).get(1);
32                    result.get(resultSize - 1).set(1, currentFreq + minFrequency);
33                } else {
34                    // If not, add a new pair with the product and minFrequency
35                    result.add(new ArrayList<>(Arrays.asList(product, minFrequency)));
36                }
37                // Decrease the respective frequencies
38                frequency1 -= minFrequency;
39                encoded2[currentIndex][1] -= minFrequency;
40
41                // If we have processed all frequencies of the current pair in encoded2,
42                // move to the next pair
43                if (encoded2[currentIndex][1] == 0) {
44                    currentIndex++;
45                }
46            }
47        }
48        return result;
49    }
50}
51
1class Solution {
2public:
3    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
4        vector<vector<int>> result; // This will store the final Run Length Encoded product of encoded1 and encoded2
5
6        int indexInEncoded2 = 0; // Index for tracking position in encoded2
7
8        // We iterate through each element-pair in encoded1
9        for (const auto& pairInEncoded1 : encoded1) {
10            int valueInEncoded1 = pairInEncoded1[0], // Current value from encoded1
11                frequencyInEncoded1 = pairInEncoded1[1]; // Current frequency of this value in encoded1
12
13            // While we have not accounted for all instances of this particular value
14            while (frequencyInEncoded1 > 0) {
15              
16                // Compute minimum frequency to consider from both encoded1 and encoded2
17                int frequencyToProcess = min(frequencyInEncoded1, encoded2[indexInEncoded2][1]);
18              
19                // Compute the product of the values from encoded1 and encoded2
20                int productValue = valueInEncoded1 * encoded2[indexInEncoded2][0];
21              
22                // If this value was already the last value we processed, we just update its frequency
23                if (!result.empty() && result.back()[0] == productValue) {
24                    result.back()[1] += frequencyToProcess;
25                } else {
26                    // Otherwise, we add a new pair {product value, frequency} to our result
27                    result.push_back({productValue, frequencyToProcess});
28                }
29
30                // Decrease the frequencies in encoded1 and encoded2 by the frequency we have just processed
31                frequencyInEncoded1 -= frequencyToProcess;
32                encoded2[indexInEncoded2][1] -= frequencyToProcess;
33
34                // If we've used up all instances of the current value in encoded2, move to the next pair
35                if (encoded2[indexInEncoded2][1] == 0) {
36                    ++indexInEncoded2;
37                }
38            }
39        }
40
41        return result; // Return the final product after Run Length Encoding
42    }
43};
44
1// Define the type for the encoded arrays to increase code readability.
2type EncodedArray = Array<[number, number]>;
3
4// Given two run-length encoded arrays encoded1 and encoded2, this function will
5// calculate the run-length encoded product of the two arrays.
6function findRLEArray(encoded1: EncodedArray, encoded2: EncodedArray): EncodedArray {
7    let result: EncodedArray = []; // This will store the final RLE product of encoded1 and encoded2.
8
9    let indexInEncoded2 = 0; // Index for tracking position in encoded2.
10
11    // Iterate through each value-frequency pair in encoded1.
12    for (const [valueInEncoded1, originalFrequencyInEncoded1] of encoded1) {
13        let frequencyInEncoded1 = originalFrequencyInEncoded1; // Current frequency of this value in encoded1.
14
15        // While we have not processed all instances of this particular value
16        while (frequencyInEncoded1 > 0) {
17          
18            // Compute minimum frequency to consider from both encoded1 and encoded2.
19            let frequencyToProcess = Math.min(frequencyInEncoded1, encoded2[indexInEncoded2][1]);
20          
21            // Compute the product of the values from encoded1 and encoded2.
22            let productValue = valueInEncoded1 * encoded2[indexInEncoded2][0];
23          
24            // If this value was already the last value we processed, we just update its frequency.
25            if (result.length > 0 && result[result.length - 1][0] === productValue) {
26                result[result.length - 1][1] += frequencyToProcess;
27            } else {
28                // Otherwise, we add a new pair [product value, frequency] to our result.
29                result.push([productValue, frequencyToProcess]);
30            }
31
32            // Decrease the frequencies in encoded1 and encoded2 by the frequency we have just processed.
33            frequencyInEncoded1 -= frequencyToProcess;
34            encoded2[indexInEncoded2][1] -= frequencyToProcess;
35
36            // If we've used up all instances of the current value in encoded2, move to the next pair.
37            if (encoded2[indexInEncoded2][1] === 0) {
38                indexInEncoded2++;
39            }
40        }
41    }
42
43    return result; // Return the final RLE product.
44}
45
46// You can then use the findRLEArray function with two run-length encoded arrays.
47// For example: findRLEArray([[1,4], [2,3]], [[3,4], [5,2]]);
48
Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Time and Space Complexity

Time Complexity

The time complexity of the given code primarily depends on these factors:

  1. Iterating through encoded1, which has n elements: O(n).
  2. A nested loop for processing elements in encoded2, which can be iterated up to m times in the worst case (in case the sizes in encoded1 are much larger): O(m).

However, since the second loop decreases the frequency from encoded2 without resetting, each element of encoded2 will be processed at most once throughout the entire iteration of encoded1. Therefore, the total time complexity will be O(n + m) where n is the total number of elements in encoded1 and m is the total number of elements in encoded2.

Space Complexity

The space complexity is determined by the size of the output, which in the worst case might contain an individual element for each multiplication of pairs from encoded1 and encoded2. In the worst case, every pair multiplication might result in a distinct value not matching the last element of the ans list, thus:

  1. The ans list: Up to O(n + m) in the worst case.
  2. Constant space for the pointers and temporary variables like vi, fi, f, v, j.

Therefore, the total space complexity of the given code would be O(n + m).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫