bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
MediumArrays & HashingLC 900

RLE Iterator

We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length encoding (0-indexed), for all even i, encoding[i] tells us the number of times that the non-negative integer value encoding[i + 1] is repeated in the sequence. For example, the sequence arr = [8,8,8,5,5] can be encoded to be encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] and encoding = [2,8,1,8,2,5] are also valid RLE of arr. Given a run-length encoded array, design an iterator that iterates through it. Implement the RLEIterator class: RLEIterator(int[] encoded) Initializes the object with the encoded array encoded. int next(int n) Exhausts the next n elements and returns the last element exhausted in this way.

Asked at 3 companies
AmazonGoogleWish
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode