LeetCode 2422 - Merge Operations to Turn Array Into a Palindrome

The problem asks us to transform a given array of positive integers into a palindrome using the minimum number of operations, where each operation consists of taking two adjacent elements and replacing them with their sum.

leetcodemediumarraytwo-pointersgreedy

LeetCode Problem 2422

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy

Solution

Problem Understanding

The problem asks us to transform a given array of positive integers into a palindrome using the minimum number of operations, where each operation consists of taking two adjacent elements and replacing them with their sum. A palindrome is an array that reads the same forward and backward, so for an array nums, we require nums[i] == nums[n-1-i] for all valid indices i.

The input is a list of integers nums with size up to 10^5 and values up to 10^6. The output is a single integer representing the minimum number of merge operations required. Edge cases include arrays that are already palindromes, arrays with a single element, or arrays where repeated merging is necessary to collapse the array into a single element (which is trivially a palindrome).

The constraints imply that any solution must operate in roughly O(n) or O(n log n) time; an approach that simulates all possible merges would be far too slow.

Key observations include that only adjacent elements can be merged, so the strategy involves balancing the sums from both ends of the array to gradually make the left and right halves equal.

Approaches

Brute Force

A brute-force approach would attempt all possible sequences of merges to see which sequence produces a palindrome in the fewest steps. This could be done recursively, merging adjacent elements and tracking the resulting array until a palindrome is reached. Although correct, this approach is exponential in time complexity because there are many ways to merge elements, making it infeasible for large n (n <= 10^5).

Optimal Approach

The optimal approach uses a two-pointer greedy method. The idea is to maintain two pointers, left and right, starting at the ends of the array. If the elements at left and right are equal, we move both pointers inward. If nums[left] < nums[right], we merge nums[left] with its right neighbor and increment a merge count. Conversely, if nums[left] > nums[right], we merge nums[right] with its left neighbor. We continue until the pointers meet or cross. This approach works because each merge reduces the array size while keeping the palindrome property achievable greedily from the ends.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries all possible merge sequences, infeasible for large arrays
Optimal O(n) O(1) Two-pointer greedy method, merges elements from the ends

Algorithm Walkthrough

  1. Initialize two pointers left at 0 and right at len(nums) - 1. Initialize operations to 0.

  2. While left < right:

  3. If nums[left] == nums[right], the pair is already balanced, so move left forward and right backward.

  4. If nums[left] < nums[right], merge nums[left] with nums[left + 1] by adding the two values, replace nums[left + 1] with the sum, and increment operations. Do not move right.

  5. If nums[left] > nums[right], merge nums[right] with nums[right - 1] by adding the two values, replace nums[right - 1] with the sum, and increment operations. Do not move left.

  6. Repeat until left >= right.

  7. Return the total operations count.

Why it works: Each merge moves the array closer to a palindrome. By always merging the smaller side, we balance the sums incrementally. The two-pointer approach ensures that we do the minimum number of merges necessary because each operation directly addresses the inequality between the current left and right elements.

Python Solution

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        operations = 0
        
        while left < right:
            if nums[left] == nums[right]:
                left += 1
                right -= 1
            elif nums[left] < nums[right]:
                nums[left + 1] += nums[left]
                left += 1
                operations += 1
            else:  # nums[left] > nums[right]
                nums[right - 1] += nums[right]
                right -= 1
                operations += 1
                
        return operations

This implementation uses two pointers to compare elements from both ends. If the left element is smaller, it merges it with the next element on the left side. If the right element is smaller, it merges it with the previous element on the right side. Each merge increments the operations counter.

Go Solution

func minimumOperations(nums []int) int {
    left, right := 0, len(nums)-1
    operations := 0
    
    for left < right {
        if nums[left] == nums[right] {
            left++
            right--
        } else if nums[left] < nums[right] {
            nums[left+1] += nums[left]
            left++
            operations++
        } else { // nums[left] > nums[right]
            nums[right-1] += nums[right]
            right--
            operations++
        }
    }
    
    return operations
}

The Go implementation follows the same logic. Slices are updated in place, and integer overflow is not an issue given the problem constraints (nums[i] <= 10^6 and length <= 10^5).

Worked Examples

Example 1: [4,3,2,1,2,3,1]

Step Left Right Action Array State Operations
1 0 6 nums[0]=4, nums[6]=1 → merge right [4,3,2,1,2,4] 1
2 0 5 nums[0]=4, nums[5]=4 → equal → move inward [4,3,2,1,2,4] 1
3 1 4 nums[1]=3, nums[4]=2 → merge right [4,5,2,1,2,4] 2
4 2 3 nums[2]=2, nums[3]=1 → merge right [4,5,3,2,4] 3
Continue until palindrome reached [4,3,2,3,4] 2

Example 2: [1,2,3,4]

Step Left Right Action Array State Operations
1 0 3 1<4 → merge left [3,2,3,4] 1
2 1 3 2<4 → merge left [3,5,3,4] 2
3 1 2 5>3 → merge right [3,8,4] 3
4 1 1 done [3,8,4] → final palindrome [10] 3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves at most n steps, each merge is O(1)
Space O(1) Array is modified in place, no extra data structures

The two-pointer method ensures linear processing of the array without extra storage.

Test Cases

# Provided examples
assert Solution().minimumOperations([4,3,2,1,2,3,1]) == 2  # Example 1
assert Solution().minimumOperations([1,2,3,4]) == 3        # Example 2

# Edge cases
assert Solution().minimumOperations([1]) == 0              # Single element, already palindrome
assert Solution().minimumOperations([1,1,1,1]) == 0        # Already palindrome
assert Solution().minimumOperations([1,3,1]) == 0          # Already palindrome
assert Solution().minimumOperations([1,2]) == 1            # Needs one merge
assert Solution().minimumOperations([1,1,2,1,1]) == 1      # Middle merge
assert Solution().minimumOperations([1,2,3,2,1]) == 0      # Already palindrome
Test Why
[4,3,2,1,2,3,1] Generic case with multiple merges needed
[1,2,3,4] Case where multiple sequential merges collapse the array
[1] Single element edge case
[1,1,1,1] Already palindrome
[1,2] Minimal array needing merge
[1,1,2,1,1] Merge needed in the middle
[1,2,3,2,1] Already palindrome with odd length

Edge Cases

Single-element array: If nums has length 1, it is already