Skip to main content
Talentd

Minimum Cost for Cutting Cake I - Solution & Explanation

MediumArrayDynamic ProgrammingGreedySorting26 min read
Practice this problem

Problem Statement

There is an m x n cake that needs to be cut into 1 x 1 pieces.

You are given integers m, n, and two arrays:

  • horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i.
  • verticalCut of size n - 1, where verticalCut[j] represents the cost to cut along the vertical line j.

In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:

  1. Cut along a horizontal line i at a cost of horizontalCut[i].
  2. Cut along a vertical line j at a cost of verticalCut[j].

After the cut, the piece of cake is divided into two distinct pieces.

The cost of a cut depends only on the initial cost of the line and does not change.

Return the minimum total cost to cut the entire cake into 1 x 1 pieces.

 

Example 1:

Input: m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

Output: 13

Explanation:

  • Perform a cut on the vertical line 0 with cost 5, current total cost is 5.
  • Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
  • Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
  • Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.
  • Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.

The total cost is 5 + 1 + 1 + 3 + 3 = 13.

Example 2:

Input: m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

Output: 15

Explanation:

  • Perform a cut on the horizontal line 0 with cost 7.
  • Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.
  • Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.

The total cost is 7 + 4 + 4 = 15.

 

Constraints:

  • 1 <= m, n <= 20
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 103

Approach Overview

Problem Overview: You are given the costs of horizontal and vertical cuts needed to divide an m x n cake into 1x1 pieces. Each time you perform a cut, the cost is multiplied by the number of current segments in the opposite direction. The goal is to choose the order of cuts so the total cost is minimized.

Approach 1: Greedy with Priority Queue (O((m+n) log(m+n)) time, O(m+n) space)

The key observation: expensive cuts should be applied as early as possible. When you perform a cut later, it gets multiplied by more segments, which increases its total cost. To minimize the final sum, always perform the highest-cost cut first. Push all horizontal and vertical cuts into a max heap (priority queue) and repeatedly extract the largest cost. Maintain counters for horizontal and vertical segments. A horizontal cut contributes cost * verticalSegments, while a vertical cut contributes cost * horizontalSegments. This greedy strategy guarantees the minimum cost because it prevents expensive cuts from being multiplied by larger segment counts later.

This approach relies heavily on ideas from Greedy algorithms and works well because the cost contribution grows multiplicatively as segments increase.

Approach 2: Greedy with Sorting (O((m+n) log(m+n)) time, O(1) extra space)

Instead of using a heap, you can sort both cost arrays in descending order and simulate the greedy selection using two pointers. Compare the next largest horizontal and vertical cost and pick the larger one. Update the segment counters accordingly and accumulate the weighted cost. Sorting allows you to process cuts in decreasing order without maintaining a heap, making the implementation simpler while keeping the same asymptotic complexity.

This version primarily uses Array manipulation and Sorting. In practice it runs slightly faster due to lower constant factors compared to a priority queue.

Approach 3: Dynamic Programming (O(h * v) time, O(h * v) space)

A Dynamic Programming formulation considers how many horizontal and vertical cuts have already been performed. Let dp[i][j] represent the minimum cost after performing i horizontal and j vertical cuts. The next operation can either be another horizontal cut or a vertical cut. A horizontal cut adds horizontalCost[i] * (j + 1), while a vertical cut adds verticalCost[j] * (i + 1). Transition between states until all cuts are used. This explicitly explores interleavings of cut orders but is slower and uses more memory than the greedy strategy.

Recommended for interviews: The greedy strategy with sorting or a priority queue is the expected solution. It demonstrates the core insight: performing higher-cost cuts earlier prevents them from being multiplied by larger segment counts. Mentioning the DP formulation shows deeper understanding, but implementing the greedy approach efficiently is what interviewers typically look for.

Approach 1: Greedy Approach: Priority Queue

The key idea is to prioritize cuts with higher costs first, as these influence the subsequential cutting costs significantly. We use a priority queue (or max heap) to always perform the cut with the maximum cost from both available horizontal and vertical cuts. This ensures that more expensive cuts are counted first while there are more pieces to divide the cake into.

This solution starts by sorting both the horizontal and vertical cut arrays in descending order. It maintains counters for horizontal pieces and vertical pieces. Then, using a greedy strategy, it determines whether it should cut horizontally or vertically by selecting the maximum available cost cut. The total cost is accumulated by the number of pieces influenced by the cut. The iteration continues until all cuts are made, ensuring it checks both remaining horizontal and vertical cuts if one is exhausted first. This method efficiently calculates the minimum possible cost.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O((m + n) log(m + n)) due to the sorting step. Space complexity: O(1) since it uses only a fixed amount of extra space.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

In the dynamic programming approach, we define a 2D DP array where dp[i][j] represents the minimal cost to cut the i x j subgrid into 1 x 1 pieces. This approach utilizes memoization to store previously calculated results efficiently. It systematically builds the solution by evaluating subproblems and their optimal solutions.

This DP-based solution defines a state dp[i][j] where i x j is the cost to split the cake to 1x1 segments. By evaluating and combining each row and column cut efficiently, it determines the cumulative minimal cost. It recursively breaks down the problem while memoizing results to avoid re-computation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), Space complexity: O(m * n).

Try this approach in the editor →

Approach 3: Greedy + Two Pointers

For a given position, the earlier you cut, the fewer cuts are needed, so it is clear that positions with higher costs should be cut earlier.

Therefore, we can sort the arrays horizontalCut and verticalCut in descending order, and then use two pointers i and j to point to the costs in horizontalCut and verticalCut, respectively. Each time, we choose the position with the larger cost to cut, while updating the corresponding number of rows and columns.

Each time a horizontal cut is made, if the number of columns before the cut was v, then the cost of this cut is horizontalCut[i] times v, and then the number of rows h is incremented by one; similarly, each time a vertical cut is made, if the number of rows before the cut was h, then the cost of this cut is verticalCut[j] times h, and then the number of columns v is incremented by one.

Finally, when both i and j reach the end, return the total cost.

The time complexity is O(m times log m + n times log n), and the space complexity is O(log m + log n). Here, m and n are the lengths of horizontalCut and verticalCut, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach: Priority Queue

Time Complexity: O((m + n) log(m + n)) due to the sorting step. Space complexity: O(1) since it uses only a fixed amount of extra space.

Dynamic Programming Approach

Time Complexity: O(m * n), Space complexity: O(m * n).

Greedy + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Priority QueueO((m+n) log(m+n))O(m+n)When you want a straightforward greedy implementation that always selects the largest remaining cut.
Greedy with SortingO((m+n) log(m+n))O(1)Most common interview solution; simpler and faster than heap-based implementation.
Dynamic ProgrammingO(h * v)O(h * v)Useful for understanding all possible cut orders or when demonstrating DP reasoning.

Video Solution

Minimum Cost for Cutting Cake I & II | Thought Process | Leetcode 3218 | 3219 | codestorywithMIK • codestorywithMIK • 6,017 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Cost for Cutting Cake I easy or hard?
Minimum Cost for Cutting Cake I is typically classified as Medium difficulty. The implementation is straightforward once you recognize the greedy insight, but identifying why the largest-cost-first strategy minimizes the total cost requires algorithmic intuition.
Minimum Cost for Cutting Cake I Python/Java solution
Python and Java implementations usually sort both cost arrays in descending order and iterate with two pointers. At each step the algorithm selects the larger cut cost, multiplies it by the current number of opposite-direction segments, and updates the segment count. The logic is identical across Python, Java, C++, and JavaScript.
How to solve Minimum Cost for Cutting Cake I in O(n log n)?
Sort the horizontal and vertical cut costs in descending order. Maintain counters for horizontal and vertical segments. At each step choose the larger remaining cost, add its weighted contribution (cost multiplied by current segments in the opposite direction), and update the segment count. This greedy ordering ensures the total cost is minimized with O((m+n) log(m+n)) complexity.
What is the best approach for Minimum Cost for Cutting Cake I?
The optimal approach is a greedy strategy that always performs the highest-cost cut first. By sorting the horizontal and vertical cut costs in descending order (or using a max heap), you ensure expensive cuts happen when the number of segments is small. This minimizes the multiplication effect that occurs as the cake gets divided. The time complexity is O((m+n) log(m+n)).
Is Minimum Cost for Cutting Cake I asked at Google/Amazon/Meta?
This problem is a variation of the classic board-cutting greedy problem frequently asked in interviews at companies like Amazon and Google. The key concept—choosing the largest cost first to minimize multiplicative impact—appears in many greedy interview questions.
What data structure is used in Minimum Cost for Cutting Cake I?
The solution typically uses arrays combined with sorting or a max priority queue. Sorting enables processing costs in descending order, while a priority queue allows dynamically selecting the highest remaining cut. Both implementations rely on greedy decision making.
What is the time complexity of Minimum Cost for Cutting Cake I?
The optimal greedy solution runs in O((m+n) log(m+n)) time due to sorting or priority queue operations. Each cut is processed exactly once while maintaining segment counts. Space complexity ranges from O(1) with sorting to O(m+n) when using a priority queue.

Ready to solve this problem?

Practice Minimum Cost for Cutting Cake I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost for Cutting Cake II