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
- Walk both encodings with two pointers and two remaining-count variables.
- At each step, the product of the current values applies to
min(rem1, rem2)positions. - Append the run, merging with the previous entry when the product equals the last stored value.
- 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] == prodtriggers 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]afterigoes out of range: the bounds check before reassigningrem1is required.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.