# Minimum Cost for Cutting Cake II
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-for-cutting-cake-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-for-cutting-cake-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-cost-for-cutting-cake-ii/image0.gif)

* 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 <= 105`
* `horizontalCut.length == m - 1`
* `verticalCut.length == n - 1`
* `1 <= horizontalCut[i], verticalCut[i] <= 103`

# Approaches
## Dynamic Programming with Bitmasking
This approach attempts to solve the problem by exploring every possible sequence of cuts using dynamic programming with bitmasking. A state in our DP is defined by the set of horizontal and vertical cuts that have already been performed. These sets are represented by bitmasks. For each state, we recursively calculate the minimum cost by trying every possible next cut (both horizontal and vertical) and choosing the one that leads to the minimum total cost for the subsequent cuts.
**Time:** O((m+n) * 2^(m+n)). There are `2^(m-1) * 2^(n-1)` states, and for each state, we iterate through up to `m-1 + n-1` possible next cuts. · **Space:** O(2^(m+n)). The memoization table requires `2^(m-1) * 2^(n-1)` entries.
**Pros:** It is a correct approach that is guaranteed to find the optimal solution by exhaustively checking all possibilities.
**Cons:** Extremely high time and space complexity, making it impractical for the given constraints.; The state space grows exponentially with `m` and `n`, leading to Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) errors for anything but very small inputs.
### Explanation
The core of this method is a recursive function, let's call it `solve(hMask, vMask)`, which computes the minimum cost to finish cutting the cake given that the cuts represented by `hMask` (for horizontal) and `vMask` (for vertical) are already done. The cost of making a new cut depends on the number of pieces it must slice through. A horizontal cut slices through a number of pieces equal to the current number of vertical segments (`popcount(vMask) + 1`). A vertical cut slices through a number of pieces equal to the current number of horizontal segments (`popcount(hMask) + 1`). The function explores making each available cut, recursively calls itself for the new state, and takes the minimum over all possibilities. Memoization is used to store the results for each `(hMask, vMask)` pair to avoid redundant computations. However, due to the `2^(m-1) * 2^(n-1)` possible states, this approach is not feasible for the problem's constraints.

```java
// This is a conceptual implementation and will time out for the given constraints.
import java.util.Arrays;

class Solution {
    private long[][] memo;
    private int m, n;
    private int[] horizontalCut, verticalCut;
    private int hTargetMask, vTargetMask;

    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        // This approach is too slow for the given constraints but illustrates the concept.
        if (m > 15 || n > 15) return -1; // Heuristic check to prevent memory errors
        this.m = m;
        this.n = n;
        this.horizontalCut = horizontalCut;
        this.verticalCut = verticalCut;
        this.hTargetMask = (1 << (m - 1)) - 1;
        this.vTargetMask = (1 << (n - 1)) - 1;
        this.memo = new long[1 << (m - 1)][1 << (n - 1)];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(0, 0);
    }

    private long solve(int hMask, int vMask) {
        if (hMask == hTargetMask && vMask == vTargetMask) {
            return 0;
        }
        if (memo[hMask][vMask] != -1) {
            return memo[hMask][vMask];
        }

        long minCost = Long.MAX_VALUE;
        int hPieces = Integer.bitCount(hMask) + 1;
        int vPieces = Integer.bitCount(vMask) + 1;

        // Try making a horizontal cut
        if (hMask != hTargetMask) {
            for (int i = 0; i < m - 1; i++) {
                if ((hMask & (1 << i)) == 0) {
                    long currentCost = (long) horizontalCut[i] * vPieces + solve(hMask | (1 << i), vMask);
                    minCost = Math.min(minCost, currentCost);
                }
            }
        }

        // Try making a vertical cut
        if (vMask != vTargetMask) {
            for (int i = 0; i < n - 1; i++) {
                if ((vMask & (1 << i)) == 0) {
                    long currentCost = (long) verticalCut[i] * hPieces + solve(hMask, vMask | (1 << i));
                    minCost = Math.min(minCost, currentCost);
                }
            }
        }

        return memo[hMask][vMask] = minCost;
    }
}
```
### Algorithm
- Define a recursive function `solve(hMask, vMask)` with memoization, where `hMask` and `vMask` are bitmasks representing the cuts already made.
- The base case for the recursion is when all cuts have been made (all bits in masks are set), in which case the cost is 0.
- If the result for a state `(hMask, vMask)` is already in the memoization table, return it.
- To compute the cost for a state, initialize a `minCost` variable to infinity.
- Determine the current number of horizontal and vertical pieces. The number of horizontal pieces is `popcount(hMask) + 1`, and vertical pieces is `popcount(vMask) + 1`.
- Iterate through all horizontal cuts. If a cut `i` has not been made yet, calculate the cost of making it now: `cost = horizontalCut[i] * (number of vertical pieces) + solve(new_hMask, vMask)`. Update `minCost` with this value if it's smaller.
- Similarly, iterate through all vertical cuts. If a cut `j` has not been made, calculate its cost: `cost = verticalCut[j] * (number of horizontal pieces) + solve(hMask, new_vMask)`. Update `minCost` accordingly.
- Store the computed `minCost` in the memoization table and return it.
- The initial call to the function will be `solve(0, 0)`.

## Greedy Approach by Sorting All Cuts
A more efficient method is a greedy approach. The key insight is that it is always optimal to perform the cut with the highest cost as early as possible. The cost of a cut is its base cost multiplied by the number of pieces it divides. By making expensive cuts when the cake is in fewer pieces, we minimize their contribution to the total cost. This strategy involves combining all cuts, sorting them by cost in descending order, and then processing them one by one.
**Time:** O(N log N), where `N = m + n`. The dominant operation is sorting the combined list of cuts. · **Space:** O(m+n). We need to create a list to store all `m-1 + n-1` cuts.
**Pros:** Finds the optimal solution with a much better time complexity than the DP approach.; The greedy logic is intuitive and relatively straightforward to implement.
**Cons:** Requires `O(m+n)` auxiliary space to store the combined list of cuts.; The time complexity, while polynomial, is slightly worse than the most optimal approach due to sorting a larger, combined array.
### Explanation
This greedy strategy is based on the observation that the total cost is a sum of terms, where each term is `cost_of_cut * number_of_pieces_it_cuts`. To minimize this sum, we should pair large costs with small multipliers. The multipliers (`hPieces` and `vPieces`) start at 1 and increase as we make more cuts. Therefore, by processing cuts in descending order of their base cost, we ensure that the highest costs are multiplied by the smallest possible multipliers.

To implement this, we can create a helper class, say `Cut`, to store a cut's cost and its type (horizontal or vertical). We populate a list with all cuts from `horizontalCut` and `verticalCut`. Then, we sort this list in descending order of cost. Finally, we iterate through the sorted list, calculating the cost for each cut based on the current number of horizontal and vertical pieces and updating the piece counts.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    class Cut implements Comparable<Cut> {
        int cost;
        char type; // 'H' for horizontal, 'V' for vertical

        Cut(int cost, char type) {
            this.cost = cost;
            this.type = type;
        }

        @Override
        public int compareTo(Cut other) {
            return Integer.compare(other.cost, this.cost);
        }
    }

    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        List<Cut> cuts = new ArrayList<>();
        for (int cost : horizontalCut) {
            cuts.add(new Cut(cost, 'H'));
        }
        for (int cost : verticalCut) {
            cuts.add(new Cut(cost, 'V'));
        }

        // Sort cuts in descending order of cost
        Collections.sort(cuts);

        long totalCost = 0;
        long hPieces = 1;
        long vPieces = 1;

        for (Cut cut : cuts) {
            if (cut.type == 'H') {
                totalCost += (long) cut.cost * vPieces;
                hPieces++;
            } else { // type == 'V'
                totalCost += (long) cut.cost * hPieces;
                vPieces++;
            }
        }

        return totalCost;
    }
}
```
### Algorithm
- Create a custom `Cut` class or a similar structure to hold the cost and type ('H' for horizontal, 'V' for vertical) of each cut.
- Create a single list and populate it with all `m-1` horizontal cuts and `n-1` vertical cuts.
- Sort this combined list of cuts in descending order based on their cost.
- Initialize `totalCost = 0`, `hPieces = 1` (representing one initial horizontal piece), and `vPieces = 1` (one initial vertical piece).
- Iterate through the sorted list of cuts.
- For each cut:
  - If it's a horizontal cut, add `cost * vPieces` to `totalCost` and then increment `hPieces`.
  - If it's a vertical cut, add `cost * hPieces` to `totalCost` and then increment `vPieces`.
- After iterating through all the cuts, `totalCost` will hold the minimum cost.

## Optimized Greedy Approach with Two Pointers
This is the most efficient approach, building upon the same greedy strategy but with an implementation optimization. Instead of merging the two arrays of cuts into a single large array and then sorting, we can sort the `horizontalCut` and `verticalCut` arrays independently. After sorting, we can use a two-pointer technique, similar to the merge step in merge-sort, to pick the highest-cost cut at each step from either of the two arrays.
**Time:** O(m log m + n log n). This is dominated by the time to sort the two cut arrays. The subsequent two-pointer traversal takes linear time, O(m+n). · **Space:** O(log m + log n) or O(1). This is the space used by the in-place sorting algorithm (e.g., Quicksort's recursion stack). If we cannot modify the input arrays, it becomes O(m+n) to store copies.
**Pros:** Most efficient solution in terms of both time and space complexity.; Avoids the overhead of creating and managing a combined list of cuts.; The time complexity is governed by sorting two smaller arrays instead of one large one, which is faster in practice.
**Cons:** This approach requires modifying the input arrays by sorting them. If the input arrays are immutable, we would need to create copies, which would increase the space complexity to `O(m+n)`.
### Explanation
By sorting both `horizontalCut` and `verticalCut` arrays (e.g., in ascending order), we can use pointers starting from the end of each array to access the cuts in descending order of cost. We maintain a pointer for horizontal cuts (`hPtr`) and one for vertical cuts (`vPtr`). In each step, we compare the costs at the current pointers and choose the larger one. This simulates iterating through a merged, sorted list of all cuts without actually creating one.

If `horizontalCut[hPtr]` is greater than `verticalCut[vPtr]`, we 'perform' this horizontal cut. The cost added is `horizontalCut[hPtr] * vPieces`. We then increment the number of horizontal pieces (`hPieces`) and move the horizontal pointer (`hPtr--`). If the vertical cut is more expensive, we do the analogous operations for the vertical cut. This continues until all cuts are processed. This method avoids the `O(m+n)` space overhead of the previous approach and has a slightly better time complexity constant.

```java
import java.util.Arrays;

class Solution {
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);

        long totalCost = 0;
        long hPieces = 1;
        long vPieces = 1;
        int hPtr = m - 2; // Pointer for horizontalCut, starting from the largest
        int vPtr = n - 2; // Pointer for verticalCut, starting from the largest

        while (hPtr >= 0 || vPtr >= 0) {
            long hCost = (hPtr >= 0) ? horizontalCut[hPtr] : -1;
            long vCost = (vPtr >= 0) ? verticalCut[vPtr] : -1;

            if (hCost > vCost) {
                // Take horizontal cut
                totalCost += hCost * vPieces;
                hPieces++;
                hPtr--;
            } else {
                // Take vertical cut
                totalCost += vCost * hPieces;
                vPieces++;
                vPtr--;
            }
        }

        return totalCost;
    }
}
```
### Algorithm
- Sort both `horizontalCut` and `verticalCut` arrays. For this strategy, it's convenient to sort them in ascending order.
- Initialize `totalCost = 0`, `hPieces = 1`, and `vPieces = 1`.
- Initialize two pointers: `hPtr` to the end of the sorted `horizontalCut` array (`m-2`) and `vPtr` to the end of the sorted `verticalCut` array (`n-2`). These pointers will now point to the cuts with the highest costs.
- Loop while either `hPtr` or `vPtr` is valid (i.e., `>= 0`).
- Inside the loop, compare the costs at `horizontalCut[hPtr]` and `verticalCut[vPtr]`.
  - If the horizontal cut cost is greater than the vertical cut cost (or if the vertical pointer is out of bounds), process the horizontal cut. Add `horizontalCut[hPtr] * vPieces` to `totalCost`, increment `hPieces`, and decrement `hPtr`.
  - Otherwise, process the vertical cut. Add `verticalCut[vPtr] * hPieces` to `totalCost`, increment `vPieces`, and decrement `vPtr`.
- Continue until both pointers have traversed their respective arrays. The final `totalCost` is the minimum cost.

# Solutions
### Java

```java
class Solution {
public
  long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
    Arrays.sort(horizontalCut);
    Arrays.sort(verticalCut);
    long ans = 0;
    int i = m - 2, j = n - 2;
    int h = 1, v = 1;
    while (i >= 0 || j >= 0) {
      if (j < 0 || (i >= 0 && horizontalCut[i] > verticalCut[j])) {
        ans += 1L * horizontalCut[i--] * v;
        ++h;
      } else {
        ans += 1L * verticalCut[j--] * h;
        ++v;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumCost(int m, int n, vector<int> &horizontalCut,
                        vector<int> &verticalCut) {
    sort(horizontalCut.rbegin(), horizontalCut.rend());
    sort(verticalCut.rbegin(), verticalCut.rend());
    long long ans = 0;
    int i = 0, j = 0;
    int h = 1, v = 1;
    while (i < m - 1 || j < n - 1) {
      if (j == n - 1 || (i < m - 1 && horizontalCut[i] > verticalCut[j])) {
        ans += 1LL * horizontalCut[i++] * v;
        h++;
      } else {
        ans += 1LL * verticalCut[j++] * h;
        v++;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int: horizontalCut . sort(reverse=True) verticalCut . sort(reverse=True) ans = i = j = 0 h = v = 1 while i < m - 1 or j < n - 1: if j == n - 1 or (i < m - 1 and horizontalCut[i] > verticalCut[j]): ans += horizontalCut[i] * v h, i = h + 1, i + 1 else: ans += verticalCut[j] * h v, j = v + 1, j + 1 return ans

```