Watch 10 video solutions for Merge Adjacent Equal Elements, a medium level problem involving Array, Stack, Simulation. This walkthrough by Sanyam IIT Guwahati has 510 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
| 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 |