Skip to main content
Talentd

Merge Adjacent Equal Elements - Solution & Explanation

MediumArrayStackSimulation7 min read
Practice this problem

Problem Statement

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.

 

Example 1:

Input: nums = [3,1,1,2]

Output: [3,4]

Explanation:

  • The middle two elements are equal and merged into 1 + 1 = 2, resulting in [3, 2, 2].
  • The last two elements are equal and merged into 2 + 2 = 4, resulting in [3, 4].
  • No adjacent equal elements remain. Thus, the answer is [3, 4].

Example 2:

Input: nums = [2,2,4]

Output: [8]

Explanation:

  • The first two elements are equal and merged into 2 + 2 = 4, resulting in [4, 4].
  • The first two elements are equal and merged into 4 + 4 = 8, resulting in [8].

Example 3:

Input: nums = [3,7,5]

Output: [3,7,5]

Explanation:

There are no adjacent equal elements in the array, so no operations are performed.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Approach Overview

Problem Overview: You are given an array and must repeatedly merge adjacent elements that have the same value. When two neighboring elements match, they collapse into a single merged value according to the rule defined by the problem (commonly doubling or combining the value). The challenge is simulating these merges efficiently while preserving the correct order.

Approach 1: Brute Force Simulation (O(nĀ²) time, O(1) extra space)

The most direct approach repeatedly scans the array looking for adjacent equal elements. When you find a pair, merge them and shift the remaining elements left to maintain a valid array. After each merge, restart the scan because a new merge opportunity might appear with the newly formed value. This approach mirrors the literal process described in the problem but performs poorly because every merge can trigger a full array shift and another scan.

Approach 2: Stack-Based Simulation (O(n) time, O(n) space)

A stack models the merge process efficiently. Iterate through the array from left to right. For each value, compare it with the element on top of the stack. If the top element equals the current value, pop it, compute the merged value, and push the result back. Otherwise, push the current value normally. Each element is pushed and popped at most once, which keeps the total work linear.

This method works because the stack always represents the current stable state of the array after all valid merges to the left have already happened. When a merge creates a new value, pushing it back onto the stack allows further merges with previous elements if needed. The algorithm effectively performs the same operations as the naive simulation but avoids repeated rescans.

The pattern is common in problems involving collapsing adjacent elements, resolving neighbors, or maintaining a dynamic frontier. Problems tagged with simulation often benefit from a stack because it naturally tracks the most recent unresolved element.

Recommended for interviews: The stack-based approach is the expected solution. Mentioning the brute force simulation first shows you understand the mechanics of the problem, but implementing the stack optimization demonstrates stronger algorithmic thinking and reduces the complexity from O(nĀ²) to O(n).

Solution

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.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(n), which is used to store the elements in the stack.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(nĀ²)O(1)Useful for understanding the raw merge mechanics or when constraints are very small
Stack-Based SimulationO(n)O(n)General case and interview-preferred solution for efficiently resolving adjacent merges

Video Solution

Merge Adjacent Equal Elements | LeetCode 3834 | Weekly Contest 488 ā€¢ Sanyam IIT Guwahati ā€¢ 548 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Merge Adjacent Equal Elements easy or hard?
Merge Adjacent Equal Elements is generally considered a medium-level problem. The main challenge is recognizing that a stack cleanly models the repeated merging process and avoids the inefficiency of repeatedly rescanning the array.
Merge Adjacent Equal Elements Python/Java solution
The typical implementation iterates through the array and uses a stack (list in Python or Stack/Deque in Java). When the current element equals the top of the stack, pop the top, compute the merged value, and push it back. The same logic translates easily to C++, Go, and TypeScript.
How to solve Merge Adjacent Equal Elements in O(n)?
Use a stack to simulate the merging process. Iterate through the array, compare the current value with the stack's top element, and merge when they match. Push the merged value back to allow further merges if possible. This ensures a single linear pass with O(n) time and O(n) space.
What is the best approach for Merge Adjacent Equal Elements?
The stack-based simulation is the best approach. Traverse the array once and maintain a stack representing the current merged state. When the current element equals the stack top, merge them and push the result back. Each element is processed at most twice, giving O(n) time complexity.
Is Merge Adjacent Equal Elements asked at Google/Amazon/Meta?
Variants of adjacent merge and collapse problems appear in interviews at companies like Amazon, Google, and Meta. These companies often test stack-based simulations or array compression techniques where local neighbor interactions must be resolved efficiently.
What data structure is used in Merge Adjacent Equal Elements?
A stack is the primary data structure used for the optimal solution. It tracks the most recent unresolved element and allows efficient comparison with the current value to determine whether a merge should occur.
What is the time complexity of Merge Adjacent Equal Elements?
The optimal stack solution runs in O(n) time because each element is pushed and popped from the stack at most once. The brute force simulation may degrade to O(n^2) since each merge can trigger another full scan of the array.

Ready to solve this problem?

Practice Merge Adjacent Equal Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays