Minimum operations to make an array palindrome

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}