Log inSign up
mediumGeeksforGeeksNot Started

Minimum Cost to Cut a Board

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

A board of length M and width N is given. To break the board into 1 x 1 squares, you need to make M - 1 horizontal cuts and N - 1 vertical cuts.

The cost of each horizontal cut is given in array X[] of size M - 1, and the cost of each vertical cut is given in array Y[] of size N - 1.

Whenever a cut is made across the board, the cost is multiplied by the number of pieces currently present in the perpendicular direction. Find the minimum total cost to cut the board into 1 x 1 squares.

Example 1 · Example 1: Small Board:

Input: M = 6, N = 4, X = [2, 1, 3, 1, 4], Y = [4, 1, 2]
Output: 42
Explanation: Sorted X = [4, 3, 2, 1, 1], Sorted Y = [4, 2, 1].\n- Cut Y[0]=4 (or X[0]=4): cost += 4 * 1 = 4. vPieces = 2.\n- Cut X[0]=4: cost += 4 * 2 = 8. hPieces = 2.\n- Cut X[1]=3: cost += 3 * 2 = 6. hPieces = 3.\n- Cut Y[1]=2: cost += 2 * 3 = 6. vPieces = 3.\nContinuing this greedy selection yields minimum total cost 42.

Constraints:

  • 1 <= M, N <= 105
  • 0 <= X[i], Y[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why cutting expensive lines early minimizes perpendicular segment multiplications.
  • Track dynamic horizontal and vertical piece multipliers correctly.
  • Implement the optimal two-pointer solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Grid or chocolate bar cut into unit squares.
  • Cuts cost money scaled by pieces already created.
  • Minimize sum of (cut cost * current segment count).

Algorithmic Decision Tree:

  • Always pick max(currentHorizontalCut, currentVerticalCut).
  • If horizontal cut chosen: cost += X[i] * vPieces; hPieces++.
  • If vertical cut chosen: cost += Y[j] * hPieces; vPieces++.

Connected Patterns:

Huffman CodingConnect RopesFractional Knapsack

1. Recursive Permutation Search

Intuition

Recursively evaluate both choices at each step (making the next horizontal cut vs the next vertical cut) and find the minimal total cost.

Algorithm

  1. Step 1: Sort X and Y descending.
  2. Step 2: Define recursive function minCost(i, j, hPieces, vPieces).
  3. Step 3: If i == X.size() and j == Y.size(), return 0.
  4. Step 4: If i < X.size(), try horizontal cut: X[i] * vPieces + minCost(i + 1, j, hPieces + 1, vPieces).
  5. Step 5: If j < Y.size(), try vertical cut: Y[j] * hPieces + minCost(i, j + 1, hPieces, vPieces + 1).
  6. Step 6: Return the minimum of valid choices.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 long long solve(int i, int j, int hPieces, int vPieces, const vector<int>& X, const vector<int>& Y) {
9 if (i == X.size() && j == Y.size()) return 0;
10 long long ans = 1e18;
11 if (i < X.size()) {
12 ans = min(ans, (long long)X[i] * vPieces + solve(i + 1, j, hPieces + 1, vPieces, X, Y));
13 }
14 if (j < Y.size()) {
15 ans = min(ans, (long long)Y[j] * hPieces + solve(i, j + 1, hPieces, vPieces + 1, X, Y));
16 }
17 return ans;
18 }
19public:
20 long long minimumCostOfBreaking(vector<int> X, vector<int> Y, int M, int N) {
21 sort(X.rbegin(), X.rend());
22 sort(Y.rbegin(), Y.rend());
23 return solve(0, 0, 1, 1, X, Y);
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> X = {2, 1, 3, 1, 4};
30 vector<int> Y = {4, 1, 2};
31 cout << "Min Cost: " << sol.minimumCostOfBreaking(X, Y, 6, 4) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(2^(M + N))
  • Space complexity: O(M + N)

2. Max-Heap Cut Selection

Intuition

Store all cut costs tagged with their type in a max-priority queue and pop the largest available cut iteratively.

Algorithm

  1. Step 1: Insert all horizontal cuts as pairs (cost, H) and vertical cuts as (cost, V) into a max-heap.
  2. Step 2: Initialize hPieces = 1, vPieces = 1, totalCost = 0.
  3. Step 3: Pop the maximum cut from the heap.
  4. Step 4: If type is H: totalCost += cost * vPieces, hPieces++.
  5. Step 5: If type is V: totalCost += cost * hPieces, vPieces++.
  6. Step 6: Repeat until the heap is empty, then return totalCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7class Solution {
8public:
9 long long minimumCostOfBreaking(vector<int> X, vector<int> Y, int M, int N) {
10 priority_queue<pair<int, char>> maxHeap;
11 for (int x : X) maxHeap.push({x, 'H'});
12 for (int y : Y) maxHeap.push({y, 'V'});
13
14 int hPieces = 1, vPieces = 1;
15 long long totalCost = 0;
16
17 while (!maxHeap.empty()) {
18 auto top = maxHeap.top();
19 maxHeap.pop();
20
21 int cost = top.first;
22 char type = top.second;
23
24 if (type == 'H') {
25 totalCost += (long long)cost * vPieces;
26 hPieces++;
27 } else {
28 totalCost += (long long)cost * hPieces;
29 vPieces++;
30 }
31 }
32
33 return totalCost;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> X = {2, 1, 3, 1, 4};
40 vector<int> Y = {4, 1, 2};
41 cout << "Min Cost (Heap): " << sol.minimumCostOfBreaking(X, Y, 6, 4) << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O((M + N) log(M + N))
  • Space complexity: O(M + N)

3. Greedy Two Pointers on Sorted Cuts

Intuition

Sort horizontal and vertical cuts in descending order. Use two pointers to greedily select the larger cut, scaling by perpendicular piece counts.

Algorithm

  1. Step 1: Sort array X in descending order and array Y in descending order.
  2. Step 2: Initialize i = 0, j = 0, hPieces = 1, vPieces = 1, totalCost = 0.
  3. Step 3: While i < X.size() and j < Y.size(): if X[i] > Y[j], totalCost += X[i] * vPieces, hPieces++, i++; else totalCost += Y[j] * hPieces, vPieces++, j++.
  4. Step 4: Process remaining horizontal cuts: totalCost += X[i] * vPieces, i++.
  5. Step 5: Process remaining vertical cuts: totalCost += Y[j] * hPieces, j++.
  6. Step 6: Return totalCost.

Interactive Trace for Cutting Board

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compare X[0]=4 and Y[0]=4
Visual state
Values and pointers at this exact step
pointers
S
cut
cut
pending
pending
0
↑ i
1
↑ j
2
3
Check / comparison
Y[0] (4) cut chosen. Multiplier: hPieces = 1.
Decision / next transition
Add 4 * 1 = 4 to cost. vPieces = 2.
Why this step matters

Step 1: Compare X[0]=4 and Y[0]=4. Tie-break: take Y[0]=4. Multiplied by hPieces (1). Total cost = 4. vPieces becomes 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 long long minimumCostOfBreaking(vector<int> X, vector<int> Y, int M, int N) {
10 sort(X.rbegin(), X.rend());
11 sort(Y.rbegin(), Y.rend());
12
13 int i = 0, j = 0;
14 int hPieces = 1, vPieces = 1;
15 long long totalCost = 0;
16
17 while (i < X.size() && j < Y.size()) {
18 if (X[i] > Y[j]) {
19 totalCost += (long long)X[i] * vPieces;
20 hPieces++;
21 i++;
22 } else {
23 totalCost += (long long)Y[j] * hPieces;
24 vPieces++;
25 j++;
26 }
27 }
28
29 while (i < X.size()) {
30 totalCost += (long long)X[i] * vPieces;
31 hPieces++;
32 i++;
33 }
34
35 while (j < Y.size()) {
36 totalCost += (long long)Y[j] * hPieces;
37 vPieces++;
38 j++;
39 }
40
41 return totalCost;
42 }
43};
44
45int main() {
46 Solution sol;
47 vector<int> X = {2, 1, 3, 1, 4};
48 vector<int> Y = {4, 1, 2};
49 cout << "Min Cost (Optimal): " << sol.minimumCostOfBreaking(X, Y, 6, 4) << endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(M log M + N log N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recursive Order PermutationO((M + N)!)O(M + N)Try all possible interleavings of horizontal and vertical cuts recursively, tracking piece counts and taking the minimum cost.Combinatorial explosion of cut sequences.
2.Better — Max-Heap Cut SelectionO((M + N) log(M + N))O(M + N)Push all cuts into a max-heap tagged with cut orientation (H or V). Pop the maximum cut and update costs and piece counters accordingly.Heap operations.
3.Optimal — Two Pointers on Sorted ArraysOptimalO(M log M + N log N)O(1) auxiliarySort both cut cost arrays descending. Maintain two pointers and pieces counters (hPieces = 1, vPieces = 1). In each step, execute the larger cut.Initial sorting step.
Back to DSA Sheet