Product of Two Run-Length Encoded Arrays - Practice Coding Problems

Product of Two Run-Length Encoded Arrays - Problem

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] = [val_i, freq_i] describes the i^th segment of repeated numbers in nums where val_i is the value that is repeated freq_i 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:

Expand both encoded1 and encoded2 into the full arrays nums1 and nums2 respectively.
Create a new array prodNums of length nums1.length and set prodNums[i] = nums1[i] * nums2[i].
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] = [val_i, freq_i] describes the i^th segment of nums1, and each encoded2[j] = [val_j, freq_j] describes the j^th 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.

Input & Output

Example 1 — Basic Case

$ Input: encoded1 = [[1,3],[2,2]], encoded2 = [[6,2],[3,3]]

› Output: [[6,2],[6,1],[6,2]]

💡 Note: Expanded arrays are [1,1,1,2,2] and [6,6,3,3,3]. Products: [6,6,3,6,6]. Compressed: [[6,2],[3,1],[6,2]]

Example 2 — Single Segments

$ Input: encoded1 = [[1,2]], encoded2 = [[4,2]]

› Output: [[4,2]]

💡 Note: Both arrays have single segments. Products: [1×4, 1×4] = [4,4]. Compressed: [[4,2]]

Example 3 — Different Lengths

$ Input: encoded1 = [[2,1],[3,1],[4,1]], encoded2 = [[5,3]]

› Output: [[10,1],[15,1],[20,1]]

💡 Note: First array [2,3,4], second array [5,5,5]. Products: [10,15,20]. All different, so [[10,1],[15,1],[20,1]]

Constraints

1 ≤ encoded1.length, encoded2.length ≤ 10⁵
encoded1[i].length == 2
1 ≤ encoded1[i][1], encoded2[i][1] ≤ 10⁴
-10⁵ ≤ encoded1[i][0], encoded2[i][0] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Two run-length encoded arrays representing compressed sequences

Process

Multiply corresponding elements without full expansion

Output

Return compressed product array

Key Takeaway

🎯 Key Insight: Use two pointers to process overlapping segments without expanding the full arrays

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is to use two pointers to process both run-length encoded arrays simultaneously without expanding them fully. Instead of creating the full arrays (which uses O(n) space), we can process overlapping segments directly and build the result on-the-fly. Best approach is Two Pointers with Time: O(m+n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Direct Processing	O(m + n)	O(1)	Use two pointers to process both arrays simultaneously without full expansion
Brute Force - Full Expansion	O(n)	O(n)	Expand both arrays completely, multiply elements, then compress result

Two Pointers - Direct Processing — Algorithm Steps

Step 1: Initialize pointers i, j for both arrays and position counters
Step 2: Find overlap between current segments from both arrays
Step 3: Calculate product and determine frequency for this overlap
Step 4: Add to result if product differs from last segment
Step 5: Advance pointers when segments are fully consumed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Set pointers to first segments of both arrays

Process Overlap

Find intersection of current segments and compute product

Advance Pointers

Move pointers when segments are consumed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int** encoded1, int encoded1Size, int* encoded1ColSize, int** encoded2, int encoded2Size, int* encoded2ColSize, int* returnSize, int** returnColumnSizes) {
    int maxResultSize = encoded1Size + encoded2Size;
    int** result = (int**)malloc(maxResultSize * sizeof(int*));
    *returnColumnSizes = (int*)malloc(maxResultSize * sizeof(int));
    
    int resultIdx = 0;
    int i = 0, j = 0; // Pointers for encoded1 and encoded2
    int pos1 = 0, pos2 = 0; // Current positions within segments
    
    while (i < encoded1Size && j < encoded2Size) {
        int val1 = encoded1[i][0], freq1 = encoded1[i][1];
        int val2 = encoded2[j][0], freq2 = encoded2[j][1];
        
        // Calculate product
        int product = val1 * val2;
        
        // Find how many elements we can process from current segments
        int remaining1 = freq1 - pos1;
        int remaining2 = freq2 - pos2;
        int count = (remaining1 < remaining2) ? remaining1 : remaining2;
        
        // Add to result if it's different from the last segment
        if (resultIdx == 0 || result[resultIdx-1][0] != product) {
            result[resultIdx] = (int*)malloc(2 * sizeof(int));
            result[resultIdx][0] = product;
            result[resultIdx][1] = count;
            (*returnColumnSizes)[resultIdx] = 2;
            resultIdx++;
        } else {
            result[resultIdx-1][1] += count;
        }
        
        // Update positions
        pos1 += count;
        pos2 += count;
        
        // Move to next segment if current one is exhausted
        if (pos1 == freq1) {
            i++;
            pos1 = 0;
        }
        if (pos2 == freq2) {
            j++;
            pos2 = 0;
        }
    }
    
    *returnSize = resultIdx;
    return result;
}

int main() {
    printf("[[6,1],[7,1],[8,1]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

Single pass through both encoded arrays where m and n are lengths of encoded arrays

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for pointers and current segment tracking

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Direct Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler