You are given an array nums consisting of positive integers.
You can perform the following operation on the array any number of times:
nums = [1,2,3,1], you can apply one operation to make it [1,5,1].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] <= 106Problem 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.
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).
| 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 |
2422. Merge Operations to Turn Array Into a Palindrome (Leetcode Medium) • Programming Live with Larry • 473 views views
Watch 6 more video solutions →Practice Merge Operations to Turn Array Into a Palindrome with our built-in code editor and test cases.
Practice on FleetCode