Skip to content

1868. Product of Two Run-Length Encoded Arrays 👍

  • Time: $O(|\texttt{encoded1}| + |\texttt{encoded2}|)$
  • Space: $O(|\texttt{encoded1}| + |\texttt{encoded2}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1,
                                   vector<vector<int>>& encoded2) {
    vector<vector<int>> ans;
    int i = 0;  // encoded1's index
    int j = 0;  // encodes2's index

    while (i < encoded1.size() && j < encoded2.size()) {
      const int mult = encoded1[i][0] * encoded2[j][0];
      const int minFreq = min(encoded1[i][1], encoded2[j][1]);
      if (!ans.empty() && mult == ans.back()[0])
        ans.back()[1] += minFreq;
      else
        ans.push_back({mult, minFreq});
      encoded1[i][1] -= minFreq;
      encoded2[j][1] -= minFreq;
      if (encoded1[i][1] == 0)
        ++i;
      if (encoded2[j][1] == 0)
        ++j;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
    List<List<Integer>> ans = new ArrayList<>();
    int i = 0; // encoded1's index
    int j = 0; // encodes2's index

    while (i < encoded1.length && j < encoded2.length) {
      final int mult = encoded1[i][0] * encoded2[j][0];
      final int minFreq = Math.min(encoded1[i][1], encoded2[j][1]);
      if (!ans.isEmpty() && mult == ans.get(ans.size() - 1).get(0))
        ans.get(ans.size() - 1).set(1, ans.get(ans.size() - 1).get(1) + minFreq);
      else
        ans.add(Arrays.asList(mult, minFreq));
      encoded1[i][1] -= minFreq;
      encoded2[j][1] -= minFreq;
      if (encoded1[i][1] == 0)
        ++i;
      if (encoded2[j][1] == 0)
        ++j;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def findRLEArray(self, encoded1: list[list[int]],
                   encoded2: list[list[int]]) -> list[list[int]]:
    ans = []
    i = 0  # encoded1's index
    j = 0  # encoded2's index

    while i < len(encoded1) and j < len(encoded2):
      mult = encoded1[i][0] * encoded2[j][0]
      minFreq = min(encoded1[i][1], encoded2[j][1])
      if ans and mult == ans[-1][0]:
        ans[-1][1] += minFreq
      else:
        ans.append([mult, minFreq])
      encoded1[i][1] -= minFreq
      encoded2[j][1] -= minFreq
      if encoded1[i][1] == 0:
        i += 1
      if encoded2[j][1] == 0:
        j += 1

    return ans