Merge Operations to Turn Array Into a Palindrome

Merge Operations to Turn Array Into a Palindrome - Problem

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].

Return the minimum number of operations needed to turn the array into a palindrome.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,3,2,1,2,3,1]

› Output: 3

💡 Note: Step by step: [4,3,2,1,2,3,1] → [4,3,2,1,2,4] → [4,3,2,3,4] → [4,3,5,4] → palindrome achieved in 3 operations

Example 2 — Already Palindrome

$ Input: nums = [1,2,3,2,1]

› Output: 0

💡 Note: Array is already a palindrome, so no operations needed

Example 3 — Single Element

$ Input: nums = [1]

› Output: 0

💡 Note: Single element is always a palindrome, return 0

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [4,3,2,1,2,3,1] needs to become palindrome

Merge Strategy

Use two pointers, merge smaller side when ends differ

Result

Minimum 3 operations needed

Key Takeaway

🎯 Key Insight: When array ends don't match, always merge the side with smaller value to minimize total operations

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to use a greedy two-pointer approach where we compare elements from both ends and merge the side with the smaller value when they don't match. This minimizes operations because merging the smaller side creates a better chance for future matches. Best approach uses Two Pointers Greedy with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2ⁿ)	O(n)	Try all possible merge operations until palindrome is found
Optimized Two Pointers	O(n)	O(1)	Enhanced greedy approach with boundary optimization
Two Pointers Greedy	O(n)	O(1)	Use two pointers from ends, merge the smaller side when values don't match

Recursive Backtracking — Algorithm Steps

Check if current array is palindrome
If not, try merging each adjacent pair
Recursively solve for each possibility
Return minimum operations found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Array

Start with [4,3,2,1,2,3,1]

Try All Merges

Recursively try merging each adjacent pair

Find Minimum

Return path with fewest operations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int isPalindrome(int* arr, int size) {
    int left = 0, right = size - 1;
    while (left < right) {
        if (arr[left] != arr[right]) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}

int minOps(int* arr, int size) {
    if (isPalindrome(arr, size)) {
        return 0;
    }
    if (size <= 1) {
        return 0;
    }
    
    int minOperations = INT_MAX;
    for (int i = 0; i < size - 1; i++) {
        int* newArr = (int*)malloc((size - 1) * sizeof(int));
        int idx = 0;
        for (int j = 0; j < i; j++) {
            newArr[idx++] = arr[j];
        }
        newArr[idx++] = arr[i] + arr[i+1];
        for (int j = i + 2; j < size; j++) {
            newArr[idx++] = arr[j];
        }
        int operations = 1 + minOps(newArr, size - 1);
        if (operations < minOperations) {
            minOperations = operations;
        }
        free(newArr);
    }
    
    return minOperations;
}

int solution(int* nums, int size) {
    return minOps(nums, size);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each position can be merged or not, creating exponential possibilities

✓ Linear Growth

Space Complexity

O(n)

Recursion depth can go up to n levels

⚡ Linearithmic Space

24.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler