You are given an integer array nums.
You must repeatedly apply the following merge operation until no more changes can be made:
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:
1 + 1 = 2, resulting in [3, 2, 2].2 + 2 = 4, resulting in [3, 4].[3, 4].Example 2:
Input: nums = [2,2,4]
Output: [8]
Explanation:
2 + 2 = 4, resulting in [4, 4].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 <= 1051 <= nums[i] <= 105Problem 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).
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | Useful for understanding the raw merge mechanics or when constraints are very small |
| Stack-Based Simulation | O(n) | O(n) | General case and interview-preferred solution for efficiently resolving adjacent merges |
Merge Adjacent Equal Elements | LeetCode 3834 | Weekly Contest 488 • Sanyam IIT Guwahati • 510 views views
Watch 9 more video solutions →Practice Merge Adjacent Equal Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor