Number of Runs: Count Consecutive Equal-Element Segments in an Array

Question

## Problem

A "run" is a maximal contiguous subarray of equal elements. Given an array, return the number of runs.

```python
def count_runs(arr: list) -> int:
    pass
```

**Example:**
```
Input:  [1, 1, 2, 3, 3, 3, 1]
Runs:   [1,1], [2], [3,3,3], [1]
Output: 4

Input:  [5]
Output: 1

Input:  []
Output: 0
```

## Round 2 - Variant

Return not just the count but also the encoded form: `[(value, length)]` pairs (run-length encoding).

```python
def run_length_encode(arr: list) -> list[tuple]:
    pass
```

**Example:**
```
Input:  [1, 1, 2, 3, 3, 3, 1]
Output: [(1,2), (2,1), (3,3), (1,1)]
```

Then decode it back:
```python
def run_length_decode(encoded: list[tuple]) -> list:
    pass
```

## Follow-ups

1. What is the time and space complexity of encoding and decoding?
2. For what types of data does run-length encoding provide the most compression?
3. How would you handle this for a stream of data (you cannot load the full array into memory)?
4. Extend to 2D: encode each row independently, then encode the rows of encodings. What are the tradeoffs?

Number of Runs: Count Consecutive Equal-Element Segments in an Array

Question Details

Full Details

Topics

More from Roblox