Merge Adjacent Equal Elements

medium stack array simulation

Problem

Given an integer array nums, repeatedly apply this merge until no change is possible: find the leftmost pair of adjacent equal elements and replace the two of them with a single element equal to their sum. Each merge shrinks the array by one. Return the final array once no adjacent equal elements remain.

Inputnums = [3, 1, 1, 2]

Output[3, 4]

Merge 1+1 → [3, 2, 2], then merge 2+2 → [3, 4]. No adjacent equals remain.

nums (comma-separated positive integers)

def mergeAdjacent(nums):
    stack = []
    for x in nums:
        cur = x
        # absorb every equal neighbour now on top
        while stack and stack[-1] == cur:
            cur += stack.pop()
        stack.append(cur)
    return stack

function mergeAdjacent(nums) {
  const stack = [];
  for (const x of nums) {
    let cur = x;
    // absorb every equal neighbour now on top
    while (stack.length && stack[stack.length - 1] === cur) {
      cur += stack.pop();
    }
    stack.push(cur);
  }
  return stack;
}

List<Long> mergeAdjacent(int[] nums) {
    Deque<Long> stack = new ArrayDeque<>();
    for (int x : nums) {
        long cur = x;
        // absorb every equal neighbour now on top
        while (!stack.isEmpty() && stack.peekLast() == cur) {
            cur += stack.pollLast();
        }
        stack.addLast(cur);
    }
    return new ArrayList<>(stack);
}

vector<long long> mergeAdjacent(vector<int>& nums) {
    vector<long long> stack;
    for (int x : nums) {
        long long cur = x;
        // absorb every equal neighbour now on top
        while (!stack.empty() && stack.back() == cur) {
            cur += stack.back();
            stack.pop_back();
        }
        stack.push_back(cur);
    }
    return stack;
}

Explanation

The naive reading — scan the array, merge the leftmost equal pair, then start over — can take O(n²) work because each merge restarts the scan. A stack collapses all of that into a single left-to-right pass.

We process elements one at a time. The stack always holds the “already merged” prefix, left to right, with no two adjacent equal values inside it. When a new value cur arrives, we compare it with the stack’s top.

If they are equal, that is exactly a leftmost adjacent equal pair in the current array, so we pop the top and fold it into cur as their sum. The new sum might now equal the element beneath it, creating a fresh adjacent pair, so we keep looping the while until the top differs. Only then do we push cur.

This matches the “leftmost pair first” rule: because everything to the left is already fully merged, the first place a new merge can happen is right where cur meets the top. Each value is pushed once and popped at most once, so the whole thing is linear.

Example: [3, 1, 1, 2]. Push 3, push 1. The second 1 equals the top, so 1 + 1 = 2 replaces it; 2 differs from 3, push it. The final 2 equals the top, so 2 + 2 = 4; 4 differs from 3, push. Stack [3, 4] is the answer.

Time: O(n) Space: O(n)