34. Minimum Operations to Make an Array Palindrome

You may repeatedly merge two adjacent elements into one (replacing them with their sum). Find the minimum number of such merges needed to make the array a palindrome. Print that minimum.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print a single integer - the minimum number of adjacent merges needed to make the array a palindrome.

1 <= n <= 10^5

An array that's ALREADY a palindrome (like this exact example) needs zero merges - a good sanity check to run mentally before assuming the algorithm must always do some work.

You're allowed to merge any two ADJACENT elements into one (replacing them with their sum), repeatedly. Find the minimum number of merges needed to make the whole array read the same forwards and backwards. Brute force: Try every possible sequence of merges recursively, exploring all combinations of which adjacent pairs to merge and in what order - this branches exponentially and is impractical beyond tiny arrays. Optimised: A greedy two-pointer approach works because whenever the two ends DON'T match, the only sensible move is to merge on the side with the smaller value (growing it toward the larger side) - merging the LARGER side would never help, since it only makes the mismatch worse, so the greedy choice is always at least as good as any alternative.

Use two pointers left and right together with memoization over the (left, right) state, representing the minimum merges needed to make the current unmerged middle section a palindrome given the running sums accumulated on each side so far; compare the running left-side sum to the running right-side sum and branch into whichever side needs to absorb the next element, but cache results for repeated (left, right) states instead of recomputing them. This avoids the raw exponential blow-up of pure backtracking by reusing overlapping subproblems. Time: O(n^2) Space: O(n^2)

Try every possible sequence of adjacent merges via backtracking: at each state of the array, consider merging every possible adjacent pair, recursively continue from the resulting shorter array, and check whether it's already a palindrome, taking the minimum operation count over every branch that reaches one. Since each step branches into many possible merges and the array shrinks unpredictably along each path, the number of states explored grows combinatorially. Time: O(2^n) Space: O(n)

Use two pointers left=0 and right=n-1 with running sums leftSum=arr[left] and rightSum=arr[right]; if the sums are equal, move both pointers inward with no merge needed; if leftSum is smaller, it can never independently match the right side, so merge it with the next element and count an operation; symmetrically merge the right side if it's smaller. This greedy choice is always safe because whichever side is currently smaller is provably forced to merge regardless of what comes later, so a single pass to the middle finds the true minimum directly with no exploration needed. Time: O(n) Space: O(1)

1. Use two pointers, one at each end of the array. 2. If the values at both pointers already match, move both pointers inward - no merge needed here. 3. If they don't match, merge the SMALLER side's two outermost elements into one (combining it with its neighbor toward the middle), counting this as one operation, and try the comparison again with the new, updated boundary. 4. Continue until the two pointers meet or cross.

Time: O(n) - the two pointers only ever move inward or trigger a merge, so the total work across the whole process is linear in the array's size. Space: O(1) - the merging can be tracked with simple running sums at each pointer, no extra array needed.

n = 1 (already a palindrome, answer 0); an array that is already a palindrome, as in the example (answer 0); and n = 10^5 (largest, confirming the two-pointer merge approach is O(n)).

Be ready to justify WHY merging the smaller side (not the larger side, and not either side arbitrarily) is always the correct greedy choice - this justification is the crux of the whole problem.