Product of two run length encoded arrays

Array Two Pointers

59.6% acceptance

Mar 31, 2026

415

No description available.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_rle_array(encoded1: Vec<Vec<i32>>, encoded2: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut result: Vec<Vec<i32>> = Vec::new();
    let mut i = 0;
    let mut j = 0;
    let mut r1 = 0; // remaining freq in encoded1[i]
    let mut r2 = 0; // remaining freq in encoded2[j]
    
    r1 = encoded1[0][1];
    r2 = encoded2[0][1];
    
    while i < encoded1.len() && j < encoded2.len() {
      let prod = encoded1[i][0] * encoded2[j][0];
      let take = r1.min(r2);
      
      if let Some(last) = result.last_mut() {
        if last[0] == prod {
          last[1] += take;
        } else {
          result.push(vec![prod, take]);
        }
      } else {
        result.push(vec![prod, take]);
      }
      
      r1 -= take;
      r2 -= take;
      
      if r1 == 0 {
        i += 1;
        if i < encoded1.len() {
          r1 = encoded1[i][1];
        }
      }
      if r2 == 0 {
        j += 1;
        if j < encoded2.len() {
          r2 = encoded2[j][1];
        }
      }
    }
    result
  }
}