⚡Flashcard Drill➔
NeetCode #215LC-1868MediumTwo Pointers
← Back to All Problems

#215 · #1868 · Product of Two Run-Length Encoded Arrays(两个行程编码数组的积)

📌 Problem Statement & Constraints

Two run-length encoded arrays encoded1 and encoded2 represent arrays of the same length, each entry [value, frequency]. Return the run-length encoded product of the two arrays, merging adjacent runs with equal values. Constraints: 1 <= encoded1.length, encoded2.length <= 10^4, total decoded length at most 10^5.

💡 Core Algorithmic Approaches

  1. Walk both encodings with two pointers and two remaining-count variables.
  2. At each step, the product of the current values applies to min(rem1, rem2) positions.
  3. Append the run, merging with the previous entry when the product equals the last stored value.
  4. Decrement both remaining counts by that amount and advance whichever pointer is exhausted.

💻 Benchmark Python3 Implementation

class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        res = []
        i = j = 0
        rem1, rem2 = encoded1[0][1], encoded2[0][1]
        while i < len(encoded1) and j < len(encoded2):
            prod = encoded1[i][0] * encoded2[j][0]
            cnt = min(rem1, rem2)      # this product holds for `cnt` positions
            if res and res[-1][0] == prod:
                res[-1][1] += cnt      # merge adjacent equal products
            else:
                res.append([prod, cnt])
            rem1 -= cnt
            rem2 -= cnt
            if rem1 == 0:
                i += 1
                if i < len(encoded1):
                    rem1 = encoded1[i][1]
            if rem2 == 0:
                j += 1
                if j < len(encoded2):
                    rem2 = encoded2[j][1]
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): each encoding entry is consumed once.
💾 Space Complexity
O(k) for the result, where k is the number of output runs.

⚠️ Interview Pitfalls & Follow-ups

  • Decoding both arrays fully and multiplying element-wise: O(total length), which can be 10^5 here -- acceptable but not the point of the problem, and it loses the compression.
  • Forgetting to merge adjacent equal products: the output must have maximal runs, so res[-1][0] == prod triggers a merge.
  • Advancing both pointers whenever either count hits zero: each must be advanced independently based on its own remaining count.
  • Accessing encoded1[i][1] after i goes out of range: the bounds check before reassigning rem1 is required.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems