Merge Operations to Turn Array Into a Palindrome - Solution & Explanation
Problem Statement
You are given an array nums consisting of positive integers.
You can perform the following operation on the array any number of times:
- Choose any two adjacent elements and replace them with their sum.
- For example, if
nums = [1,2,3,1], you can apply one operation to make it[1,5,1].
- For example, if
Return the minimum number of operations needed to turn the array into a palindrome.
Example 1:
Input: nums = [4,3,2,1,2,3,1] Output: 2 Explanation: We can turn the array into a palindrome in 2 operations as follows: - Apply the operation on the fourth and fifth element of the array, nums becomes equal to [4,3,2,3,3,1]. - Apply the operation on the fifth and sixth element of the array, nums becomes equal to [4,3,2,3,4]. The array [4,3,2,3,4] is a palindrome. It can be shown that 2 is the minimum number of operations needed.
Example 2:
Input: nums = [1,2,3,4] Output: 3 Explanation: We do the operation 3 times in any position, we obtain the array [10] at the end which is a palindrome.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106
Approach Overview
Problem Overview: You are given an integer array. In one operation, you can merge two adjacent elements and replace them with their sum. The goal is to perform the minimum number of merge operations so the array becomes a palindrome. A palindrome reads the same from left to right and right to left.
Approach 1: Brute Force Simulation (O(n2) time, O(1) space)
The most direct idea is to repeatedly scan the array and merge elements whenever the ends do not match. If nums[left] != nums[right], merge one side and rebuild the array structure. After each merge, shift elements and continue checking until the array becomes a palindrome. Because merging requires modifying the array and shifting elements, each operation may take O(n) time. In the worst case you perform up to O(n) merges, leading to O(n2) total time. This approach demonstrates the mechanics of the operation but is inefficient for large arrays.
Approach 2: Greedy + Two Pointers (O(n) time, O(1) space)
The optimal solution uses a greedy strategy with two pointers. Start one pointer at the left end and another at the right end. If nums[left] == nums[right], both values already match in the palindrome structure, so move both pointers inward. If the left value is smaller, merge it with the next element (nums[left] += nums[left+1]) and move the left pointer forward. If the right value is smaller, merge from the right side (nums[right] += nums[right-1]) and move the right pointer backward.
The key insight: when the sums differ, merging the smaller side is always optimal. A smaller value cannot match the larger one unless it accumulates more elements, so greedily expanding that side minimizes future merges. Each element participates in at most one merge step as the pointers move inward, which guarantees linear traversal.
This pattern is common in array problems where you compare symmetric positions and adjust values incrementally. The greedy rule ensures progress without revisiting previous states, keeping the algorithm O(n). The implementation modifies values logically during traversal rather than rebuilding the array structure.
Recommended for interviews: The greedy greedy two-pointer approach is the expected solution. Interviewers want to see that you recognize the symmetry of a palindrome and avoid expensive array modifications. Mentioning the brute force simulation first shows you understand the operation, but implementing the O(n) two-pointer strategy demonstrates strong problem-solving instincts.
Solution
Define two pointers i and j, pointing to the beginning and end of the array respectively, use variables a and b to represent the values of the first and last elements, and variable ans to represent the number of operations.
If a < b, we move the pointer i one step to the right, i.e., i \leftarrow i + 1, then add the value of the element pointed to by i to a, i.e., a \leftarrow a + nums[i], and increment the operation count by one, i.e., ans \leftarrow ans + 1.
If a > b, we move the pointer j one step to the left, i.e., j \leftarrow j - 1, then add the value of the element pointed to by j to b, i.e., b \leftarrow b + nums[j], and increment the operation count by one, i.e., ans \leftarrow ans + 1.
Otherwise, it means a = b, at this time we move the pointer i one step to the right, i.e., i \leftarrow i + 1, move the pointer j one step to the left, i.e., j \leftarrow j - 1, and update the values of a and b, i.e., a \leftarrow nums[i] and b \leftarrow nums[j].
Repeat the above process until i \ge j, return the operation count ans.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Useful for understanding the merge process or quick prototyping |
| Greedy + Two Pointers | O(n) | O(1) | Optimal solution for interviews and production; processes array in a single pass |
Video Solution
2422. Merge Operations to Turn Array Into a Palindrome (Leetcode Medium) • Programming Live with Larry • 480 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Merge Operations to Turn Array Into a Palindrome easy or hard?
Merge Operations to Turn Array Into a Palindrome Python/Java solution
How to solve Merge Operations to Turn Array Into a Palindrome in O(n)?
What is the best approach for Merge Operations to Turn Array Into a Palindrome?
Is Merge Operations to Turn Array Into a Palindrome asked at Google/Amazon/Meta?
What data structure is used in Merge Operations to Turn Array Into a Palindrome?
What is the time complexity of Merge Operations to Turn Array Into a Palindrome?
Ready to solve this problem?
Practice Merge Operations to Turn Array Into a Palindrome with our built-in code editor and test cases.
Practice on FleetCode