Minimum no. of operations required to make an array palindrome

The problem, simply

You get an array of positive numbers. In one step you may take two numbers that sit next to each other and replace them with their sum. The array gets one shorter.

Find the fewest steps that make the array a palindrome: it reads the same from left to right and from right to left. One number on its own always counts as a palindrome, so there is always an answer.

A story to remember it

Picture it

Examples

Way 1: the simple way

Peel off matching ends. When the two ends differ, you could glue on the left or glue on the right. Try both, and keep the one that needs fewer steps in the end.

class Solution {
    public int minMerges(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int x : arr) list.add(x);
        return solve(list);
    }

    private int solve(List<Integer> a) {
        int i = 0, j = a.size() - 1;
        while (i < j && a.get(i).equals(a.get(j))) { i++; j--; }   // peel matching ends
        if (i >= j) return 0;                                       // already a mirror
        List<Integer> glueLeft = new ArrayList<>(a);
        glueLeft.set(i + 1, a.get(i) + a.get(i + 1));
        glueLeft.remove(i);
        List<Integer> glueRight = new ArrayList<>(a);
        glueRight.set(j - 1, a.get(j - 1) + a.get(j));
        glueRight.remove(j);
        return 1 + Math.min(solve(glueLeft), solve(glueRight));
    }
}

How long it takes: every mismatch splits into two tries, so up to O(2^n). Extra room: up to n waiting calls, each holding a copy of the list, O(n^2).

Way 2: the clever way

There is no real choice. If the left end is smaller than the right end, the left end can never match the right end as it is: the right end can only grow. So the left end must be glued. The same goes the other way.

1. Put i at the front and j at the back. left is the car at i, right the car at j.
2. If left == right, they match. Move both inward and read the new cars.
3. If left < right, glue: move i one step and add that car to left. Count one step.
4. If left > right, glue on the right side the same way.
5. Stop when i and j meet or cross.

The code never really shortens the array. It keeps a running sum on each side, which is the same as gluing. The lower row shows the train as if we had glued it.

class Solution {
    public int minMerges(int[] arr) {
        int i = 0, j = arr.length - 1, steps = 0;
        if (j < 0) return 0;
        long left = arr[i], right = arr[j];      // the car at each end, after any gluing
        while (i < j) {
            if (left == right) {                 // a match: step in on both sides
                i++;
                j--;
                if (i < j) { left = arr[i]; right = arr[j]; }
            } else if (left < right) {           // front is shorter: glue it to the next car
                i++;
                left += arr[i];
                steps++;
            } else {                             // back is shorter: glue it to the car before
                j--;
                right += arr[j];
                steps++;
            }
        }
        return steps;
    }
}

How long it takes: every step moves i or j (or both) one spot, O(n). Extra room: a few numbers, O(1), and the input is not changed.

Watch out for

• The sums can get large. Use long for left and right.
• This greedy needs positive numbers. With zeros or negatives, a glue can make a car shorter and the argument breaks.
• After a match, read fresh values only if i < j; otherwise you may read past the middle.

What interviewers ask next

• Why is the greedy optimal? The smaller end must grow before it can match, and the only way it grows is by gluing on its own side. So that glue is forced, and every forced glue is counted once.
• Return the final palindrome, not just the count. Write each matched pair of sums into a front list and a back list as you go.
• What if a step may also split a number into two? That is a different problem with a dynamic programming answer over the two ends.
• Minimum insertions to make a string a palindrome. That is a classic 2D dynamic programming problem: n minus the longest palindromic subsequence.

Remember this

Grown-up words: the cars are array elements, gluing is the merge operation, the two friends are two pointers, and the running totals are prefix and suffix sums.