Compress Array

01 · Question

Given an integer array, repeatedly replace the leftmost adjacent equal pair with its sum until no equal neighbors remain. Return the resulting array without changing the input.

Examples: [8,4,2,2,2,4] → [16,2,4]; [4,4,4,4] → [16]; [1,2,3] → [1,2,3]; [] → [].

Merges may cascade immediately; this is not the rule that a tile merges only once per move in 2048.

02 · Analysis

Invariant: the stack is the fully compressed prefix. Read the next value, merge while it equals the top, then push the final value. This respects the leftmost-pair rule because all earlier pairs are already resolved.

Trace: [8,4,2] + 2 → [8,4] + 4 → [8] + 8 → [] + 16. The remaining inputs 2 and 4 give [16,2,4].

Each element is pushed once; every loop iteration pops an entry. O(n) time, O(n) space, assuming constant-time arithmetic. Zeros and negative values also work; every merge reduces the length even if the numeric value does not change.

03 · Solution

Reference solution

1def compress_array(arr):
2    stack = []
3    for value in arr:
4        while stack and stack[-1] == value:
5            value += stack.pop()
6        stack.append(value)
7    return stack

Compress Array by K