Skip to main content
Talentd

Product of Two Run-Length Encoded Arrays - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo Pointers6 min readAsked at: Meta, Yandex
Practice this problem

Problem Statement

Run-length encoding is a compression algorithm that allows for an integer array nums with many segments of consecutive repeated numbers to be represented by a (generally smaller) 2D array encoded. Each encoded[i] = [vali, freqi] describes the ith segment of repeated numbers in nums where vali is the value that is repeated freqi times.

  • For example, nums = [1,1,1,2,2,2,2,2] is represented by the run-length encoded array encoded = [[1,3],[2,5]]. Another way to read this is "three 1's followed by five 2's".

The product of two run-length encoded arrays encoded1 and encoded2 can be calculated using the following steps:

  1. Expand both encoded1 and encoded2 into the full arrays nums1 and nums2 respectively.
  2. Create a new array prodNums of length nums1.length and set prodNums[i] = nums1[i] * nums2[i].
  3. Compress prodNums into a run-length encoded array and return it.

You are given two run-length encoded arrays encoded1 and encoded2 representing full arrays nums1 and nums2 respectively. Both nums1 and nums2 have the same length. Each encoded1[i] = [vali, freqi] describes the ith segment of nums1, and each encoded2[j] = [valj, freqj] describes the jth segment of nums2.

Return the product of encoded1 and encoded2.

Note: Compression should be done such that the run-length encoded array has the minimum possible length.

 

Example 1:

Input: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]]
Output: [[6,6]]
Explanation: encoded1 expands to [1,1,1,2,2,2] and encoded2 expands to [6,6,6,3,3,3].
prodNums = [6,6,6,6,6,6], which is compressed into the run-length encoded array [[6,6]].

Example 2:

Input: encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]]
Output: [[2,3],[6,1],[9,2]]
Explanation: encoded1 expands to [1,1,1,2,3,3] and encoded2 expands to [2,2,2,3,3,3].
prodNums = [2,2,2,6,9,9], which is compressed into the run-length encoded array [[2,3],[6,1],[9,2]].

 

Constraints:

  • 1 <= encoded1.length, encoded2.length <= 105
  • encoded1[i].length == 2
  • encoded2[j].length == 2
  • 1 <= vali, freqi <= 104 for each encoded1[i].
  • 1 <= valj, freqj <= 104 for each encoded2[j].
  • The full arrays that encoded1 and encoded2 represent are the same length.

Approach Overview

Problem Overview: You are given two arrays encoded using run-length encoding (RLE). Each element is stored as [value, frequency], meaning the value repeats multiple times. The task is to compute the element-wise product of the fully expanded arrays and return the result in run-length encoded form.

Approach 1: Decompress Then Multiply (Brute Force) (Time: O(N + M), Space: O(N + M))

The most straightforward idea is to fully expand both encoded arrays into their original forms. Iterate through each [value, frequency] pair and append the value frequency times into a new array. Once both arrays are decompressed, compute the element-wise product and then run-length encode the result again by grouping consecutive identical values.

This method works but defeats the purpose of run-length encoding. If frequencies are large, the decompressed arrays can be huge, causing unnecessary memory usage. The approach mainly helps verify correctness before implementing the optimal solution.

Approach 2: Two Pointers on Encoded Segments (Optimal) (Time: O(n + m), Space: O(1) excluding output)

The key insight is that you never need to decompress the arrays. Each encoded pair represents a contiguous segment of identical values. Instead of expanding them, process segments directly using a two pointers technique.

Maintain one pointer for each encoded array. At every step, multiply the current values from both segments. The number of elements contributing to the product is the minimum of their remaining frequencies. Append a new segment [product, minFreq] to the result.

After producing this segment, reduce the frequency of both segments by minFreq. If one segment is exhausted, move its pointer to the next pair. Continue until one array is fully processed. While appending to the result, merge with the previous segment if the product value is the same to keep the output properly run-length encoded.

This approach processes each encoded segment once. No large intermediate arrays are created, which keeps memory usage minimal. The pattern is similar to merging intervals or scanning sorted lists and commonly appears in problems involving compressed data structures or array segment processing.

Recommended for interviews: Interviewers expect the two-pointer segment processing approach. It shows you recognize that decompression is unnecessary and can operate directly on encoded data. Mentioning the brute force idea first demonstrates understanding of the problem, but implementing the optimal two pointers solution shows strong algorithmic judgment and efficiency awareness.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Decompress Then MultiplyO(N + M)O(N + M)Useful for understanding the problem or when input sizes are small.
Two Pointers on Encoded SegmentsO(n + m)O(1)Optimal approach. Works directly on run-length encoded segments without decompression.

Video Solution

PRODUCT OF TWO RUN-LENGTH ENCODED ARRAYS | PYTHON | LEETCODE # 1868 • Cracking FAANG • 5,057 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Product of Two Run-Length Encoded Arrays easy or hard?
The problem is rated Medium on LeetCode. The main challenge is recognizing that decompression is unnecessary and designing a two-pointer algorithm that operates directly on encoded segments.
Product of Two Run-Length Encoded Arrays Python/Java solution
Most implementations iterate through both encoded arrays using two indices. At each step, compute the product of the values, append the segment with the minimum frequency, update counts, and merge adjacent segments with the same product. The logic translates directly to Python, Java, C++, and Go.
How to solve Product of Two Run-Length Encoded Arrays in O(n + m)?
Maintain two pointers, one for each encoded array. Multiply the current values and take the minimum of their frequencies to determine the segment length for the product. Reduce the frequencies accordingly and move pointers when a segment is exhausted while merging consecutive identical product values in the output.
What is the best approach for Product of Two Run-Length Encoded Arrays?
The best approach uses two pointers that traverse both run-length encoded arrays simultaneously. Instead of decompressing the arrays, you multiply segment values and use the minimum frequency to determine how many elements contribute to the product. This keeps the algorithm efficient with O(n + m) time and O(1) extra space.
Is Product of Two Run-Length Encoded Arrays asked at Google/Amazon/Meta?
Problems involving run-length encoding and two-pointer segment processing appear in interviews at companies like Google, Amazon, and Meta. They test the ability to work with compressed data representations and avoid unnecessary expansion of large datasets.
What data structure is used in Product of Two Run-Length Encoded Arrays?
The problem primarily uses arrays combined with the two pointers technique. Each input array stores run-length encoded pairs, and pointers track the current segment being processed while building the encoded result.
What is the time complexity of Product of Two Run-Length Encoded Arrays?
The optimal solution runs in O(n + m) time where n and m are the number of encoded segments in the two arrays. Each segment is processed once using two pointers. Space complexity is O(1) excluding the output array.

Ready to solve this problem?

Practice Product of Two Run-Length Encoded Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays