ArrayProblem 34 of 36
Minimum no. of operations required to make an array palindrome
Problem Statement
Given an array of positive integers, find the minimum number of merge operations required to make the array a palindrome. A merge operation combines two adjacent elements into their sum.
Example:
- Input:
arr = [1, 4, 5, 1] - Output:
1 - Explanation: Merge 4 and 5 to get [1, 9, 1], which is a palindrome.
Approach 1: Brute Force (Recursive)
Intuition
Try all possible ways to merge elements and find the minimum operations needed to make it a palindrome.
Algorithm
- If array is already palindrome, return 0
- For each pair of unequal elements from ends
- Try merging from left or right
- Return minimum operations
java
import java.util.*;
public class Solution {
public int minOperations(int[] arr) {
List<Integer> list = new ArrayList<>();
for (int num : arr) list.add(num);
return solve(list, 0, list.size() - 1, 0);
}
private int solve(List<Integer> arr, int left, int right, int ops) {
if (left >= right) return ops;
if (arr.get(left).equals(arr.get(right))) {
return solve(arr, left + 1, right - 1, ops);
}
// Try merging from left
List<Integer> leftMerge = new ArrayList<>(arr);
leftMerge.set(left + 1, leftMerge.get(left + 1) + leftMerge.get(left));
leftMerge.remove(left);
int leftOps = solve(leftMerge, left, leftMerge.size() - 1 - (arr.size() - 1 - right), ops + 1);
// Try merging from right
List<Integer> rightMerge = new ArrayList<>(arr);
rightMerge.set(right - 1, rightMerge.get(right - 1) + rightMerge.get(right));
rightMerge.remove(right);
int rightOps = solve(rightMerge, left, rightMerge.size() - 1 - (arr.size() - 1 - right) - 1, ops + 1);
return Math.min(leftOps, rightOps);
}
}Complexity Analysis
- Time Complexity: O(2^n) - Each element can be merged or not
- Space Complexity: O(n²) - Recursion stack and array copies
Approach 2: Optimal - Two Pointers (Greedy)
Intuition
Use two pointers from both ends. If elements are equal, move inward. If not, merge the smaller side since merging makes values larger and we want to balance them.
Algorithm
- Initialize left = 0, right = n-1
- While left < right:
- If arr[left] == arr[right]: move both pointers
- If arr[left] < arr[right]: merge arr[left] with arr[left+1]
- If arr[left] > arr[right]: merge arr[right] with arr[right-1]
- Count total merge operations
java
public class Solution {
public int minOperations(int[] arr) {
int n = arr.length;
int[] nums = arr.clone(); // Make a copy
int left = 0;
int right = n - 1;
int operations = 0;
while (left < right) {
if (nums[left] == nums[right]) {
// Already matching, move inward
left++;
right--;
} else if (nums[left] < nums[right]) {
// Merge left element with next
left++;
nums[left] += nums[left - 1];
operations++;
} else {
// Merge right element with previous
right--;
nums[right] += nums[right + 1];
operations++;
}
}
return operations;
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass with two pointers
- Space Complexity: O(1) - Only constant extra space (or O(n) if copying array)
Approach 3: Without Modifying Array
Intuition
Instead of actually merging, track cumulative sums from both ends.
Algorithm
- Use two pointers with cumulative sums
- Compare sums instead of elements
- Move pointer with smaller sum and add next element
java
public class Solution {
public int minOperations(int[] arr) {
int n = arr.length;
int left = 0;
int right = n - 1;
int operations = 0;
long leftSum = arr[left];
long rightSum = arr[right];
while (left < right) {
if (leftSum == rightSum) {
// Move both pointers
left++;
right--;
if (left < right) {
leftSum = arr[left];
rightSum = arr[right];
}
} else if (leftSum < rightSum) {
// Merge from left side
left++;
leftSum += arr[left];
operations++;
} else {
// Merge from right side
right--;
rightSum += arr[right];
operations++;
}
}
return operations;
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass with two pointers
- Space Complexity: O(1) - Only constant extra space
Key Takeaways
- Greedy approach works - Always merge the smaller side to balance values
- Two pointers from ends - Classic palindrome checking pattern
- Cumulative sums - Avoid actually modifying the array
- Merge operation - Adjacent elements can be combined into their sum
- Maximum operations - At most n-1 merges (reduces to single element)