Minimum Cost to cut a board into squares

Last Updated : 13 Sep, 2025

Given a board of dimensions n × m that needs to be cut into n × m squares. The cost of making a cut along a horizontal or vertical edge is provided in two arrays:

  • x[]: Cutting costs along the vertical edges (length-wise).
  • y[]: Cutting costs along the horizontal edges (width-wise).

Find the minimum total cost required to cut the board into squares optimally.

Examples: 

Input: x[] = [2, 1, 3, 1, 4], y[] = [4, 1, 2], n = 4, m = 6
Output: 42
Explanation:

Initially no. of horizontal segments = 1 & no. of vertical segments = 1.
Optimal way to cut into square is:
Pick 4 (from x) -> vertical cut, Cost = 4 × horizontal segments = 4,
 Now, horizontal segments = 1, vertical segments = 2.
Pick 4 (from y) -> horizontal cut, Cost = 4 × vertical segments = 8,
 Now, horizontal segments = 2, vertical segments = 2.
Pick 3 (from x) -> vertical cut, Cost = 3 × horizontal segments = 6,
 Now, horizontal segments = 2, vertical segments = 3.
Pick 2 (from x) -> vertical cut, Cost = 2 × horizontal segments = 4,
 Now, horizontal segments = 2, vertical segments = 4.
Pick 2 (from y) -> horizontal cut, Cost = 2 × vertical segments = 8,
 Now, horizontal segments = 3, vertical segments = 4.
Pick 1 (from x) -> vertical cut, Cost = 1 × horizontal segments = 3,
Now, horizontal segments = 3, vertical segments = 5.
Pick 1 (from x) -> vertical cut, Cost = 1 × horizontal segments = 3,
Now, horizontal segments = 3, vertical segments = 6.
Pick 1 (from y) -> horizontal cut, Cost = 1 × vertical segments = 6,
Now, horizontal segments = 4, vertical segments = 6.
So, the total cost = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Input: x[] = [1, 1, 1], y[] = [1, 1, 1], n = 4, m = 4
Output: 15
Explanation:
Initially no. of horizontal segments = 1 & no. of vertical segments = 1.
Optimal way to cut into square is:
Pick 1 (from y) -> horizontal cut, Cost = 1 × vertical segments = 1,
Now, horizontal segments = 2, vertical segments = 1.
Pick 1 (from y) -> horizontal cut, Cost = 1 × vertical segments = 1,
Now, horizontal segments = 3, vertical segments = 1.
Pick 1 (from y) -> horizontal cut, Cost = 1 × vertical segments = 1,
Now, horizontal segments = 4, vertical segments = 1.
Pick 1 (from x) -> vertical cut, Cost = 1 × horizontal segments = 4,
Now, horizontal segments = 4, vertical segments = 2.
Pick 1 (from x) -> vertical cut, Cost = 1 × horizontal segments = 4,
Now, horizontal segments = 4, vertical segments = 3.
Pick 1 (from x) -> vertical cut, Cost = 1 × horizontal segments = 4,
Now, horizontal segments = 4, vertical segments = 4
So, the total cost = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Try All Permutations - O((n+m)!×(n+m)) Time and O(n+m) Space

The idea is to generate all possible permutations of the given cuts and then calculate the cost for each permutation. Finally, return the minimum cost among them.

Note: This approach is not feasible for larger inputs because the number of permutations grows factorially as (m+n-2)!.
For each permutation, we must calculate the cost in O(m+n) time. Hence, the overall time complexity becomes O((m+n−2)!×(m+n)).

[Expected Approach] Using Greedy Technique - O( n (log n)+m (log m)) Time and O(1) Space

The idea is to make the most expensive cuts first using a greedy approach. The observation is that choosing the highest cost cut at each step reduces future costs by affecting multiple pieces at once. We sort the vertical (x) and horizontal (y) cut costs in descending order, then iteratively pick the larger one to maximize cost savings. The remaining cuts are processed separately to ensure all sections are split optimally.

What happens when we make a cut?

  • Horizontal cut → you are cutting across the width, so the number of horizontal strips increases (hCount++). But the cost is multiplied by vCount (the number of vertical strips), because the horizontal cut has to pass through all vertical segments.
  • Vertical cut → you are cutting across the height, so the number of vertical strips increases (vCount++). But the cost is multiplied by hCount (the number of horizontal strips), because the vertical cut has to pass through all horizontal segments.

Steps to solve the problem:

  • Sort both x and y arrays in descending order.
  • Use two pointers, one for x and one for y, starting from the largest value and moving toward smaller values.
  • Maintain hCount and vCount to track how many segments each cut affects and update them accordingly.
  • Iterate while both x and y have unprocessed cuts, always choosing the larger cost to minimize overall expenses.
  • If x has remaining cuts, process them with hCount multiplier; similarly, process remaining y cuts with vCount.
  • Accumulate total cost at each step using the formula: cut cost * number of affected pieces, ensuring minimal cost.
C++ 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int minCost(int n, int m, 
                          vector<int>& x, vector<int>& y) {
    
    // Sort the cutting costs in ascending order
    sort(x.begin(), x.end());
    sort(y.begin(), y.end()); 

    int hCount = 1, vCount = 1; 
    int i = x.size() - 1, j = y.size() - 1; 
    int totalCost = 0;

    while (i >= 0 && j >= 0) {
        
        // Choose the larger cost cut to 
        // minimize future costs
        if (x[i] >= y[j]) {
            totalCost += x[i] * hCount; 
            vCount++;
            i--;
        } 
        else {
            totalCost += y[j] * vCount; 
            hCount++;
            j--;
        }
    }

    // Process remaining vertical cuts
    while (i >= 0) {
        totalCost += x[i] * hCount;
        vCount++;
        i--;
    }

    // Process remaining horizontal cuts
    while (j >= 0) {
        totalCost += y[j] * vCount;
        hCount++;
        j--;
    }

    return totalCost;
}

int main() {
    
    int n = 4, m = 6;
    vector<int> x = {2, 1, 3, 1, 4};
    vector<int> y = {4, 1, 2};

    cout << minCost(n, m, x, y) << endl;
    return 0;
}
Java 
import java.util.Arrays;

class GfG {
    
    static int minCost(int n, int m, 
                                     int[] x, int[] y) {
        
        // Sort the cutting costs in ascending order
        Arrays.sort(x);
        Arrays.sort(y); 

        int hCount = 1, vCount = 1; 
        int i = x.length - 1, j = y.length - 1; 
        int totalCost = 0;
        while (i >= 0 && j >= 0) {
            
            // Choose the larger cost cut to 
            // minimize future costs
            if (x[i] >= y[j]) {
                totalCost += x[i] * hCount; 
                vCount++;
                i--;
            } 
            else {
                totalCost += y[j] * vCount; 
                hCount++;
                j--;
            }
        }

        // Process remaining vertical cuts
        while (i >= 0) {
            totalCost += x[i] * hCount;
            vCount++;
            i--;
        }

        // Process remaining horizontal cuts
        while (j >= 0) {
            totalCost += y[j] * vCount;
            hCount++;
            j--;
        }

        return totalCost;
    }

    public static void main(String[] args) {
        
        int n = 4,m = 6;
        int[] x = {2, 1, 3, 1, 4};
        int[] y = {4, 1, 2};

        System.out.println(minCost(n, m, x, y));
    }
}
Python 
def minCost(n,m, x, y):
    
    # Sort the cutting costs in ascending order
    x.sort()
    y.sort()

    hCount, vCount = 1, 1
    i, j = len(x) - 1, len(y) - 1
    totalCost = 0
    while i >= 0 and j >= 0:
        
        # Choose the larger cost cut to 
        # minimize future costs
        if x[i] >= y[j]:
            totalCost += x[i] * hCount
            vCount += 1
            i -= 1
        else:
            totalCost += y[j] * vCount
            hCount += 1
            j -= 1

    # Process remaining vertical cuts
    while i >= 0:
        totalCost += x[i] * hCount
        vCount += 1
        i -= 1

    # Process remaining horizontal cuts
    while j >= 0:
        totalCost += y[j] * vCount
        hCount += 1
        j -= 1

    return totalCost

if __name__ == "__main__":
    
    n,m = 4, 6
    x = [2, 1, 3, 1, 4]
    y = [4, 1, 2]

    print(minCost(n,m,x, y))
C# 
using System;

class GfG {

    public static int minCost(int n, int m, 
                                            int[] x, int[] y) {
        
        // Sort the cutting costs in ascending order
        Array.Sort(x);
        Array.Sort(y);

        int hCount = 1, vCount = 1;
        int i = x.Length - 1, j = y.Length - 1;
        int totalCost = 0;

        // Process the cuts in greedy manner
        while (i >= 0 && j >= 0) {
            
            // Choose the larger cost cut to 
            // minimize future costs
            if (x[i] >= y[j]) {
                totalCost += x[i] * hCount;
                vCount++;
                i--;
            }
            else {
                totalCost += y[j] * vCount;
                hCount++;
                j--;
            }
        }

        // Process remaining vertical cuts
        while (i >= 0) {
            totalCost += x[i] * hCount;
            vCount++;
            i--;
        }

        // Process remaining horizontal cuts
        while (j >= 0) {
            totalCost += y[j] * vCount;
            hCount++;
            j--;
        }

        return totalCost;
    }
    
    public static void Main() {
        
        int n=4,m=6;
        int[] x = {2, 1, 3, 1, 4};
        int[] y = {4, 1, 2};

        Console.WriteLine(minCost(n,m, x, y));
    }
}
JavaScript 
function minCost( n,m, x, y) {
    
    // Sort the cutting costs in ascending order
    x.sort((a, b) => a - b);
    y.sort((a, b) => a - b);

    let hCount = 1, vCount = 1;
    let i = x.length - 1, j = y.length - 1;
    let totalCost = 0;

    while (i >= 0 && j >= 0) {
        
        // Choose the larger cost cut to 
        // minimize future costs
        if (x[i] >= y[j]) {
            totalCost += x[i] * hCount;
            vCount++;
            i--;
        } 
        else {
            totalCost += y[j] * vCount;
            hCount++;
            j--;
        }
    }

    // Process remaining vertical cuts
    while (i >= 0) {
        totalCost += x[i] * hCount;
        vCount++;
        i--;
    }

    // Process remaining horizontal cuts
    while (j >= 0) {
        totalCost += y[j] * vCount;
        hCount++;
        j--;
    }

    return totalCost;
}

// Driver Code
let n = 4,m = 6;
let x = [2, 1, 3, 1, 4];
let y = [4, 1, 2];

console.log(minCost(n,m, x, y));

Output
42
Comment
Article Tags:
Greedy
DSA

Explore