Minimum Cost to cut a board into squares

The problem, simply

A board has m rows and n columns of little squares. To split it into single squares you must cut along every line between rows (m - 1 row lines) and every line between columns (n - 1 column lines). Each line has a price.

When you cut along a line, you cut every piece that line passes through, and you pay the price once for each piece. Give back the smallest total cost.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order of the cuts. Keep track of how many row strips and column strips the board has. A row cut passes through one piece per column strip, and a column cut through one piece per row strip.

1. Pick any unused line as the next cut and pay its price times the pieces it passes through.
2. Recurse with that line marked as used and the strip count raised by one.
3. Keep the cheapest total.

class Solution {
    public long minCost(int[] rowLines, int[] colLines) {
        return tryAll(rowLines, colLines, new boolean[rowLines.length], new boolean[colLines.length], 1, 1);
    }

    // rows and cols: how many strips the board has in each direction right now
    private long tryAll(int[] r, int[] c, boolean[] usedR, boolean[] usedC, int rows, int cols) {
        long best = Long.MAX_VALUE;
        boolean anyLeft = false;
        for (int i = 0; i < r.length; i++) {
            if (usedR[i]) continue;
            anyLeft = true;
            usedR[i] = true;                                   // a row cut crosses every column strip
            best = Math.min(best, (long) r[i] * cols + tryAll(r, c, usedR, usedC, rows + 1, cols));
            usedR[i] = false;
        }
        for (int j = 0; j < c.length; j++) {
            if (usedC[j]) continue;
            anyLeft = true;
            usedC[j] = true;                                   // a column cut crosses every row strip
            best = Math.min(best, (long) c[j] * rows + tryAll(r, c, usedR, usedC, rows, cols + 1));
            usedC[j] = false;
        }
        return anyLeft ? best : 0;
    }
}

How long it takes: with m + n - 2 lines there are (m + n - 2)! orders, so O((m + n)!). Extra room: the recursion is one level per cut, O(m + n).

Way 2: the clever way

A line is cut once, but its price is multiplied by the pieces it passes through, and that number only grows. So a line's price should be paid while the multiplier is small. The most expensive line should go first, then the next most expensive, no matter which direction it runs.

1. Sort the row prices and the column prices from big to small.
2. Keep two counters: rows (row strips so far) and cols (column strips so far). Both start at 1.
3. Compare the biggest row price left with the biggest column price left. Cut the bigger one:
   • a row cut costs price * cols, then rows++;
   • a column cut costs price * rows, then cols++.
4. When one list runs out, cut the rest of the other list the same way.

Each cell in the picture is one piece, labelled with its height and width in little squares.

import java.util.Arrays;

class Solution {
    public long minCost(int[] rowLines, int[] colLines) {
        Arrays.sort(rowLines);
        Arrays.sort(colLines);
        int i = rowLines.length - 1, j = colLines.length - 1;   // the biggest prices sit at the end
        long rows = 1, cols = 1, cost = 0;
        while (i >= 0 || j >= 0) {
            if (j < 0 || (i >= 0 && rowLines[i] >= colLines[j])) {
                cost += rowLines[i--] * cols;    // a row cut goes through every column strip
                rows++;
            } else {
                cost += colLines[j--] * rows;    // a column cut goes through every row strip
                cols++;
            }
        }
        return cost;
    }
}

How long it takes: sorting is O(m log m + n log n) and the merge walk is O(m + n). Extra room: O(1) beyond the sort.

Watch out for

• Ties between a row line and a column line can go either way. Both orders give the same total, because together the two cuts pay price * (rows + cols + 1) either way.
• Use long. The counters can reach 100,000 and prices a million.
• Do not cut one direction completely first. In the 2 by 2 example, cutting the cheap column first costs 7 instead of 5.
• The number of lines is one less than the number of rows or columns.

What interviewers ask next

• Prove that bigger first is right. If a cheaper line comes right before a more expensive one, swapping them moves the expensive line to a smaller multiplier and the cheap one to a bigger one, which never costs more. This is an exchange argument.
• What if every cut costs only its price, no matter how many pieces it passes through? Then the order does not matter and the answer is the sum of all prices.
• What if you only want to break a chocolate bar into squares with the fewest snaps, one piece at a time? Every snap makes one more piece, so it is always m * n - 1 snaps.
• Can you do better than sorting? If prices are small integers, counting sort makes it O(m + n + max price).

Remember this

Grown-up words: the strips are the counts of horizontal and vertical segments, picking the bigger of two sorted lists is a merge step, and the swap proof is an exchange argument.