Minimum operations to make an array palindrome
Problem
In one operation you may replace two adjacent elements with their sum. Return the minimum number of operations needed to turn the array into a palindrome.
Example 1
Input: [15, 4, 15] Output: 0
Example 2
Input: [1, 4, 5, 1] Output: 1
Merge 4 and 5 into 9: [1, 9, 1].
Also asked as: Minimum no. of operations required to make an array palindrome
Test cases
Case 1
Input: [15,4,15] Expected: 0
Case 2
Input: [1,4,5,1] Expected: 1
Case 3
Input: [11,14,15,99] Expected: 3
Case 4
Input: [5] Expected: 0
View solutionHide solution1 approach
1. Two pointers, merge the smaller side
Time O(n)Space O(1)
Compare ends. If equal, move both in. If left < right, merge a[l] into a[l+1] (one op). If left > right, merge a[r] into a[r−1].
function minOpsPalindrome(a) { let l = 0, r = a.length - 1, ops = 0; while (l < r) { if (a[l] === a[r]) { l++; r--; } else if (a[l] < a[r]) { a[l + 1] += a[l]; l++; ops++; } else { a[r - 1] += a[r]; r--; ops++; } } return ops;}