LeetCode 3834 - Merge Adjacent Equal Elements
The problem asks us to repeatedly merge adjacent equal elements in an integer array nums until no further merges are possible. Specifically, if two consecutive elements are equal, we replace them with their sum.
Difficulty: 🟡 Medium
Topics: Array, Stack, Simulation
Solution
Problem Understanding
The problem asks us to repeatedly merge adjacent equal elements in an integer array nums until no further merges are possible. Specifically, if two consecutive elements are equal, we replace them with their sum. The key points are that we always pick the leftmost pair for merging, and after each merge, the array size decreases by one. The process continues until the array has no adjacent equal elements.
The input nums is an array of integers where each element is at least 1, and the array can have up to 100,000 elements. The output is the final array after all possible merge operations. The constraints imply that a naive approach that repeatedly scans the entire array for equal pairs could be too slow, as it may require many passes for large arrays.
Important edge cases include arrays that are already fully unique (no merges happen), arrays with long sequences of identical numbers, and arrays where merging triggers further merges (cascading merges).
Approaches
The brute-force approach involves repeatedly scanning the array from left to right, merging the first adjacent equal pair found, and then restarting from the beginning. This guarantees correctness because we always merge leftmost pairs. However, each merge requires shifting elements in the array and rescanning, which can lead to O(n²) time complexity in the worst case. For an array of length up to 100,000, this is not feasible.
The optimal approach leverages a stack-based simulation. Instead of repeatedly scanning the array, we maintain a stack to keep track of the currently processed elements. For each element in the array, we compare it with the top of the stack. If they are equal, we pop the top, sum it with the current element, and then push the sum back. This allows cascading merges to happen naturally: after a merge, we check again with the new top of the stack. This approach processes each element at most a few times, giving O(n) time complexity.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly scan array and merge leftmost equal pair |
| Optimal | O(n) | O(n) | Use stack to simulate merges efficiently |
Algorithm Walkthrough
- Initialize an empty stack.
- Iterate through each element
numin the input arraynums. - While the stack is not empty and the top element equals
num, pop the top element from the stack and sum it withnum. Setnumto this new sum. This handles cascading merges automatically. - Push
numonto the stack. At this point, no further immediate merges are possible with the previous element. - After processing all elements, the stack contains the final merged array in order. Convert the stack to a list and return it.
Why it works: The stack invariant guarantees that no two adjacent elements on the stack are equal. When we process a new element, we merge it with the previous element as long as equality holds. This captures the repeated leftmost merge process without rescanning the entire array.
Python Solution
from typing import List
class Solution:
def mergeAdjacent(self, nums: List[int]) -> List[int]:
stack: List[int] = []
for num in nums:
while stack and stack[-1] == num:
num += stack.pop()
stack.append(num)
return stack
The implementation initializes an empty stack to store the partially merged array. For each number, it repeatedly merges with the top of the stack if they are equal. The while loop ensures cascading merges are handled efficiently. Finally, the stack represents the array after all possible merges.
Go Solution
func mergeAdjacent(nums []int) []int64 {
stack := []int64{}
for _, n := range nums {
num := int64(n)
for len(stack) > 0 && stack[len(stack)-1] == num {
num += stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
stack = append(stack, num)
}
return stack
}
The Go solution mirrors the Python approach. We use a slice stack to simulate the stack, converting each input element to int64 to avoid overflow when summing. The for loop handles cascading merges, and the final stack is returned as the result.
Worked Examples
Example 1: nums = [3,1,1,2]
| Step | Stack | Operation |
|---|---|---|
| 1 | [] | push 3 |
| 2 | [3] | push 1 |
| 3 | [3] → [3,2] | merge 1+1=2 |
| 4 | [3,2] | push 2 |
| 5 | [3,4] | merge 2+2=4 |
| Final | [3,4] | no more merges |
Example 2: nums = [2,2,4]
| Step | Stack | Operation |
|---|---|---|
| 1 | [] | push 2 |
| 2 | [2] → [4] | merge 2+2=4 |
| 3 | [4] → [8] | merge 4+4=8 |
| Final | [8] | no more merges |
Example 3: nums = [3,7,5]
| Step | Stack | Operation |
|---|---|---|
| 1 | [] | push 3 |
| 2 | [3] | push 7 |
| 3 | [3,7] | push 5 |
| Final | [3,7,5] | no merges |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each element is pushed and popped at most once from the stack, giving linear time |
| Space | O(n) | Stack stores at most all elements of the array |
The stack ensures that we process each element efficiently, handling cascading merges in a single pass, avoiding the quadratic behavior of repeated full scans.
Test Cases
# test cases
sol = Solution()
# Provided examples
assert sol.mergeAdjacent([3,1,1,2]) == [3,4] # merges middle 1s then 2s
assert sol.mergeAdjacent([2,2,4]) == [8] # multiple cascading merges
assert sol.mergeAdjacent([3,7,5]) == [3,7,5] # no merges
# Edge cases
assert sol.mergeAdjacent([1]) == [1] # single element
assert sol.mergeAdjacent([5,5,5,5]) == [20] # all equal, multiple merges
assert sol.mergeAdjacent([1,2,3,4]) == [1,2,3,4] # all unique, no merges
assert sol.mergeAdjacent([2,2,2,2,4,4]) == [16] # cascading merges
| Test | Why |
|---|---|
| [3,1,1,2] | Checks basic merge operations |
| [2,2,4] | Checks cascading merges |
| [3,7,5] | Array with no merges |
| [1] | Single element edge case |
| [5,5,5,5] | All elements equal, multiple merges |
| [1,2,3,4] | No merges possible |
| [2,2,2,2,4,4] | Complex cascading merges |
Edge Cases
Single element: An array of length 1 cannot have merges. The implementation handles this by simply pushing the element to the stack and returning it.
All elements equal: In arrays like [5,5,5,5], repeated merges cause cascading sums. The stack ensures that after each merge, the new element is checked against the previous, so the final sum accumulates correctly.
No merges possible: Arrays with all distinct elements never enter the merge loop. The stack simply accumulates elements in order, ensuring the output is identical to the input. This avoids unnecessary operations.