3834. Merge Adjacent Equal Elements

MediumStackArraySimulation

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

You must repeatedly apply the following merge operation until no more changes can be made:

If any two adjacent elements are equal, choose the leftmost such adjacent pair in the current array and replace them with a single element equal to their sum.

After each merge operation, the array size decreases by 1. Repeat the process on the updated array until no more changes can be made.

Return the final array after all possible merge operations.

The key idea is that each time you scan the array from the left, whenever you find the first pair of adjacent elements that are equal, you combine them into their sum. This combination may create a new equal pair with the element to its left, so merging can cascade. The process continues until there are no two adjacent elements that are equal anywhere in the array.

Example walkthrough: Suppose nums = [1, 1, 2]. The leftmost equal adjacent pair is [1, 1], which merges into 2, giving [2, 2]. Now [2, 2] is an equal pair, so it merges into 4, giving [4]. No more merges are possible, so the final array is [4].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Stack?

This problem maps to Stack through a short path in the full flowchart.

Merging adjacent equal elements and cascading the check backward after each merge maps perfectly to a stack-based reduction.

Open in Flowchart

Intuition

The naive way to solve this problem would be to repeatedly scan the entire array from the left, find the first equal adjacent pair, merge them, and start over. However, this leads to a lot of redundant scanning, since after each merge we restart from the beginning.

The crucial observation is about where new merges can happen. When we merge a pair of equal elements into their sum, the only place a new equal pair could appear is between this new merged value and the element immediately to its left. The elements further to the left were already processed and known to be non-mergeable, so we never need to look ahead — only backward.

This "merge and check backward" behavior maps perfectly onto a stack. As we process elements one by one from left to right, the stack always holds the current state of the merged array up to the current position. Whenever we push a new element x, we check the top of the stack:

If the top element equals x, they form an equal adjacent pair. We pop both and push their sum back.
This new sum might now equal the element beneath it, so we keep checking and merging until the top two elements differ.

Because every element is pushed onto the stack once, and each merge reduces the stack size, the whole process runs in linear time with a single pass — far more efficient than repeatedly rescanning from the start. The final contents of the stack, from bottom to top, give exactly the merged array we want to return.

Pattern Learn more about Stack patterns.

Solution Approach

Solution 1: Stack

We can use a stack to simulate the process of merging adjacent equal elements.

Define a stack stk to store the current processed array elements. Traverse each element x of the input array nums and push it onto the stack. Then check if the top two elements of the stack are equal. If they are equal, pop them and push their sum back onto the stack. Repeat this process until the top two elements of the stack are no longer equal. Finally, the elements in the stack are the final merged array.

Let's break down the implementation step by step:

Initialize the stack. Create an empty list stk = [] that will act as our stack and hold the merged array as we build it.
Iterate over each element. For every element x in nums, append it to the stack with stk.append(x). At this moment, x sits on top of the stack.
Merge backward while possible. Use a while loop with the condition len(stk) > 1 and stk[-1] == stk[-2]. This checks that there are at least two elements and that the top two are equal:
- If the condition holds, execute stk.append(stk.pop() + stk.pop()). This pops the top two equal elements, adds them, and pushes the sum back onto the stack.
- The loop continues, so the newly pushed sum is again compared with the element below it. This naturally handles cascading merges without any extra logic.
Return the result. After all elements are processed, stk contains the fully merged array from bottom to top, which is exactly the answer.

A small detail worth noting: in stk.pop() + stk.pop(), the additions are commutative, so the order in which the two pops happen does not affect the sum.

Complexity Analysis:

Time complexity: O(n), where n is the length of nums. Each element is pushed onto the stack once, and every merge operation removes one element overall. Since the total number of pushes and pops is bounded linearly, the entire process runs in linear time.
Space complexity: O(n), for the stack, which in the worst case (no merges happen) holds all n elements.

Example Walkthrough

Let's trace through the stack-based approach using the input nums = [2, 1, 1, 2]. We'll watch how the stack evolves as each element is processed, paying special attention to the cascading merges.

We start with an empty stack stk = [] and process the elements one at a time from left to right.

Step 1 — Process x = 2: We push 2 onto the stack.

stk = [2]
The while condition len(stk) > 1 fails (only one element), so no merge happens.

Step 2 — Process x = 1: We push 1 onto the stack.

stk = [2, 1]
Check the top two: stk[-1] == stk[-2] → 1 == 2? No. The loop does not run.

Step 3 — Process x = 1: We push 1 onto the stack.

stk = [2, 1, 1]
Check the top two: 1 == 1? Yes. We pop both 1s and push their sum 2.
stk = [2, 2]
The loop continues. Check again: 2 == 2? Yes. This is the cascade — the merge created a new equal pair with the element to its left. We pop both 2s and push their sum 4.
stk = [4]
Check again: len(stk) > 1 fails. The loop stops.

Step 4 — Process x = 2: We push 2 onto the stack.

stk = [4, 2]
Check the top two: 2 == 4? No. The loop does not run.

Final Result: After all elements are processed, the stack holds [4, 2], which is our answer.

The table below summarizes the entire process:

Element pushed	Stack after push	Merges triggered	Stack after merges
`2`	`[2]`	none	`[2]`
`1`	`[2, 1]`	none	`[2, 1]`
`1`	`[2, 1, 1]`	`1+1=2`, then `2+2=4`	`[4]`
`2`	`[4, 2]`	none	`[4, 2]`

The key insight illustrated here is Step 3: merging the two 1s into 2 immediately created a brand-new equal pair (2 and 2) with the element already on the stack. The while loop handles this chain reaction automatically by re-checking the top two elements after every merge — exactly the "merge and check backward" behavior, without ever needing to rescan from the start.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def mergeAdjacent(self, nums: List[int]) -> List[int]:
6        # Stack to keep track of processed elements
7        stack: List[int] = []
8
9        for num in nums:
10            # Push the current number onto the stack
11            stack.append(num)
12
13            # While the top two elements are equal, merge them by summing
14            while len(stack) > 1 and stack[-1] == stack[-2]:
15                # Pop the top two equal elements and push their sum back
16                merged = stack.pop() + stack.pop()
17                stack.append(merged)
18
19        return stack
20

1class Solution {
2    /**
3     * Merges adjacent equal elements by repeatedly combining them.
4     * When the top two elements on the stack are equal, they are summed
5     * into a single value. This may trigger further merges with the new top.
6     *
7     * @param nums the input array of integers
8     * @return a list of Long values after all adjacent merges are complete
9     */
10    public List<Long> mergeAdjacent(int[] nums) {
11        // Use a stack-like list to hold processed values
12        List<Long> stack = new ArrayList<>();
13
14        for (int num : nums) {
15            // Push the current value onto the stack
16            stack.add((long) num);
17
18            // Keep merging while the top two elements are equal
19            while (stack.size() > 1
20                    && stack.get(stack.size() - 1).equals(stack.get(stack.size() - 2))) {
21                // Remove the top two equal elements
22                long top = stack.remove(stack.size() - 1);
23                long second = stack.remove(stack.size() - 1);
24
25                // Push their sum back, which may cause another merge
26                stack.add(top + second);
27            }
28        }
29
30        return stack;
31    }
32}
33

1class Solution {
2public:
3    // Merge adjacent equal elements: when the last two elements on the stack
4    // are equal, pop them and push their sum. Repeat until no adjacent
5    // equal pair remains at the top.
6    vector<long long> mergeAdjacent(vector<int>& nums) {
7        vector<long long> stack;  // Acts as a stack to hold processed values
8
9        for (int value : nums) {
10            // Push the current value onto the stack
11            stack.push_back(value);
12
13            // While the top two elements are equal, merge them
14            while (stack.size() > 1 && stack.back() == stack[stack.size() - 2]) {
15                long long top = stack.back();  // Last element
16                stack.pop_back();
17
18                long long second = stack.back();  // Second-to-last element
19                stack.pop_back();
20
21                // Push the merged sum back onto the stack
22                stack.push_back(top + second);
23            }
24        }
25
26        return stack;
27    }
28};
29

1function mergeAdjacent(nums: number[]): number[] {
2    // Stack to hold the processed values
3    const stack: number[] = [];
4
5    // Iterate through each number in the input array
6    for (const num of nums) {
7        // Push the current number onto the stack
8        stack.push(num);
9
10        // While the top two elements are equal, merge them by summing
11        while (stack.length > 1 && stack.at(-1)! === stack.at(-2)!) {
12            const top = stack.pop()!;        // Remove the top element
13            const secondTop = stack.pop()!;  // Remove the next element
14            stack.push(top + secondTop);     // Push their combined sum
15        }
16    }
17
18    // Return the final merged stack
19    return stack;
20}
21

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The outer for loop iterates over each of the n elements exactly once. Although the inner while loop performs merge operations, each element can only be merged a limited number of times before being pushed back onto the stack, and the total number of push and pop operations across the entire execution is bounded by O(n). Therefore, the overall time complexity is linear.
Space Complexity: O(n). The stack stk is used to store the elements during processing. In the worst case (e.g., when no adjacent elements are equal), the stack may hold all n elements simultaneously, so the space required is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the "leftmost pair" rule and using a left-to-right re-scan after each merge

A very natural first instinct is to translate the problem statement literally: scan from the left, find the first equal adjacent pair, merge it, and then restart the scan from the beginning of the array. While this produces the correct answer, it can be implemented naively in a way that is needlessly slow.

# Naive O(n^2) (or worse) approach
class Solution:
    def mergeAdjacent(self, nums: List[int]) -> List[int]:
        nums = nums[:]
        i = 0
        while i < len(nums) - 1:
            if nums[i] == nums[i + 1]:
                nums[i] += nums[i + 1]
                del nums[i + 1]          # O(n) shift
                i = 0                    # restart from the beginning
            else:
                i += 1
        return nums

The problem here is twofold:

del nums[i + 1] shifts all subsequent elements, costing O(n) per deletion.
Resetting i = 0 after every merge forces a full re-scan, leading to quadratic (or worse) time.

Solution: Recognize that a merge can only ever cascade leftward (the new sum may equal the element to its left, but it can never affect elements to its right that haven't been visited yet). This is exactly what the stack captures: when you push an element and merge backward in a while loop, you are correctly simulating the "leftmost pair first, then cascade left" behavior without restarting the scan. The stack version is O(n).

Pitfall 2: Mutating the input list while iterating over it

If you try to merge in place by iterating over nums directly with a for loop and simultaneously deleting elements, you will skip elements or hit index errors, because the loop's index assumptions break when the underlying list shrinks.

# Buggy: modifying nums while iterating
for i in range(len(nums)):
    if nums[i] == nums[i + 1]:   # IndexError once the list shrinks
        ...

Solution: Build a fresh stack instead of mutating the original list during traversal. Each input element is read exactly once, and all merging happens on the separate stack structure.

Pitfall 3: Comparing the wrong pair (top with bottom, or forgetting the size check)

Two subtle off-by-one style mistakes can occur in the merge loop:

Forgetting len(stack) > 1, which causes an IndexError (or compares an element with itself) when only one element remains.
Comparing non-adjacent stack positions instead of the top two (stack[-1] and stack[-2]).

# Buggy: missing the length guard
while stack[-1] == stack[-2]:   # IndexError when len(stack) == 1
    stack.append(stack.pop() + stack.pop())

Solution: Always guard with len(stack) > 1 before the equality check, and only ever compare the two topmost elements (stack[-1] == stack[-2]), since those are the only adjacent pair that a freshly pushed/merged element can form:

while len(stack) > 1 and stack[-1] == stack[-2]:
    stack.append(stack.pop() + stack.pop())

Pitfall 4: Assuming pop order matters

A minor conceptual worry is whether stack.pop() + stack.pop() produces the correct value given that the two pops happen in a specific order. Because addition is commutative, the order of the two popped values does not change the sum, so this is safe. However, if the problem were ever changed to a non-commutative operation (e.g., subtraction or concatenation), the order would matter and you would need to capture the values explicitly:

top = stack.pop()
second = stack.pop()
stack.append(second - top)   # order now matters

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering