Welcome to Subscribe On Youtube

3834. Merge Adjacent Equal Elements

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.

 

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​​​​​​​

Solutions

Solution 1: Stack

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

Define a stack $\textit{stk}$ to store the current processed array elements. Traverse each element $x$ of the input array $\textit{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 $\textit{nums}$. The space complexity is $O(n)$, which is used to store the elements in the stack.

  • class Solution {
    public List<Long> mergeAdjacent(int[] nums) {
        List<Long> stk = new ArrayList<>();
        for (int x : nums) {
            stk.add((long) x);
            while (stk.size() > 1 && stk.get(stk.size() - 1).equals(stk.get(stk.size() - 2))) {
                long a = stk.remove(stk.size() - 1);
                long b = stk.remove(stk.size() - 1);
                stk.add(a + b);
            }
        }
        return stk;
    }
}


  • class Solution {
public:
    vector<long long> mergeAdjacent(vector<int>& nums) {
        vector<long long> stk;
        for (int x : nums) {
            stk.push_back(x);
            while (stk.size() > 1 && stk.back() == stk[stk.size() - 2]) {
                long long a = stk.back();
                stk.pop_back();
                long long b = stk.back();
                stk.pop_back();
                stk.push_back(a + b);
            }
        }
        return stk;
    }
};


  • class Solution:
    def mergeAdjacent(self, nums: List[int]) -> List[int]:
        stk = []
        for x in nums:
            stk.append(x)
            while len(stk) > 1 and stk[-1] == stk[-2]:
                stk.append(stk.pop() + stk.pop())
        return stk


  • func mergeAdjacent(nums []int) []int64 {
	stk := []int64{}
	for _, x := range nums {
		stk = append(stk, int64(x))
		for len(stk) > 1 && stk[len(stk)-1] == stk[len(stk)-2] {
			a := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			b := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			stk = append(stk, a+b)
		}
	}
	return stk
}


  • function mergeAdjacent(nums: number[]): number[] {
    const stk: number[] = [];
    for (const x of nums) {
        stk.push(x);
        while (stk.length > 1 && stk.at(-1)! === stk.at(-2)!) {
            const a = stk.pop()!;
            const b = stk.pop()!;
            stk.push(a + b);
        }
    }
    return stk;
}

All Problems

All Solutions