Minimum Cost to Cut a Stick

Hard
897.

Minimum Cost to Cut a Stick

Minimum Cost to Cut a Stick is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Microsoft interviews.

A stick of length n is marked at the positions in cuts. Cutting a stick costs the length of the stick being cut, and after a cut the two pieces are cut independently.

You may perform the cuts in any order. Return the minimum total cost.

Example 1

Input
n = 7, cuts = [1,3,4,5]
Output
16
Explanation
Cutting in the order 3, 5, 1, 4 costs 7 + 4 + 3 + 2.

Example 2

Input
n = 9, cuts = [5,6,1,4,2]
Output
22

Example 3

Input
n = 5, cuts = [2]
Output
5
Explanation
One cut on the whole stick.

Constraints

  • 2 <= n <= 1000000
  • 1 <= cuts.length <= 100
  • 1 <= cuts[i] <= n - 1
  • All values in cuts are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} cuts
 * @return {number}
 */
var minCost = function(n, cuts) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost to Cut a Stick — Solution in Python, Java & C++

Minimum Cost to Cut a Stick solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Cost to Cut a Stick is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Microsoft interviews.

Problem statement

A stick of length n is marked at the positions in cuts. Cutting a stick costs the length of the stick being cut, and after a cut the two pieces are cut independently.

You may perform the cuts in any order. Return the minimum total cost.

Example 1

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Cutting in the order 3, 5, 1, 4 costs 7 + 4 + 3 + 2.

Example 2

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22

Example 3

Input: n = 5, cuts = [2]
Output: 5
Explanation: One cut on the whole stick.

Constraints

  • 2 <= n <= 1000000
  • 1 <= cuts.length <= 100
  • 1 <= cuts[i] <= n - 1
  • All values in cuts are distinct.

Hints for Minimum Cost to Cut a Stick

  1. Hint 1

    Sort the cut positions and add the two stick ends, 0 and n, as sentinels.

  2. Hint 2

    dp[i][j] is the cost of fully cutting the piece between sentinel positions i and j.

  3. Hint 3

    Choose which cut inside that piece is made first: it costs the piece's length and splits the work in two.

How to solve Minimum Cost to Cut a Stick

Interval DP over the sorted cut positions. Once a piece is isolated, the cuts inside it never interact with anything outside — so deciding which of its cuts happens first splits the problem cleanly.

Approach

  1. Build pts = [0] + sorted(cuts) + [n].
  2. dp[i][j] is the minimum cost to make every cut strictly between pts[i] and pts[j].
  3. For each k in (i, j), cutting at pts[k] first costs pts[j] - pts[i] plus dp[i][k] + dp[k][j].
  4. Fill by increasing interval length; the answer is dp[0][m-1].

Why it works

The cost of any single cut is the length of the piece it lands on, which depends only on the two nearest cuts already made on either side — exactly the interval boundaries. So fixing the first cut inside an interval makes the two halves independent, which is what licenses the DP. Adding the sentinels removes the need to special-case the stick's ends.

Complexity

  • Time — O(m³) where m is the number of cuts
  • Space — O(m²)

Pitfalls

  • Choosing which cut is made last does not decompose — the piece's length would then depend on cuts outside the interval.
  • The cuts must be sorted; the input order is arbitrary.
  • A greedy 'always cut in the middle' is wrong.

Reference solution

Python

from typing import List

def minCost(n: int, cuts: List[int]) -> int:
    pts = [0] + sorted(cuts) + [n]
    m = len(pts)
    dp = [[0] * m for _ in range(m)]
    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            best = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
            dp[i][j] = best + pts[j] - pts[i]
    return dp[0][m - 1]

Java

public static int minCost(int n, int[] cuts) {
    int[] sorted = cuts.clone();
    Arrays.sort(sorted);
    int m = sorted.length + 2;
    int[] pts = new int[m];
    pts[0] = 0;
    pts[m - 1] = n;
    for (int i = 0; i < sorted.length; i++) pts[i + 1] = sorted[i];
    int[][] dp = new int[m][m];
    for (int len = 2; len < m; len++) {
        for (int i = 0; i + len < m; i++) {
            int j = i + len;
            int best = Integer.MAX_VALUE;
            for (int k = i + 1; k < j; k++) best = Math.min(best, dp[i][k] + dp[k][j]);
            dp[i][j] = best + pts[j] - pts[i];
        }
    }
    return dp[0][m - 1];
}

C++

int minCost(int n, vector<int>& cuts) {
    vector<int> pts;
    pts.push_back(0);
    vector<int> sorted = cuts;
    sort(sorted.begin(), sorted.end());
    for (int c : sorted) pts.push_back(c);
    pts.push_back(n);
    int m = (int) pts.size();
    vector<vector<int>> dp(m, vector<int>(m, 0));
    for (int len = 2; len < m; len++) {
        for (int i = 0; i + len < m; i++) {
            int j = i + len;
            int best = INT_MAX;
            for (int k = i + 1; k < j; k++) best = min(best, dp[i][k] + dp[k][j]);
            dp[i][j] = best + pts[j] - pts[i];
        }
    }
    return dp[0][m - 1];
}

JavaScript

var minCost = function(n, cuts) {
    var pts = [0].concat(cuts.slice().sort(function(a, b) { return a - b; })).concat([n]);
    var m = pts.length;
    var dp = [];
    for (var a = 0; a < m; a++) {
        var row = [];
        for (var b = 0; b < m; b++) row.push(0);
        dp.push(row);
    }
    for (var len = 2; len < m; len++) {
        for (var i = 0; i + len < m; i++) {
            var j = i + len;
            var best = Infinity;
            for (var k = i + 1; k < j; k++) {
                var v = dp[i][k] + dp[k][j];
                if (v < best) best = v;
            }
            dp[i][j] = best + pts[j] - pts[i];
        }
    }
    return dp[0][m - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming