RLE Iterator - Practice Coding Problems

RLE Iterator - Problem

We can use run-length encoding (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. If there is no element left to exhaust, return -1 instead.

Input & Output

Example 1 — Basic RLE Iterator

$ Input: encoded = [3,8,0,9,2,5], operations = [2,1,1,2]

› Output: [8,8,5,-1]

💡 Note: RLE represents [8,8,8,5,5]. next(2) consumes 2 elements, returns 8. next(1) consumes 1 element, returns 8. next(1) consumes 1 element, returns 5. next(2) needs 2 elements but only 1 left, returns -1.

Example 2 — Empty Segments

$ Input: encoded = [1,2,0,3,4,1], operations = [1,1,1,1]

› Output: [2,1,1,1]

💡 Note: RLE represents [2,1,1,1,1]. The 0-count segment is skipped. Each next(1) returns consecutive elements.

Example 3 — Exact Exhaustion

$ Input: encoded = [2,5], operations = [1,1,1]

› Output: [5,5,-1]

💡 Note: RLE represents [5,5]. First two next(1) calls return 5, third call returns -1 as no elements left.

Constraints

1 ≤ encoded.length ≤ 1000
encoded.length % 2 == 0
1 ≤ encoded[i] ≤ 10⁹
1 ≤ n ≤ 10⁹
At most 1000 calls will be made to next

Visualization

Tap to expand

Understanding the Visualization

Input

RLE encoded array [3,8,0,9,2,5] represents sequence [8,8,8,5,5]

Process

Iterator tracks current segment and remaining count

Output

next() operations return last consumed element or -1

Key Takeaway

🎯 Key Insight: Track current RLE segment position and remaining count instead of expanding the entire array

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to track the current position in the RLE array and maintain a count of remaining elements in the current segment. Instead of expanding the entire array, we can iterate through RLE segments on-demand. The optimized approach uses O(1) space and O(k) time per next() call where k is the number of segments to skip. Time: O(k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Expand Array	O(S) for init + O(1) for next	O(S)	Decode the entire RLE array into a full array, then iterate normally
Optimized - Track Current Segment	O(1) for init + O(k) for next	O(1)	Maintain pointer to current RLE segment and track remaining count

Brute Force - Expand Array — Algorithm Steps

Step 1: Decode RLE array into full expanded array during initialization
Step 2: Use simple index pointer to skip n elements and return last one

Visualization

Tap to expand

Step-by-Step Walkthrough

Decode RLE

Expand [3,8,2,5] into [8,8,8,5,5]

Track Index

Use simple index pointer to navigate

Return Element

Return element at current position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* decoded;
    int size;
    int index;
} RLEIterator;

RLEIterator* createRLEIterator(int* encoded, int encodedSize) {
    RLEIterator* rle = (RLEIterator*)malloc(sizeof(RLEIterator));
    rle->decoded = (int*)malloc(100000 * sizeof(int));
    rle->size = 0;
    rle->index = 0;
    
    for (int i = 0; i < encodedSize; i += 2) {
        int count = encoded[i];
        int value = encoded[i + 1];
        for (int j = 0; j < count; j++) {
            rle->decoded[rle->size++] = value;
        }
    }
    return rle;
}

int next(RLEIterator* rle, int n) {
    rle->index += n;
    if (rle->index > rle->size) {
        return -1;
    }
    return rle->decoded[rle->index - 1];
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int encoded[1000];
    int encodedSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            encoded[encodedSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    int operations[1000];
    int operationsSize = 0;
    token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            operations[operationsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    RLEIterator* rle = createRLEIterator(encoded, encodedSize);
    
    printf("[");
    for (int i = 0; i < operationsSize; i++) {
        int result = next(rle, operations[i]);
        printf("%d", result);
        if (i < operationsSize - 1) printf(",");
    }
    printf("]\n");
    
    free(rle->decoded);
    free(rle);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(S) for init + O(1) for next

S is sum of all counts in RLE array for initialization, constant time for each next call

✓ Linear Growth

Space Complexity

O(S)

Store the entire decoded sequence which can be very large

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Expand Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler