Skip to content

Compress Array by K

01 · Question

Given an integer array and k ≥ 2, repeatedly replace the leftmost block of k equal adjacent values with their sum. Return the fully compressed array.

Examples: [1,9,9,3,3,3,4], k=3 → [1,27,4]; [8,4,2,2], k=2 → [16]; [4,4,4], k=5 → [4,4,4]. Empty input returns an empty array.

02 · Analysis

Store (value, count) groups. In the settled stack, adjacent groups have different values and each count is below k. Merge a new value into the last run when equal. If its count reaches k, pop that run, multiply the value by k, and process it again against the newly exposed top.

For k=3, [(1,1),(9,2),(3,2)] + 3 becomes [(1,1),(9,2)] + 9, then [(1,1)] + 27.

Re-expand the runs to produce the answer. Each merge reduces the represented length by k−1: O(n) time and O(n) space under constant-time arithmetic. The iterative loop avoids recursion-depth failures during long cascades. Go's integer type must be large enough for merged sums.

03 · Solution

Reference solution

1def compress_array_k(arr, k):
2    if k < 2:
3        raise ValueError("k must be at least 2")
4    runs = []
5    for value in arr:
6        while True:
7            if runs and runs[-1][0] == value:
8                runs[-1][1] += 1
9            else:
10                runs.append([value, 1])
11            if runs[-1][1] < k:
12                break
13            value = runs.pop()[0] * k
14    return [value for value, count in runs for _ in range(count)]
Previous
Compress Array
Next
Viewer Counter Class